סודוקו

סודוקו (ביפנית: 数独, משמעותו "מספר יחיד") הוא תשבץ שבה מניחים ספרות על לוח משובץ, בדרך כלל 9×9. הלוח מורכב מתשעה מצולעים (בלוקים), בדרך כלל ריבועים של 3×3 תאים. המטרה היא למלא את התאים הריקים בספרות 1, 9 כך שבכל שורה, בכל טור ובכל בלוק כל ספרה תופיע בדיוק פעם אחת. בחלק מהתאים יש נתונים מראש, ויש להתחשב בהם.

הרעיון נובע מריבועים לטיניים שחקר לאונרד אוילר במאה ה-18. גרסה מבוססת הופיעה כבר ב־1895 בצרפת. הגרסה המודרנית הופיעה ב-1979 והומצאה על ידי הווארד גארנס, שלא תבע זכויות על ההמצאה. ביפן הופיע משחק עם הכלל הנוסף ב-1984, ושמו צומצם ל"סודוקו". ניו זילנדי בשם ויין גולד פיתח תוכנית מחשב ליצירת תשבצים, והתחיל לספקם ל-The Times ב-2004. סודוקו הפך לפופולרי בעיתונים ברחבי העולם, ובישראל החל להתפרסם בקביעות ב-2005.

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

שלב ראשון: מחפשים איפה חסרה ספרה בבלוק ומוציאים מיקומים שאי אפשר לשים בהם את הספרה. זה אלימינציה פשוטה.

שלב שני: לאחר שממלאים וודאיים, מסמנים מועמדים עבור תאים אחרים. אם בלוק, שורה או טור נותרו עם מעט תאים ריקים, מושווים המועמדים ונפתרים תאים נוספים.

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

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

אליפות העולם הראשונה התקיימה במרץ 2006 בלוקה, איטליה. זכתה יאנה טיילובה. תומאס סניידר הגיע למקומות הראשונים בשנים הבאות.

הנפוץ ביותר הוא 9×9, אבל קיימים לוחות קטנים יותר וגדולים יותר. יש חידות עם בלוקים בצורות שונות. לוחות קטנים לילדים נקראים "סובדוקו" (Sub Doku). לוחות גדולים מכונים "סופרדוקו" (Super Doku).

פתרון סודוקו הוא ריבוע לטיני עם אילוץ נוסף של הבלוקים. מספר האפשרויות עבור סודוקו 9×9 הוא 6,670,903,752,021,072,936,960. ניתן להראות שגם לאחר פעולות סימטריה רבות נשארים מספרים מוגדרים של פתרונות שונים. המספר המינימלי של נתונים שנותנים פתרון יחיד הוא 17, הוכחה זו הושלמה ב-2012. כמו כן יש גבול עליון למספר נתונים שניתן לתת בלי לקבוע פתרון יחיד, גודל הלוח פחות 4.

סודוקו הוא חידת מספרים על לוח משובץ. הלוח הרגיל הוא 9×9. הלוח מתחלק לתשעה תיבות של 3×3. תיבה = בלוק = תיבה של תשע משבצות.

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

התחלות היסטוריות קצרות: הרעיון קרוב לרעיונות של המתמטיקאי אוילר. גרסה מודרנית הופיעה ב-1979. ביפן קיבלה את השם "סודוקו" ב-1984. ויין גולד עשה תוכנה שיצרה תשבצים, והיא יצאה בעיתון The Times ב-2004. גם בישראל התחילו לפרסם סודוקו בקביעות ב-2005.

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

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

עובדה מעניינת: יש מספר עצום של פתרונות לסודוקו 9×9, 6,670,903,752,021,072,936,960 פתרונות. המספר הקטן ביותר של נתונים שמבטיח פתרון יחיד הוא 17.