מאסיו

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה לניווט קפיצה לחיפוש
טבלת מאסיו לא פתורה

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

חוקים[עריכת קוד מקור | עריכה]

טבלת מאסיו פתורה

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

לשני סוגי העיגולים (המלא והריק) יש דרישות שונות לאיך הלולאה צריכה לעבור דרכם:

  • ללולאה אסור לפנות בתוך תא עם עיגול לבן, אך חייבת לפנות בתא שלפני ו\או בתא שאחרי עיגול לבן.
  • הלולאה חייבת לפנות בתוך תא עם עיגול שחור, אך אסור ללולאה לפנות בתא שלפני ובתא שאחרי תא עם עיגול שחור.

גרסאות[עריכת קוד מקור | עריכה]

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

היסטוריה[עריכת קוד מקור | עריכה]

הגרסה המוקדמת של החידה הופיעה לראשונה בכתב העת Puzzle Communication Nikoli גיליון מספר 84, תחת השם שינג'ו נו קוביקזארי (真珠の首飾り, "שרשרת פנינים"). בחידה זו היו רק עיגולים לבנים. העיגולים השחורים נוספו רק בגיליון מספר 90, ושמה של החידה שונה לשירושינג'ו קורושינג'ו (白真珠黒真珠, "פנינים לבנות ופנינים שחורות"). השיפור הזה הפך את המשחק למתוחכם יותר וגרם לו לקבל את הפופולריות בה הוא זוכה. השם מאסיו, שבמקור הגיע מקריאה לא נכונה של נשיא ניקולי את המילה 真珠 (שינג'ו) בקאנג'י, ושכנראה הפך לבדיחה פנימית במשרדי ניקולי, אומץ בגיליון מספר 103 של Puzzle Communication Nikoli כדי להחליף את השם הישן והארוך.

שיטות פתרון[עריכת קוד מקור | עריכה]

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

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

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

כמו חידות היגיון וקומבינטוריקה רבות אחרות, מאסיו יכולה להיות קשה מאוד לפתרון; פתרון של חידה זו על טבלה בגודל שרירותי היא בעיה NP-שלמה.[1] בכל מקרה, חידות שפורסמו בדרך כלל נבנו בצורה כזו שיהיה אפשר לפתור אותן בפרק זמן סביר.

ראו גם[עריכת קוד מקור | עריכה]

קישורים חיצוניים[עריכת קוד מקור | עריכה]

ויקישיתוף מדיה וקבצים בנושא מאסיו בוויקישיתוף

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ Erich Friedman. "Pearl Puzzles are NP-Complete". In preparation. 2002. [1].