סודוקו

דוגמה לסודוקו

סוּדוֹקוּ (יפנית: 数独, ‏האזנה^ⓘ‏^?‏) הוא חידה שבה יש למקם ספרות על לוח משובץ שגודלו (לרוב) 9×9, המורכב מ-9 תיבות של 3×3. מטרת המשחק - למקם את 9 הסמלים (לרוב הספרות 1 עד 9) על גבי לוח המשחק כך שבכל טור, בכל שורה, ובכל תיבה, יופיע כל סמל בדיוק פעם אחת.

בלוח המשחק נתונים כמה סמלים, ויש להתייחס אליהם בעת מיקום הסמלים במהלך המשחק.

החידה הפכה פופולרית ביפן בשנת 1986 ובבריטניה, בקנדה ובישראל בשנת 2005 בעקבות קידומה בעיתונות.

היסטוריה

במאה ה-18 חקר המתמטיקאי השווייצרי לאונרד אוילר ריבועים שבהם תוכן המשבצות שונה בכל שורה ובכל עמודה. הוא קרא לריבועים האלה ריבועי קסם, אך מכיוון שאוילר מילא את משבצות הריבועים באותיות לטיניות, מכנים אותם גם בשם ריבועים לטיניים. משחק המבוסס על ריבועים לטיניים זה הופיע לראשונה בעיתון ניו יורקי בשם "Math Puzzles and Logic Problems" ("תשבצים מתמטיים ובעיות היגיון") בשנות ה-70 של המאה ה-20.

משחק הסודוקו, שבו נדרש המילוי לקיים עוד תנאי נוסף, הופיע בראשונה ביפן בשנת 1984 ונקרא: "סואוז'י ווא דוקושין ני קאגירו" (数字は独身に限る) שמשמעו - "מוגבל למספר יחיד"(=היותו בלתי נשוי)" בהמשך קוצר השם ל"סודוקו", שמשמעו ביפנית (נוסף על היותו ראשי תיבות של הביטוי לעיל) "מספר יחיד" (数独).

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

כיום החידות מפורסמות ביפן ובבריטניה גם בעיתונים יומיים, וכן בעיתון ה-"New York Post" בניו יורק. גם העיתונים האוסטרליים "האוסטרליאן" וה"סידני מורנינג הרלד" החלו בפרסום מדורים קבועים.

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

במרס 2006, בעיר לוקה (Lucca), באיטליה, התקיימה אליפות העולם הראשונה לפתרון סודוקו. המשתתפים היו בני כל הגילים מגיל 15 (המשתתף מגרמניה) ועד גיל 61 (המשתתף מאיטליה). באליפות השתתפו 85 איש מ-22 מדינות. כלכלנית ורואת חשבון צ'כית בת 31 בשם יאנה טיילובה (Jana Tylova) מהעיר מוסט (Most) זכתה באליפות; היא הקדימה בדירוג את תומאס סניידר, בוגר אוניברסיטת הרווארד בן 26, שסיים במקום השני, ואת וויי-הא-הואן בן 30, מהנדס תוכנה בגוגל, קליפורניה, שסיים במקום השלישי. את הגביע העניק למנצחת השופט ויין גולד. אליפות העולם השנייה התקיימה במרס 2007 בפראג, והפעם זכה תומאס סניידר (Thomas Snyder, שסיים במקום השני ב-2006). אליפות העולם השלישית התקיימה באפריל 2008 בגואה, ושוב זכה תומאס סניידר.

הוראות המשחק

המשחק מתבצע על טבלה של 9×9 תאים, המסודרים בתשע תיבות של 3×3 תאים. בחלק מהתאים נמצאים סמלים, ויש להשלים ולמלא את התאים הריקים בסמלים 1-9, כך שבכל טור, בכל שורה, ובכל תיבה, יופיעו כל הסמלים.

שיטות פתרון

שלב ראשון

שיטת הפתרון המומלצת היא חיפוש של מספרים החסרים באזורים (אזור=3X3 ריבועים) והשלמתם לפי המיקום האפשרי באזור. כמו בדוגמה המוצגת - חיפוש היכן אפשר להציב את המספר 7 באזור השמאלי העליון. זוהי בעצם אלימינציה של המיקומים שבהם המספר לא יוכל להשתבץ.

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

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

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

שלב שני

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

שלב שלישי

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

פתרון ממוחשב

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

נוסחים שונים

משחק של 9×9 הינו הנפוץ ביותר אולם אפשריות גם חידות של 4 אזורים של 2×2, וכן חידות של 4 אזורים של 5×5. נוסח קשה במיוחד הוא של 16×16 משבצות עם 16 אזורים, של 4×4. קיימות גם חידות פחות סימטריות של 6 אזורים של 2×3.

כמו כן קיימת גרסאות מתקדמות יותר של הסודוקו:

• סודוקו X, בו גם שני האלכסונים הראשיים מכילים את הספרות 1 עד 9.
• סאמוראי סודוקו, שהוא שילוב של מספר לוחות סודוקו, המחוברים ביניהם.
• קילר סודוקו, מעין שילוב של סודוקו וקאקורו. מכיל "כלובים" עם מספרים, כאשר כל מספר מציין את סכום הספרות הנמצאות באותו כלוב. נחשב על ידי רבים לגרסה המאתגרת ביותר של הסודוקו.

סודוקו ומתמטיקה

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

את הלוח (גריד) ניתן לייצג כגרף דו-ממדי שבו כל קודקוד מתואר באמצעות זוג סדור $(x,\,y)$, כאשר x ו y הם מספרים שלמים שנעים בין 1 ל 9 (כולל). נאמר ששני קודקודים $(x,\,y)$ ו $(x',\,y')$ הם מתואמים אם מתקיים אחד מהבאים:

• $x=x'\,$ or , כלומר: הם באותו טור.
• $y=y'\,$ or, כלומר: הם באותה שורה.
• $\lceil x/3\rceil =\lceil x'/3\rceil$ and $\lceil y/3\rceil =\lceil y'/3\rceil$, כלומר: הם באותו הבלוק.

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

פתרון סודוקו תקף הוא גם ריבוע לטיני. ישנם הרבה פחות פתרונות סודוקו מאשר ריבועים לטיניים, משום שפתרון סודוקו דורש אילוץ נוסף, אזורי (הבלוקים). למרות זאת, מתמטיקאים הצליחו לחשב את מספר הפתרונות לסודוקו של 9X9. בשנת 2005 מצא ברטרם פלגנהאור (Bertram Felgenhauer) שמספר הפתרונות לסודוקו 9X9 הוא 6,670,903,752,021,072,936,960. [1] מספר זה שווה ל $\ 9!\times 72^{2}\times 2^{7}\times 27,704,267,971$ כאשר המספר האחרון הוא ראשוני. תוצאה זו חושבה בשיטות קומבינטוריות שנעזרו בחישוב "כוח גס" באמצעות מחשב. התוצאה התקבלה בניתוח שערך פרייזר יארוויס (Frazer Jarvis) ואושרה על ידי אד ראסל (Ed Russell).

המספר המקסימלי של נתונים שניתן לספק מבלי שהפתרון יקבע ביחידות הוא גודל הלוח עצמו פחות 4. למשל: אם חסרים שני מספרים בתאים שהם פינות של מלבנים מאונכים, אזי קיימות שתי דרכים לשבצם. המספר המינימלי של נתונים שיש לספק על מנת שהפתרון יקבע ביחידות הוא עדיין בגדר בעיה בלתי פתורה, למרות שעבור ואריאציות מסוימות נמצאו פתרונות (עבור הואריאציה הסטנדרטית ללא אילוצי סימטריה, התשובה היא 17, עם אילוצי סימטריה סיבובית התשובה היא 18. תשובה זו נמצאה על ידי חובבי חידות יפניים [2]).

עגולוקו

דוגמה לעגולוקו

עגולוקו הינו סוג של חידת סודוקו. העגולוקו מבוסס על אותו עיקרון של הסודוקו - שיבוץ של כל הספרות מ-1 עד 9.
הביטו בתמונה: העיגול מחולק לשמונה "משולשי פיצה", ארבעה מעגלים ועיגול אמצעי המכיל ספרה אחת. כל 2 פיצות שכנות או כל מעגל, בשיתוף הספרה שבעיגול האמצע, צריכים להכיל את הספרות 1-9. שימו לב, ספרת האמצע תופיע פעם אחת בכל החידה, וכל מספר אחר יופיע 4 פעמים.

איך מכינים עגולוקו?

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

• ברמה הכי קשה צריך לשבץ לפחות 11 ספרות.
• השיבוץ יכול להיות בכל אחת מן המשבצות - כך שיש אפשרות לא לשבץ מלכתחילה את משבצת האמצע.

ראו גם

• קאקורו
• ריבוע קסם
• חידתו

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

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