סודוקו

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

הפתרון לאותו סודוקו

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

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

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

יש חוקרים המייחסים לפתרון תשבצי סודוקו סגולות של שיפור או שימור כישורים שכליים^[1].

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

חידה הקרובה לסודוקו המודרני שהתפרסמה ב-6 ביולי 1895 בעיתון La France

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

גרסה ראשונה למשחק הסודוקו הופיעה ב־6 ביולי 1895 בעיתון הצרפתי La France^[2]. המשחק במתכונתו הנוכחית הופיע לראשונה ב-1979 באחד המגזינים של דל מגזינס (Dell Magazines). גרסה זו הומצאה על ידי הווארד גארנס (Howard Garns), ארכיטקט אמריקאי בן 74 שפרש לגמלאות. גארנס לא רשם פטנט או תבע זכויות יוצרים, ובעקבות כך הסודוקו הפך להמצאה ברישיון חופשי ללא צורך בתמלוגים.

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

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

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

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

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

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

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

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

שלב ראשון[עריכת קוד מקור | עריכה]

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

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

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

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

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

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

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

בעיית פתירת הסודוקו ללוח בגודל משתנה ( $n^{2}$ שורות ועמודות ובלוקים בגודל $n\times n$ ) ידועה כבעיה NP-שלמה.

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

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

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

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

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

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

סודוקו מצולעים, שבו חלק מהמצולעים בני 9 המשבצות אינם ריבועים. המצולעים יכולים להיות בעלי צורה ומיקום סימטריים, אך אין זה הכרחי.
סודוקו מצולעים עם סיכומים בצד - סודוקו מצולעים, שעל שולי התשבץ מובאים סיכומי הספרות של חלק השורה או הטור עד לקו המעובה הקרוב. למעשה זה סוג נוסף של סוק"ק, סודוקו עם אלמנטים של קאקורו.
סודוקו סיני, בדומה לסודוקו מצולעים, במקום מתחם מרובע או מצולע של 9 משבצות, יש בו רצף של 9 משבצות מחוברות בקו^[3].
סודוקו סקוטי, שבו מסומנים אלכסונים, אך לא האלכסונים הארוכים ביותר. הספרות, המוצבות במשבצות המרכיבות אלכסון כלשהו, אינן יכולות לחזור על עצמן.
סודוקו אלכסונים, שבו גם שני האלכסונים הראשיים מכילים את הספרות 1 עד 9.
סודוקו מצולעים עם אלכסונים - שילוב של סודוקו מצולעים עם סודוקו אלכסונים.
סודוקו חלונות, שבו, בנוסף לתשעת הריבועים הכוללים 9 משבצות כל אחד, יש תיחומים נוספים בני 9 משבצות, אחד או יותר, הנבדלים באמצעות צבע הרקע שלהם החופפים חלקית עם מתחמי המשנה האחרים. סוג פופולרי במיוחד של סודוקו חלונות הוא היפר סודוקו המכיל ארבעה חלונות מרובעים.
סודוקו אפור לבן, שבו מבדילים באמצעות שינוי הרקע של המשבצות בין המשבצות המיועדות לספרות זוגיות ובין המשבצות המיועדות לספרות לא זוגיות. באותה צורה אפשר להבדיל בין מספרים קטנים ובין מספרים גדולים יותר^[4].
סודוקו תאומים סיאמיים הוא שילוב של שני לוחות סודוקו בעלי מקטע משותף, בדומה לחלקי הגוף המשותפים אצל תאומים סיאמיים. החלק המשותף יכול לנוע מתשע משבצות ועד 54 משבצות. ישנם גם חיבורים של שלושה לוחות סודוקו היוצרים שלישייה, ארבעה לוחות, חמישה לוחות ויותר. החיבור יכול להיות גם של שורה משותפת או טור משותף.
סודוקו סמוראי, שהוא שילוב של חמישה לוחות סודוקו, המחוברים ביניהם. השם נגזר מהדמיון החזותי של התשבץ לציור של סמוראי לבוש בקימונו.
סודוקו שכנים, שבו יש סימון על שכנותן של ספרות עוקבות. לכל ספרה, פרט לספרות 1 ו-9 יכולות להיות שתי ספרות עוקבות, האחת קטנה יותר והשנייה גדולה יותר. לספרה 1 יש שכנות רק עם הספרה 2 ולספרה 9 יש שכנות רק עם הספרה 8.
סודוקו ללא שכנים, עוד וריאנט העוסקת בציר המספרים - בווריאנט זה לא יוצבו במשבצות שכנות, במאוזן או במאונך, מספרים עוקבים על ציר המספרים.
סודוקו עם חשבון פנימי הוא סודוקו רגיל, אך הספרות המוצבות על הלוח הן סיכום או הפרש של שתי הספרות השכנות, מימין ומשמאל או למטה ומלמעלה.
סודוקו השוואתי, שבו יש סימון ליחסי גודל בין ספרות המוצבות במשבצות שכנות - גדול או קטן באחד משכנו.
סוק"ק, מעין שילוב של סודוקו וקאקורו. מכיל "כלובים" עם מספרים, כאשר כל מספר מציין את סכום הספרות הנמצאות באותו כלוב. נחשב על ידי רבים לגרסה המאתגרת ביותר של הסודוקו. גם סודוקו מצולעים עם סיכומים בצד (ראו לעיל) הוא סוג של סוק"ק.
סוק"ק אלכסונים, שהוא וריאציה של סוק"ק ובה במקום הכלובים המסוכמים ניתנים סיכומי האלכסונים של אלכסוני הריבועים הפריפריאליים.
אדוקו, שמכונה גם סך סודוקו, שהוא וריאציה אחרת של סוק"ק ובה ניתנים רק סיכומי הכלובים ואין אף ספרה מוצבת.

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

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

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

על אוסף הפתרונות פועלת מכפלה (לא ישרה) של החבורות $\ S_{9}$ (תמורה של הספרות), $\ (S_{3}\cdot (S_{3})^{3})^{2}$ (שינוי סדר השורות או העמודות בכל בלוק, וערבוב הבלוקים) ו- $\ D_{4}$ (סימטריות של הריבוע)^[6]. מספר מחלקות השקילות ביחס לפעולה הזו, הוא 5,472,730,538. זהו, אם כך, מספר הפתרונות השונים עקרונית זה מזה.

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