לצורך ההבנה, נגדיר את לוח הסודוקו כלוח המורכב מ-9 בלוקים. כלומר בלוק זה המטריצה בגודל 3*3 בה אתה צריך לשבץ את המספרים 1-9.כעת אני טוען שברור שבמידה ושיבצתי את המספר 1 בבלוק כלשהו אז אני לא ארצה לשבץ אותו שוב. כיביכול זאת דרישה סבירה. אין שום טעם שאני אשבץ אותו אם כבר אני יודע ששיבצתי אותו. יחד עם זאת, זה כנראה לא כזה פשוט כי מבחינת קוד נורא נוח לתת רקורסיה בסגנון:
foo(int[][] ar , int i , int j) {
// תנאי עצירה כלשהו
for (int k=1; k<10; ++k) {
ar[i][j] = k;
if (checkBoard(ar))
תצא מהלולאה ותתקדם ברקורסיה
}
בפועל זה דיי רע.
תאר לעצמך אנחנו בבלוק הכי ימיני למטה במטריצה ונניח שיש בו כבר את המספר 1. אז כל פעם שאנחנו ממלאים שם תא, אנחנו ממלאים אותו ב-1 ואז שולחים לבדיקת תקינות הלוח שככל הנראה תרוץ על כל הלוח עד שהיא תמצא שכבר בבלוק הזה משובץ המספר.
BFS ו-DFS אם ימומשו בצורה טובה, ישתמשו בסימונים מסויימים (בגרפים משתמשים בצבעים) כדי להימנע מלקיחת אפשרויות טריוויאליות.
למשל - רקורסיה נבונה תרוץ לפי בלוקים כאשר אנחנו נדאג לסמן את המספרים שכבר שיבצנו בתאים. ככה נימנע משליחת אפשרויות טריוויאליות לפונקציה מסיבית. תנסה להכליל את זה גם לשורות וטורים ותעיף ככה הרבה שיבוצים לא טובים. בגלל זה אולי החשיבה על זה כגרף עוזרת.
בכל מקרה, עדיין מדובר בפתרונות לא מספיק טובים (ואין מה לעשות, בעייה קשה - צריך פתרון יצירתי למרות שלאט לאט מתקדמים אליו).
אגב - בדיקת הלוח עצמו: הכי טוב לבדוק לוח על ידי מערך ביטים שהחוקיות שלו תהיה שתא i הוא 1 אםם הבלוק/טור/שורה מכיל את i. ככה אתה רץ על כל איבר פעם אחת כדי לבנות תקינות BOARD.
גירסת הדפסה
סגן המנהל
מפקח
Winner
צל"ש
מומחה
שהפתרון הטריוויאלי (נניח ליצור באמצעות BFS או DFS כזה) את כל הלוחות ולבדוק האם הם תיקניים עלול לעלות (בהסתברות קטנה כנראה, אבל בכל זאת) כ-O של מספר הלוחות. מספר הקומבינציות ליצירת לוח סודוקו הם תשחע בחזקת 81. ואפשר להרחיב את בעיית הסודוקו עבור n = k^2 (בעיית סודוקו מקורית היא עבור k = 3). עבור הרחבה מהסוג הזה יוצא שהסיבוכיות Worst Case של הפתרון הבנאלי היא:
