גשרים
גשרים (ביפנית: 橋をかけろ האשי או קאקרו, מילולית: "בנו גשרים!") היא סוג של חידה שפורסמה על ידי ההוצאה לאור ניקולי. החידה פורסמה גם באנגלית בשם Bridges (גשרים) או Chopsticks (מקלות אכילה) (השמות הגיעו משיבוש: האשי שנכתב 橋, פירושו גשר; והאשי שנכתב 箸, פירושו מקלות אכילה). החידה הופיעה גם בטיימס בשם האשי. בצרפת, דנמרק, הולנד, ובלגיה החידה מפורסמת בשם Ai-Ki-Ai.
חוקים
[עריכת קוד מקור | עריכה]החידה כוללת תאים מפוזרים, בדרך כלל בצורת עיגול, שבתוכם מספר בין 1 ל-8 ("איים"). על הפותר לחבר אותם בקווים ("גשרים") על פי הכללים הבאים:
- המספר הכתוב בעיגול מציין את מספר הגשרים שנמתחים מהאי.
- אסור לגשרים לחצות גשרים אחרים או איים.
- הגשרים יכולים להיות מוצבים אך ורק במאונך או במאוזן.
- בין כל זוג איים יכולים לחבר עד שני גשרים.
- על הגשרים לחבר בין כל האיים (כלומר, שיהיה אפשר להגיע מכל אי לכל אי).
שיטות פתרון
[עריכת קוד מקור | עריכה]פתירת גשרים מתבצעת באופן מאוד שיטתי: לאחר שמחליטים שבמקום מסוים חייב להיות גשר, הצבת הגשר במקום זה תשלול אפשרויות אחרות להצבת גשרים במקומות שונים, וכך תגרור הצבת גשרים נוספים וכן הלאה.
אחד מהשיקולים המרכזיים הוא סימון גשרים שחייבים להיות בכל מקרה. לדוגמה, אם יש אי עם המספר 3 שניתן לחבר לשני איים בלבד, אז לכל אחד מהם ניתן להעביר גשר, מאחר שלכל אחד מהם יהיה לפחות גשר אחד. שיקול דומה לגבי 5 ושלושה איים או 7 וארבעה איים; כמו כן, אי של 2 שאפשר לחבר רק לאי אחד מחייב העברת שני גשרים אליו, ובדומה 4 שמחובר לשניים, 6 שמחובר לשלושה או 8 לארבעה. שיקולים כאלה יכולים לעבוד גם אם מהאי כבר הועברו גשרים, בהפחתת הגשרים שהועברו; לדוגמה, אי עם המספר 4, שחובר בגשר אחד לאי שמסומן ב-1 וניתן לחבר אותו לעוד שני איים, ניתן להעביר לכל אחד מהם גשר אחד, בדומה למה שהוסבר קודם.
שיקול חשוב נוסף הוא חיבור כל האיים: בגלל כלל זה, ניתן לפסול כל חיבור היוצר קבוצה סגורה, שאינה כוללת את כל האיים. לדוגמה, אם יש שני איים ניתנים לחיבור עם המספר 2, ניתן לדעת שכל אחד מהם מתחבר בלפחות גשר אחד לאי אחר, כי אחרת הם יתחברו זה לזה בשני גשרים ויהוו קבוצה סגורה שלא מקושרת לשאר האיים. מקובל לסמן איים שכל הגשרים שהם מכילים כבר הועברו.
ישנה אפשרות לפתרון החידה בעזרת תכנות ליניארי בדוגמאות ה-MathProg הנמצאות ב-GLPK.
היסטוריה
[עריכת קוד מקור | עריכה]החידה הופיעה לראשונה בכתב העת Puzzle Communication Nikoli בגיליון מספר 31 (ספטמבר 1990), אף על פי שגרסה מוקדמת יותר של החידה הופיעה כבר בגיליון 28 (דצמבר 1989).
