היאוקה

הֶיָאוּאַקֵה (ביפנית: へやわけ, "חדרים מחולקים") היא סוג של חידת היגיון שפורסמה על ידי ההוצאה לאור ניקולי. נכון ל-2011, ארבעה ספרים המכילים חידות היאוקה בלבד פורסמו על ידי ניקולי. החידה הופיעה לראשונה ב-Puzzle Communication Nikoli מספר 39 (ספטמבר 1992).

חוקים

טבלת היאוקה לא פתורה

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

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

החוקים הבאים קובעים אילו תאים שחורים ואילו לבנים:

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

שיטות פתרון

טבלת היאוקה פתורה

שני הכללים הראשונים חלים גם (לדוגמה) בחידות היטורי, ולפיכך, שתי החידות הללו חולקות כמה שיטות לפתרון:

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

חידות מורכבות יותר דורשות צירוף של כלל 1 עם כלל 2 על מנת להתקדם ללא ניחושים; המפתח הוא לזהות בשילוב שני הכללים מתי התאים חייבים ליצור שתי וערב ואחת משתי האפשרויות (של השתי וערב) תיצור לולאה או מחסום סגור.

שאר הכללים מייחדים את היאוקה ממשפחת החידות אליה הוא שייך:

• כלל 5 הוא הכלל המנחה בחידה; צריך להציב תאים שחורים על מנת למנוע כל קו לבן (מאונך או מאוזן) החוצה שני גבולות של חדרים (או יותר).
• חדרים ממוספרים מהווים בדרך כלל נקודת פתיחה, בתוך מסקנות אחרות. המסקנות הבאות הן הדוגמאות הפשוטות ביותר לחדרים המוגדרים בהתחלה:
  • בחדר של 2X2 בפינת הטבלה הכולל '2' בתוכו, התא הפינתי (של הטבלה כולה) חייב להיות צבוע, וכן התא בחדרו הנמצא באלכסון ממנו. מכיוון שתאים שחורים לא יכולים לחלוק צלע (כלל 1), האלטרנטיבה היחידה היא לנתק את התא הלבן הפינתי באלכסון שחור, בסתירה לכלל 2.
  • בחדר של 2X3 עם הצלע בגודל 3 התאים לאורך גבול הטבלה הכולל '3' בתוכו, התא המרכזי בשורת 3 התאים הצמודה לגבול הטבלה חייב להיות צבוע, וכן שני התאים בחדרו הנמצאים באלכסון אליו (מאותן הסיבות לכלל לעיל).
  • בחדר של 1X3 הכולל '2', שני התאים בקצה החדר חייבים להיות צבועים; אם התא המרכזי היה צבוע, כלל 1 היה נפגע. בכלליות, בחדר של (1X(2n-1 המכיל בתוכו את המספר n, כל תא שני (כאשר תחילת הספירה היא באחד מן הקצוות) חייב להיות צבוע.
  • בחדר של 3X3 הכולל '5', חייבת צורה של שתי וערב, כאשר התאים בכל הפינות צבועים, וכן התא במרכז.

סיבוכיות חישובית

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

ראו גם

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