סודוקו

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

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

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

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

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

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

היסטוריה

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

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

גרסה ראשונה למשחק הסודוקו, הופיעה ב־6 ביולי 1895 בעיתון הצרפתי La France‏[1]. המשחק במתכונתו הנוכחית הופיע לראשונה ב-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, כך שבכל טור, בכל שורה, ובכל תיבה, יופיעו כל הסמלים.

שיטות פתרון

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

שלב ראשון

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

שלב שני

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

שלב שלישי

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

שגיאה ביצירת תמונה ממוזערת: קובץ חסר

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

פתרון ממוחשב

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

נוסחים שונים

סודוקו מצולעים בעל סימטריה חלקית

היפר סודוקו

סוק"ק

סודוקו סמוראי

סודוקו תלת ממדי - 3D

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

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

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

סודוקו אלכסונים

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

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

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

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

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

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

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

ראו גם

• עגולוקו

לקריאה נוספת

• קרול וורדרמן, סודוקו המדריך המקיף, הוצאת יבנה, 2006

• Taking Sudoku Seriously, Jason Rosenhouse and Laura Taalman, Oxford Univ Press, 2011.

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

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

הערות שוליים

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

25851149סודוקו