סלית'רלינק

טבלת סלית'רלינק לא פתורה

סלית'רלינק (ביפנית: スリザーリンク, ידוע גם כגדרות או טאקג'אקי) היא חידת היגיון שפורסמה על ידי ההוצאה לאור ניקולי.

==חוקים==

טבלת סלית'רלינק פתורה

המשחק מתבצע על סריג מרובע של נקודות. בחלק מן הריבועים הנמצאים בין הנקודות (ללא צלעות - הנקודות מסמנות את קודקודיהם) נמצאים מספרים. המטרה היא לחבר נקודות הסמוכות (סמיכות במאונך או במאוזן) כך שהקווים ייצרו לולאה פשוטה ללא קצוות פתוחים. בנוסף, מספר בתוך ריבוע מייצג כמה מצלעותיו משמשות כקטע מן הלולאה.

סוגים אחרים של גרפים מישוריים יכולים להיות בשימוש במקום הטבלה הסטנדרטית, עם מספר משתנה של פאות לכל קודקוד או קודקודים למצולע. תבניות אלה כוללות צורות כמו פתיתי שלג, ריצוף פנרוז ועוד. הצורות הללו מוסיפות סיבוכיות בכך שהן מגוונות את מספר המעברים האפשריים בכל הצטלבות, ו\או את מספר הצלעות לכל מצולע; אך בכל מקרה, אותם החוקים נדרשים לפתרון כל הצורות.

==שיטות פתרון==

===סימון===

כאשר מספר הקווים סביב תא מסוים משתווה לאותו מספר, שאר הקווים הפוטנציאליים מסביב לאותו תא יכולים להישלל ככאלה עם קווים. בדרך כלל מסמנים מקומות כאלה עם X.

סימון שימושי נוסף בפתירת סלית'רלינק היא קשת של 90° בין שני קווים פוטנציאליים סמוכים, המסמלת כי בדיוק אחד משניהם חייב להתמלא (להיות חלק מן הלולאה). סימון דומה, הוא כאשר מסמנים קשת כפולה בין קווים פוטנציאליים סמוכים, ומסמל כי שניהם או אף אחד מהם חייב להיות מלא. סימונים אלה לא הכרחיים לצורך הפתרון, אבל יכולים להיות לעזר רב בדרך אליו.

סימון קשתות מסביב ל-2 בפינה

חלק ניכר מהשיטות הבאות אפשר לפשט לשני צעדים פשוטים יותר בשימוש עם קשתות.

===בדיוק 2 או 0 קווים בכל נקודה===

מפתח טוב לפתרון החידה, הוא ההבנה כי מכל נקודה יכולים לצאת שני קווים או אף קו כלל. כך שאם לנקודה במרכז הטבלה, ולא בקצה או בפינה, יש שלושה קווים פוטנציאליים שסומנו ב-X, הרביעי גם חייב להיות מסומן ב-X. זאת משום שלנקודה לא יכול להיות רק קו אחד - אם היה, לא היה לו נתיב יציאה. בדומה, אם לנקודה בקצה הטבלה, לא בפינה, ישנם שני קווים המגיעים אליה ומסומנים ב-X, השלישי גם כן חייב להיות מסומן ב-X. ואם לנקודה בפינה יש קו פוטנציאלי אחד המסומן ב-X, על השני להיות גם הוא מסומן ב-X.

יישום של כלל פשוט זה מוביל למסקנות מורכבות יותר. הכרה בדפוסי חשיבה אלו יעזרו מאוד בפתרון החידה.

====פינות====

* אם ישנו 1 בפינה, על הקווים הפוטנציאליים לפינה להיות מסומנים ב-X, משום שקו הנכנס לפינה זו לא יוכל לצאת ממנה מבלי לעבור שוב על יד ה-1. כלל זה תקף גם כאשר שני קווים המובילים לאותה הפינה בריבוע של ה-1 מסומנים ב-X.

1 בפינה

* אם 3 נמצא בפינה, שני הקצוות החיצוניים של הטבלה יכולים להיות מלאים, מכיוון שאחרת, החוק דלעיל יופר.

3 בפינה

* אם 2 נמצא בפינה, שני קווים צריכים לצאת ולהתרחק מה-2 על הגבול.

2 בפינה

====חוקים לריבועים עם 3====

* אם 3 סמוך ל-0 במאונך או במאוזן, על כל הצלעות של ה-3 להיות מלאות חוץ מהצלע הסמוכה ל-0. בנוסף, אפשר למלא את שני הקווים הניצבים ל תאים הסמוכים.

3 סמוך ל-0

* אם שני '3'-ים סמוכים זה לזה במאונך או במאוזן, הצלע המשותפת שלהם צריכה להיות מלאה, משום שהאפשרות האחרת היחידה היא לולאה סגורה שלא ניתנת לחיבור לאף קו אחר. כמו כן, שני הקווים החיצוניים ל-'3'-ים (מקבילים לצלע המשותפת) חייבים להיות מלאים. בנוסף, הקטע העובר בין ה-'3'-ים תמיד יעטוף אותם בצורת S. לכן, הקו שבין ה-'3'-ים לא יכול להמשיך בקו ישר, והצלעות הממשיכות אותו יכולות להיות מסומנות ב-X.

שני '3'-ים סמוכים

* אם 3 סמוך ל-0 באלכסון, שתי הצלעות הפוגשות את הפינה הנושקת ל-0 צריכות להיות מלאות. זאת משום שאם אחד משתי הצלעות הללו הייתה פתוחה, לקו שנגמר בפינה של ה-0 לא היה נתיב להמשיך. כלל זה דומה מאוד לכלל של ה-3 בפינה.

3 באלכסון ל-0

* בדומה, אם ל-3 יש פינה עם שני 'X'-ים היוצאים ממנה, אז שתי הצלעות של ה-3 הנפגשות בפינה צריכות להיות מלאות. זאת מכיוון שאם אחת משתי הצלעות הללו הייתה פתוחה, השנייה הייתה צריכה להיות מלאה (משום של-3 יכולה להיות רק צלע פתוחה אחת), וכך תפגוש שלושה 'X'-ים בפינה, דבר שאינו אפשרי משום שמכל נקודה בטבלה יכולים לצאת או שני קווים או שום קו.
* אם קו מגיע לפינה של 3, חייבים להיות קווים בשתי הצלעות של ה-3 שלא סמוכות לפינה זו, משום שאם הצלע הריקה היחידה של ה-3 לא הייתה סמוכה אליהם, היו מחוברים שלושה קווים לפינה. יתר על כן, הקטע המוביל מה-3 החוצה בפינה והפוגש את הקו חייב להיות ריק; אם היה מלא, אף אחת משתי הצלעות הריקות שנשארו ל-3 לא הייתה יכולה להיות עם קו.

3 ליד קו

====אלכסונים של '3'-ים ו-'2'-ים====

* אם שני '3'-ים סמוכים באלכסון, הצלעות שלא נפגשות בפינה הנושקת לשני ה'3'-ים חייבות להיות מלאות.

שני '3'-ים באלכסון

* בדומה, אם שני '3'-ים נמצאים באותו האלכסון, ומופרדים על ידי כל מספר של '2'-ים (ורק '2'-ים), על הצלעות החיצוניות של ה'3'-ים להיות מלאות, ממש כאילו היו סמוכים באלכסון.

אלכסון של '3'-ים עם 2 ביניהם

*אם ישנה סדרה של '2'-ים בקו אלכסוני, ובקצה הסדרה ישנה פינת צלעות מלאות הנפגשת עם ה-'2'-ים, פינות צלעות מלאות תואמות צריכות להיות לאורך כל הסדרה.

סדרה של שניים או יותר '2'-ים הנפסקת על ידי שני קווים המצביעים לסדרה

* להלן סדרה של '2'-ים המסתיימת ב-3. דוגמה זו משלבת כמה מן הכללים שתוארו לעיל. ליד ה-2 המסיים את הסדרה יש פינת צלעות מלאה הכוללת בתוכה אחת (אך לא שתיים) מהצלעות בפינה החיצונית שלו: הפינה המלאה נמצאת בפינה המרוחקת מפינת ה-3. מכך אפשר להבין שאפשר למלא את שתי הצלעות החיצוניות של ה-3. זאת מכיוון ש: (1) הצלע הימנית שה-2 התחתון חייב להיות ריק, אז (2) הצלע העליונה או השמאלית של ה-2 התחתון צריכה להיות מלאה, ולכן (3) ל-2 האמצעי לא יכולים להיות קווים גם בצלע הימנית וגם בצלע התחתונה שלו (אחרת, שלושה קווים היו נפגשים בפינה הימנית-תחתונה שלו), ולכן (4) חייב להיות קו בצלע העליונה או השמאלית שלו, ולכן (5) הצלע העליונה והצלע השמאלית של ה-3 חייבות להיות מלאות. אפשר ליישם מחרוזת דומה של הסקת מסקנות בכל אלכסון של '2'-ים המסתיים ב-3.

אלכסון של '2'-ים המסתיים ב-3

====אלכסונים של 3 ו-1====

* אם 1 ו-3 סמוכים באלכסון ושתי הצלעות החיצוניות של ה-1 מסומנות ב-X, אז שתי הצלעות החיצוניות של ה-3 צריכות להיות מלאות.

אלכסון של 3 ו-1

* המקרה ההפוך נכון גם הוא: אם שתי הצלעות החיצוניות ל-3 מלאות, אזי ששתי הצלעות החיצוניות ל-1 צריכות להיות מסומנות ב-X.

מקרה נגדי לאלכסון של 3 ו-1

====חוק לתא עם 2====

אם מסביב ל-2 יש צלע כלשהי המסומנת ב-X, אז קו המגיע לאחת משתי הפינות שאינן סמוכות לצלע עם ה-X לא יכול להתרחק בזווית ישרה מה-2, שהרי כך שני קווים מסביב ל-2 יהיו בלתי אפשריים, ויכול להיות מסומן ב-X. זאת אומרת שהקו המגיע ל-2 חייב להמשיך באחת משתי הצלעות של ה-2. לכן, הקו השני של ה-2 חייב להיות הצלע החופשייה היחיד, בסמוך לקו שסומן במקור ב-X, כך שאפשר למל אותו.
לעומת זאת, אם ל-2 יש קו בצלע אחת, וצלע סמוכה המסומנת ב-X, אז הקו השני צריך להיות באחת משתי הצלעות שנשארו, ולצאת מהפינה הנגדית. אם אחת משתי יציאות אלו מסומנות ב-X, אזי הוא צריך לצאת במסלול השני.

2 ליד קו

====חוקים לתאים עם 1====

* אם קו מגיע לפינה של 1, ואם מתוך שלושת הכיוונים אליהם הקו יכול לפנות, הקו שאינו צלע של ה-1 מסומן ב-X, שתי הצלעות הסמוכות לפינה הנגדית של ה-1 יכולות להיות מסומנות ב-X גם הן.

1 ליד קו

* כלל זה נכון גם להפך: אם קו מגיע לפינה של 1, ושתי הצלעות הסמוכות לפינה הנגדית של ה-1 מסומנות ב-X, אז מתוך שלושת הכיוונים אליהם הקו יכול לפנות, הקו שאינו צלע של ה-1 יכול להיות מסומן ב-X.

מקרה נגדי ל-1 ליד קו

* אם שני '1'-ים סמוכים באלכסון, אז מתוך שמונת הקטעים המקיפים את שני התאים הללו, או ארבעת הקטעים הפנימיים (החולקים נקודת קצה אחת - הנקודה שבין ה-'1'-ים) או ארבעת הקטעים החיצוניים צריכים להיות מסומנים ב-X. אם כן, אם שני קווים חיצוניים או פנימיים לאחד מהקווים מסומנים ב-X, שני הקטעים התואמים (הפנימיים או החיצוניים) של ה-1 השני צריכים להיות מסומנים ב-ס גם הם.

'1'-ים סמוכים באלכסון
'1'-ים סמוכים באלכסון

*אם שני '1'-ים סמוכים לאורך קצה הטבלה, הקו שביניהם צריך להיות מסומן ב-X, מכיוון שלא יהיה לו לאן להמשיך מהקצה.

===מספר זוגי של קצוות באזור סגור===

באזור סגור של הסריג (שממנו אין שום מעבר לקווים "לברוח"), לא יכול להיות מספר אי-זוגי של קצוות קטעים לא מחוברים, מאחר שכל קצוות הקטעים חייבים להיות מחוברים למשהו. לעיתים קרובות, כלל זה יפסול אפשרות אחת או יותר שהיו נראות סבירות לולא כלל זה.

===משפט עקומת ז'ורדן===

בחידה קשה במיוחד, אפשר להשתמש במשפט עקומת ז'ורדן, שאומר כי כל עקומה פתוחה המתחילה ומסתיימת מחוץ לעקומה סגורה, חייבת לחצות את העקומה הסגורה מספר זוגי של פעמים. באופן פרטני יותר, זאת אומרת שבכל שורה בטבלה צריך להיות מספר זוגי של קווים אנכיים ובכל טור בטבלה צריך להיות מספר זוגי של קווים אופקיים. כאשר רק קו פוטנציאלי אחד בשתי הקבוצות הללו לא ידוע, אפשר לקבוע האם הוא חלק מן הלולאה על פי משפט זה.

שיטה פשוטה לשימוש במשפט זה היא להשחיר את השטחים החיצוניים והפנימיים. כאשר רואים שני תאים חיצוניים או שני תאים פנימיים סמוכים זה לזה, אפשר לדעת שלא עובר קו ביניהם. המקרה ההפוך נכון גם כן: אם ידוע שלא עובר קו בין שני תאים, אזי ששני התאים הללו יהיו באותו ה"צבע" (שניהם בפנים או ששניהם בחוץ). בדומה, אם תא חיצוני ותא פנימי סמוכים, חייב לעבור קו ביניהם.

==היסטוריה==

סלית'רלינק היא חידה מקורית של ניקולי. היא הופיעה לראשונה בכתב העת Puzzle Communication Nikoli גיליון מספר 26 (יוני 1989). העורך שילב שתי חידות שהופיעו שם. בהתחלה, בכל ריבוע היה מספר.

==משחקי וידאו==

משחקי וידאו של סלית'רלינק יצאו ל-נינטנדו DS, כאשר הדסון סופט שחררו את סדרת חידות חלק 5: סלית'רלינק (Puzzle Series Vol. 5: Slitherlin) ביפן, בתאריך 16 בנובמבר 2006, ואגטק (Agetec) עם סלית'רלינק בהידור של ניקולי, Brain Buster Puzzle Pak, ששוחרר בצפון אמריקה, בתאריך 17 ביוני 2007.

==ראו גם==

* רשימת החידות של ניקולי

==קישורים חיצוניים==

* [http://www.nikoli.co.jp/en/puzzles/slitherlink.html הדף של ניקולי באנגלית על סלית'רלינק]
* [https://web.archive.org/web/20130120200317/http://fano.ics.uci.edu/cites/Document/On-the-NP-completeness-of-the-Slither-Link-Puzzle.html On the NP-completeness of the Slitherlink Puzzle] סלית'רלינק היא NP-שלמה
* [http://www.krazydad.com/slitherlink/ אתר הדן בצורות שונות של תבניות סלית'רלינק שאינן טבלה מלבנית]
* [http://www.kwontomloop.com KwontomLoop] -אתר חינמי עם חידות סלית'רלינק יומיות ברמות שונות. כולל בנוסף מערכת ניקוד להשוואה עם שחקנים אחרים.
* [http://www.conceptispuzzles.com/index.aspx?uri=puzzle/slitherlink/techniques www.conceptispuzzles.com] - אתר המראה שיטות פתרון מתקדמות.
* [http://games.softpedia.com/progDownload/sLitherLink-Download-17898.html games.softpedia.com] - סלית'רלינק להורדה המספק חידות ברמות שונות. כמו כן אפשר להעלות חידה לאתר על מנת לפתור אותה.
* [http://krazydad.com/slitherlink/ krazydad.com] הורדת מספר גדול של חידות סלית'רלינק הניתנות להדפסה.
* [https://archive.today/20130421213014/http://word.chaos.co.za/2012/10/12/slitherlink-notation chaos.co.za] מערכת סימנים המוצעים לפתרון סלית'רלינק
==הערות שוליים==

קטגוריה:תשבצי מספרים
קטגוריה:בעיות NP-שלמות
קטגוריה:שעשועי מתמטיקה
קטגוריה:משחקי חשיבה
קטגוריה:משחקי עט ונייר
קטגוריה:משחקי נינטנדו DS