סלית'רלינק
 | |
| כללי | |
|---|---|
| סוגה |
NP-complete game, חידת היגיון  |
| ארץ מקור |
יפן |
  | |
סלית'רלינק (ביפנית: スリザーリンク, ידוע גם כגדרות או טאקג'אקי) היא חידת היגיון שפורסמה על ידי ההוצאה לאור ניקולי.
חוקים
[עריכת קוד מקור | עריכה]המשחק מתבצע על סריג מרובע של נקודות. בחלק מן הריבועים הנמצאים בין הנקודות (ללא צלעות - הנקודות מסמנות את קודקודיהם) נמצאים מספרים. המטרה היא לחבר נקודות הסמוכות (סמיכות במאונך או במאוזן) כך שהקווים ייצרו לולאה פשוטה ללא קצוות פתוחים. בנוסף, מספר בתוך ריבוע מייצג כמה מצלעותיו משמשות כקטע מן הלולאה.
סוגים אחרים של גרפים מישוריים יכולים להיות בשימוש במקום הטבלה הסטנדרטית, עם מספר משתנה של פאות לכל קודקוד או קודקודים למצולע. תבניות אלה כוללות צורות כמו פתיתי שלג, ריצוף פנרוז ועוד. הצורות הללו מוסיפות סיבוכיות בכך שהן מגוונות את מספר המעברים האפשריים בכל הצטלבות, ו\או את מספר הצלעות לכל מצולע; אך בכל מקרה, אותם החוקים נדרשים לפתרון כל הצורות.
שיטות פתרון
[עריכת קוד מקור | עריכה]סימון
[עריכת קוד מקור | עריכה]כאשר מספר הקווים סביב תא מסוים משתווה לאותו מספר, שאר הקווים הפוטנציאליים מסביב לאותו תא יכולים להישלל ככאלה עם קווים. בדרך כלל מסמנים מקומות כאלה עם X.
סימון שימושי נוסף בפתירת סלית'רלינק היא קשת של 90° בין שני קווים פוטנציאליים סמוכים, המסמלת כי בדיוק אחד משניהם חייב להתמלא (להיות חלק מן הלולאה). סימון דומה, הוא כאשר מסמנים קשת כפולה בין קווים פוטנציאליים סמוכים, ומסמל כי שניהם או אף אחד מהם חייב להיות מלא. סימונים אלה לא הכרחיים לצורך הפתרון, אבל יכולים להיות לעזר רב בדרך אליו.
חלק ניכר מהשיטות הבאות אפשר לפשט לשני צעדים פשוטים יותר בשימוש עם קשתות.
בדיוק 2 או 0 קווים בכל נקודה
[עריכת קוד מקור | עריכה]מפתח טוב לפתרון החידה, הוא ההבנה כי מכל נקודה יכולים לצאת שני קווים או אף קו כלל. כך שאם לנקודה במרכז הטבלה, ולא בקצה או בפינה, יש שלושה קווים פוטנציאליים שסומנו ב-X, הרביעי גם חייב להיות מסומן ב-X. זאת משום שלנקודה לא יכול להיות רק קו אחד - אם היה, לא היה לו נתיב יציאה. בדומה, אם לנקודה בקצה הטבלה, לא בפינה, ישנם שני קווים המגיעים אליה ומסומנים ב-X, השלישי גם כן חייב להיות מסומן ב-X. ואם לנקודה בפינה יש קו פוטנציאלי אחד המסומן ב-X, על השני להיות גם הוא מסומן ב-X.
יישום של כלל פשוט זה מוביל למסקנות מורכבות יותר. הכרה בדפוסי חשיבה אלו יעזרו מאוד בפתרון החידה.
פינות
[עריכת קוד מקור | עריכה]- אם ישנו 1 בפינה, על הקווים הפוטנציאליים לפינה להיות מסומנים ב-X, משום שקו הנכנס לפינה זו לא יוכל לצאת ממנה מבלי לעבור שוב על יד ה-1. כלל זה תקף גם כאשר שני קווים המובילים לאותה הפינה בריבוע של ה-1 מסומנים ב-X.
- אם 3 נמצא בפינה, שני הקצוות החיצוניים של הטבלה יכולים להיות מלאים, מכיוון שאחרת, החוק דלעיל יופר.
- אם 2 נמצא בפינה, שני קווים צריכים לצאת ולהתרחק מה-2 על הגבול.
חוקים לריבועים עם 3
[עריכת קוד מקור | עריכה]- אם 3 סמוך ל-0 במאונך או במאוזן, על כל הצלעות של ה-3 להיות מלאות חוץ מהצלע הסמוכה ל-0. בנוסף, אפשר למלא את שני הקווים הניצבים ל תאים הסמוכים.
- אם שני '3'-ים סמוכים זה לזה במאונך או במאוזן, הצלע המשותפת שלהם צריכה להיות מלאה, משום שהאפשרות האחרת היחידה היא לולאה סגורה שלא ניתנת לחיבור לאף קו אחר. כמו כן, שני הקווים החיצוניים ל-'3'-ים (מקבילים לצלע המשותפת) חייבים להיות מלאים. בנוסף, הקטע העובר בין ה-'3'-ים תמיד יעטוף אותם בצורת S. לכן, הקו שבין ה-'3'-ים לא יכול להמשיך בקו ישר, והצלעות הממשיכות אותו יכולות להיות מסומנות ב-X.
- אם 3 סמוך ל-0 באלכסון, שתי הצלעות הפוגשות את הפינה הנושקת ל-0 צריכות להיות מלאות. זאת משום שאם אחד משתי הצלעות הללו הייתה פתוחה, לקו שנגמר בפינה של ה-0 לא היה נתיב להמשיך. כלל זה דומה מאוד לכלל של ה-3 בפינה.
- בדומה, אם ל-3 יש פינה עם שני 'X'-ים היוצאים ממנה, אז שתי הצלעות של ה-3 הנפגשות בפינה צריכות להיות מלאות. זאת מכיוון שאם אחת משתי הצלעות הללו הייתה פתוחה, השנייה הייתה צריכה להיות מלאה (משום של-3 יכולה להיות רק צלע פתוחה אחת), וכך תפגוש שלושה 'X'-ים בפינה, דבר שאינו אפשרי משום שמכל נקודה בטבלה יכולים לצאת או שני קווים או שום קו.
- אם קו מגיע לפינה של 3, חייבים להיות קווים בשתי הצלעות של ה-3 שלא סמוכות לפינה זו, משום שאם הצלע הריקה היחידה של ה-3 לא הייתה סמוכה אליהם, היו מחוברים שלושה קווים לפינה. יתר על כן, הקטע המוביל מה-3 החוצה בפינה והפוגש את הקו חייב להיות ריק; אם היה מלא, אף אחת משתי הצלעות הריקות שנשארו ל-3 לא הייתה יכולה להיות עם קו.
אלכסונים של '3'-ים ו-'2'-ים
[עריכת קוד מקור | עריכה]- אם שני '3'-ים סמוכים באלכסון, הצלעות שלא נפגשות בפינה הנושקת לשני ה'3'-ים חייבות להיות מלאות.
- בדומה, אם שני '3'-ים נמצאים באותו האלכסון, ומופרדים על ידי כל מספר של '2'-ים (ורק '2'-ים), על הצלעות החיצוניות של ה'3'-ים להיות מלאות, ממש כאילו היו סמוכים באלכסון.
- אם ישנה סדרה של '2'-ים בקו אלכסוני, ובקצה הסדרה ישנה פינת צלעות מלאות הנפגשת עם ה-'2'-ים, פינות צלעות מלאות תואמות צריכות להיות לאורך כל הסדרה.
- להלן סדרה של '2'-ים המסתיימת ב-3. דוגמה זו משלבת כמה מן הכללים שתוארו לעיל. ליד ה-2 המסיים את הסדרה יש פינת צלעות מלאה הכוללת בתוכה אחת (אך לא שתיים) מהצלעות בפינה החיצונית שלו: הפינה המלאה נמצאת בפינה המרוחקת מפינת ה-3. מכך אפשר להבין שאפשר למלא את שתי הצלעות החיצוניות של ה-3. זאת מכיוון ש: (1) הצלע הימנית שה-2 התחתון חייב להיות ריק, אז (2) הצלע העליונה או השמאלית של ה-2 התחתון צריכה להיות מלאה, ולכן (3) ל-2 האמצעי לא יכולים להיות קווים גם בצלע הימנית וגם בצלע התחתונה שלו (אחרת, שלושה קווים היו נפגשים בפינה הימנית-תחתונה שלו), ולכן (4) חייב להיות קו בצלע העליונה או השמאלית שלו, ולכן (5) הצלע העליונה והצלע השמאלית של ה-3 חייבות להיות מלאות. אפשר ליישם מחרוזת דומה של הסקת מסקנות בכל אלכסון של '2'-ים המסתיים ב-3.
אלכסונים של 3 ו-1
[עריכת קוד מקור | עריכה]- אם 1 ו-3 סמוכים באלכסון ושתי הצלעות החיצוניות של ה-1 מסומנות ב-X, אז שתי הצלעות החיצוניות של ה-3 צריכות להיות מלאות.
- המקרה ההפוך נכון גם הוא: אם שתי הצלעות החיצוניות ל-3 מלאות, אזי ששתי הצלעות החיצוניות ל-1 צריכות להיות מסומנות ב-X.
חוק לתא עם 2
[עריכת קוד מקור | עריכה]אם מסביב ל-2 יש צלע כלשהי המסומנת ב-X, אז קו המגיע לאחת משתי הפינות שאינן סמוכות לצלע עם ה-X לא יכול להתרחק בזווית ישרה מה-2, שהרי כך שני קווים מסביב ל-2 יהיו בלתי אפשריים, ויכול להיות מסומן ב-X. זאת אומרת שהקו המגיע ל-2 חייב להמשיך באחת משתי הצלעות של ה-2. לכן, הקו השני של ה-2 חייב להיות הצלע החופשייה היחיד, בסמוך לקו שסומן במקור ב-X, כך שאפשר למל אותו. לעומת זאת, אם ל-2 יש קו בצלע אחת, וצלע סמוכה המסומנת ב-X, אז הקו השני צריך להיות באחת משתי הצלעות שנשארו, ולצאת מהפינה הנגדית. אם אחת משתי יציאות אלו מסומנות ב-X, אזי הוא צריך לצאת במסלול השני.
חוקים לתאים עם 1
[עריכת קוד מקור | עריכה]- אם קו מגיע לפינה של 1, ואם מתוך שלושת הכיוונים אליהם הקו יכול לפנות, הקו שאינו צלע של ה-1 מסומן ב-X, שתי הצלעות הסמוכות לפינה הנגדית של ה-1 יכולות להיות מסומנות ב-X גם הן.
- כלל זה נכון גם להפך: אם קו מגיע לפינה של 1, ושתי הצלעות הסמוכות לפינה הנגדית של ה-1 מסומנות ב-X, אז מתוך שלושת הכיוונים אליהם הקו יכול לפנות, הקו שאינו צלע של ה-1 יכול להיות מסומן ב-X.
- אם שני '1'-ים סמוכים באלכסון, אז מתוך שמונת הקטעים המקיפים את שני התאים הללו, או ארבעת הקטעים הפנימיים (החולקים נקודת קצה אחת - הנקודה שבין ה-'1'-ים) או ארבעת הקטעים החיצוניים צריכים להיות מסומנים ב-X. אם כן, אם שני קווים חיצוניים או פנימיים לאחד מהקווים מסומנים ב-X, שני הקטעים התואמים (הפנימיים או החיצוניים) של ה-1 השני צריכים להיות מסומנים ב-ס גם הם.
- אם שני '1'-ים סמוכים לאורך קצה הטבלה, הקו שביניהם צריך להיות מסומן ב-X, מכיוון שלא יהיה לו לאן להמשיך מהקצה.
מספר זוגי של קצוות באזור סגור
[עריכת קוד מקור | עריכה]באזור סגור של הסריג (שממנו אין שום מעבר לקווים "לברוח"), לא יכול להיות מספר אי-זוגי של קצוות קטעים לא מחוברים, מאחר שכל קצוות הקטעים חייבים להיות מחוברים למשהו. לעיתים קרובות, כלל זה יפסול אפשרות אחת או יותר שהיו נראות סבירות לולא כלל זה.
משפט עקומת ז'ורדן
[עריכת קוד מקור | עריכה]בחידה קשה במיוחד, אפשר להשתמש במשפט עקומת ז'ורדן, שאומר כי כל עקומה פתוחה המתחילה ומסתיימת מחוץ לעקומה סגורה, חייבת לחצות את העקומה הסגורה מספר זוגי של פעמים. באופן פרטני יותר, זאת אומרת שבכל שורה בטבלה צריך להיות מספר זוגי של קווים אנכיים ובכל טור בטבלה צריך להיות מספר זוגי של קווים אופקיים. כאשר רק קו פוטנציאלי אחד בשתי הקבוצות הללו לא ידוע, אפשר לקבוע האם הוא חלק מן הלולאה על פי משפט זה.
שיטה פשוטה לשימוש במשפט זה היא להשחיר את השטחים החיצוניים והפנימיים. כאשר רואים שני תאים חיצוניים או שני תאים פנימיים סמוכים זה לזה, אפשר לדעת שלא עובר קו ביניהם. המקרה ההפוך נכון גם כן: אם ידוע שלא עובר קו בין שני תאים, אזי ששני התאים הללו יהיו באותו ה"צבע" (שניהם בפנים או ששניהם בחוץ). בדומה, אם תא חיצוני ותא פנימי סמוכים, חייב לעבור קו ביניהם.
היסטוריה
[עריכת קוד מקור | עריכה]סלית'רלינק היא חידה מקורית של ניקולי. היא הופיעה לראשונה בכתב העת Puzzle Communication Nikoli גיליון מספר 26 (יוני 1989). העורך שילב שתי חידות שהופיעו שם. בהתחלה, בכל ריבוע היה מספר.
משחקי וידאו
[עריכת קוד מקור | עריכה]משחקי וידאו של סלית'רלינק יצאו ל-נינטנדו DS, כאשר הדסון סופט שחררו את סדרת חידות חלק 5: סלית'רלינק (Puzzle Series Vol. 5: Slitherlin) ביפן, בתאריך 16 בנובמבר 2006, ואגטק (Agetec) עם סלית'רלינק בהידור של ניקולי, Brain Buster Puzzle Pak, ששוחרר בצפון אמריקה, בתאריך 17 ביוני 2007.[1]
ראו גם
[עריכת קוד מקור | עריכה]קישורים חיצוניים
[עריכת קוד מקור | עריכה]
- הדף של ניקולי באנגלית על סלית'רלינק
- On the NP-completeness of the Slitherlink Puzzle סלית'רלינק היא NP-שלמה
- אתר הדן בצורות שונות של תבניות סלית'רלינק שאינן טבלה מלבנית
- KwontomLoop -אתר חינמי עם חידות סלית'רלינק יומיות ברמות שונות. כולל בנוסף מערכת ניקוד להשוואה עם שחקנים אחרים.
- www.conceptispuzzles.com - אתר המראה שיטות פתרון מתקדמות.
- games.softpedia.com - סלית'רלינק להורדה המספק חידות ברמות שונות. כמו כן אפשר להעלות חידה לאתר על מנת לפתור אותה.
- krazydad.com הורדת מספר גדול של חידות סלית'רלינק הניתנות להדפסה.
- chaos.co.za מערכת סימנים המוצעים לפתרון סלית'רלינק