סודוקו

היסטוריה

במאה ה-18 חקר המתמטיקאי השווייצרי לאונרד אוילר ריבועים שבהם תוכן המשבצות שונה בכל שורה ובכל עמודה. הוא קרא לריבועים האלה ריבועי קסם, אך מכיוון שאוילר מילא את משבצות הריבועים באותיות לטיניות, מכנים אותם גם בשם ריבועים לטיניים. משחק המבוסס על ריבועים לטיניים זה הופיע לראשונה בעיתון ניו יורקי בשם "Math Puzzles and Logic Problems" ("תשבצים מתמטיים ובעיות היגיון") בשנות ה-70 של המאה ה-20.
גרסה ראשונה למשחק הסודוקו, הופיעה ב־6 ביולי 1895 בעיתון הצרפתי La France‏. המשחק במתכונתו הנוכחית הופיע לראשונה ב-1979 באחד המגזינים של דל (Dell). גרסה זו הומצאה על ידי הווארד גארנס (Howard Garns), ארכיטקט אמריקאי בן 74 שפרש לגמלאות. גארנס לא רשם פטנט או תבע זכויות יוצרים, ובעקבות כך-הסודוקו הפך לפטנט ברישיון חופשי ללא צורך בתמלוגים. 
משחק הסודוקו, שבו נדרש המילוי לקיים עוד תנאי נוסף, הופיע בראשונה ביפן בשנת 1984 ונקרא: "סואוז'י ווא דוקושין ני קאגירו" (数字は独身に限る) שמשמעו - "מוגבל למספר יחיד"(=היותו בלתי נשוי)". בהמשך קוצר השם ל"סודוקו", שמשמעו ביפנית (נוסף על היותו ראשי תיבות של הביטוי לעיל) "מספר יחיד" (数独).
ניו זילנדי בשם ויין גולד, בעברו שופט בהונג קונג, פיתח תוכנית מחשב המייצרת תשבצים אלה, ובשנת 2004 החל לספקם לעיתון "הטיימס" הבריטי, אשר החל במדור יומי קבוע בעיתון.
כיום החידות מפורסמות ביפן ובבריטניה גם בעיתונים יומיים, וכן בעיתון ה-"New York Post" בניו יורק. גם העיתונים האוסטרליים "האוסטרליאן" וה"סידני מורנינג הרלד" החלו בפרסום מדורים קבועים.
בשנת 2005 גם עיתונים ישראלים החלו לפרסם סודוקו על בסיס קבוע. בישראל פורסם סודוקו בירחון התשבצים "ניקוי ראש ענק", עוד לפני שפשטה האופנה בעיתונים, תחת השם "תשע ברבוע". בירחון זה פורסמו גם שעשועוני קאקורו תחת השם "מספרים וסיכומים".

תחרויות

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

הוראות המשחק

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

שלב ראשון

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

שלב שני

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

שלב שלישי

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

פתרון ממוחשב

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

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

פתרון סודוקו תקף הוא גם ריבוע לטיני, תחום אשר נחקר רבות. קיימות הרבה פחות אפשרויות לסודוקו מאשר ריבועים לטיניים, משום שפתרון סודוקו דורש אילוץ נוסף, אזורי (הבלוקים). מספר האפשרויות לסודוקו של 9X9 הוא 6,670,903,752,021,072,936,960.

מספר זה שווה ל  כאשר המספר האחרון הוא ראשוני. תוצאה זו חושבה בשיטות קומבינטוריות שנעזרו בחישוב "כוח גס" באמצעות מחשב.
על אוסף הפתרונות פועלת מכפלה (לא ישרה) של החבורות  (שינוי הספרות),  (שינוי סדר השורות או העמודות בכל בלוק, וערבוב הבלוקים) ו- (סימטריות של הריבוע). מספר מחלקות השקילות ביחס לפעולה הזו, הוא 5,472,730,538. זהו, אם כך, מספר הפתרונות השונים עקרונית זה מזה.
המספר המקסימלי של נתונים שניתן לספק מבלי שהפתרון יקבע ביחידות הוא גודל הלוח עצמו פחות 4. למשל: אם חסרים שני מספרים בתאים שהם פינות של מלבנים מאונכים, אזי קיימות שתי דרכים לשבצם. 
המספר המינימלי של נתונים שיש לספק על מנת שהפתרון יקבע ביחידות עדיין לא ידוע. הדוגמאות הידועות עם מספר הנתונים הקטן ביותר הן עם 17 נתונים.

אלגוריתמים וסיבוכיות

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