סודוקו שיטות פתרון

שלב ראשון

שיטת הפתרון המומלצת היא חיפוש של מספרים החסרים באזורים (אזור=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.

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

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

 

חזרה למשחק סודוקו