פתרון מבוסס בינה מלאכותית לסודוקו

פתרון מבוסס בינה מלאכותית לסודוקו

חותמת זמן: 29 בינואר 2024 9:40
צומת המקור: 3091242

29 בינואר הוא יום הפאזלים הלאומי, ולכבוד חגיגות, יצרנו בלוג מהנה המפרט כיצד לפתור סודוקו באמצעות בינה מלאכותית (AI).

מבוא

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

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

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

יסודות סודוקו

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

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

הסיבוך

בנוסף להשתייכות לשורה אחת ועמודה אחת ויחידה, תא שייך לתיבה אחת ויחידה. ישנן 1 תיבות, והן מסומנות בצבע בטבלה 9. טבלה 1 משתמשת במספר שלם ייחודי בין 2 ל-1 כדי לזהות כל תיבה או רשת. התאים עם ערך שורה של (9, 1 או 2) וערך עמודה של (3, 1 או 2) שייכים לתיבה 3. תיבה 1 היא ערכי שורה של (6, 4, 5) וערכי העמודות (6, 7 , 8). מזהה התיבה נקבע על ידי הנוסחה BOX_ID = {9x(floor((ROW_ID-3) /1)} + תקרה (COL_ID/3). עבור התא (3), 5,7 = 6x(floor(3-5) ))/1) + תקרה (3/8)= 3×3 + 1 = 3+3.

לב הפאזל

כדי למצוא ערך שלם אחד בין 1 ל-9 עבור כל תא לא ידוע כך שהמספרים השלמים 1 עד 9 ישמשו פעם אחת ופעם אחת בלבד עבור כל עמודה, כל שורה וכל תיבה.

בואו נסתכל על התא (1,3) שהוא ריק. בשורה 1 כבר יש את הערכים 2 ו-7. אלה אינם מותרים בתא זה. בעמודה 3 כבר יש את הערכים 3, 5,6, 7,9. אלה אינם מותרים. בתיבה 1 (צהובה) יש את הערכים 2, 3 ו-8. אלו אסורים. הערכים הבאים אינם מותרים (2,7); (3, 5, 6, 7, 9); (2, 3, 8). הערכים הייחודיים שאינם מותרים הם (2, 3, 5, 6, 7, 8, 9). הערכים המועמדים היחידים הם (1,4).

גישת פתרון תהיה להקצות זמנית 1 לתא (1,3) ואז לנסות למצוא ערכים מועמדים לתא אחר.

פתרון לעקיבה לאחור: התחלת רכיבים

מבנה מערך

מקום ההתחלה הוא להחליט על מבנה מערך לאחסון בעיית המקור ולתמוך בחיפוש. לטבלה 3 יש מבנה מערך זה. עמודה 1 היא מזהה מספר שלם ייחודי עבור כל תא. הערכים נעים בין 1 ל-81. עמודה 2 היא מזהה השורה של התא. עמודה 3 היא מזהה העמודה של התא. עמודה 4 היא מזהה התיבה. עמודה 5 היא הערך בתא. התבוננות בתא ללא ערך מקבל את הערך אפס במקום ריק או null. זה שומר על "מערך שלמים בלבד" - עדיפה בהרבה מבחינת ביצועים.

ב-APL, מערך זה יאוחסן במערך דו מימדי שבו הצורה היא 2 על 81. נניח שהאלמנטים של טבלה 5 מאוחסנים במשתנה MAT. פונקציות לדוגמה הן:

הפקודה MAT[1 2 3;]תופסת את 3 השורות הראשונות של MAT
1 1 1 1 2
2 1 2 1 0
3 1 3 1 0
MAT[1 2 3; 4 5] מאבטח את שורות 1, 2, 3 ורק עמודות 4 ו-5
1
1
1
(MAT[;5]=0)/MAT[;1] מוצא את כל התאים שצריכים ערך.

הכנס טבלה 3

בדיקת שפיות: כפילויות

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

בדיקת שפיות: אפשרויות לתאים ללא ערכים

פיסת מידע מועילה מאוד תהיה כל הערכים האפשריים עבור תא ללא ערך. אם אין מועמדים, אז החידה הזו אינה ניתנת לפתרון. תא לא יכול לקבל ערך שכבר נתבע על ידי שכנו. באמצעות טבלה 1 עבור תא (1,3,'1' – 1 האחרון הוא ה-box), השכנות שלו הן שורה 1, עמודה 3 ותיבה 1. בשורה 1 יש את הערכים (2,7); בעמודה 3 יש את הערכים (3,5,6,7,9); בתיבה 1 יש את הערכים (2,3,8). התא (1,3.1) אינו יכול לקבל את הערכים הבאים (2,3,5,6,7,8,9). האפשרויות היחידות לתא (1,3,1) הן (1,4). עבור תא (4,1,2) הערכים 1, 2, 3, 5, 6, 7, 9 כבר נמצאים בשימוש בשורה 4, עמודה 1 ו/או בתיבה 4. הערכים המועמדים היחידים הם (4,8) . ה-unction "SANITY_CAND" מטפל בהיגיון הזה.

טבלה 5 מציגה את המועמדים, למשל, 1 בתחילת תהליך החיפוש. אם לתא כבר הוקצה ערך בתנאי ההתחלה (טבלה 1), אז ערך זה חוזר על עצמו ומוצג באדום. אם לתא שצריך ערך יש רק אפשרות אחת, היא מוצגת בלבן. לתא (8,7,9) יש את הערך היחיד 7 בלבן. (2,5,8,4,3) נתבעים על ידי עמודה 7 שכן. (1, 2, 9) על ידי שורה 8. (3,2,6) על ידי תיבה 9. רק הערך 7 אינו נתבע.

בדיקת שפיות: מחפש קונפליקטים

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

מה יהיה סכסוך? אם הערך היחיד האפשרי לתא (3,7,3) היה 7 (במקום 1, 6, 7), אז יש התנגשות. תא (8,7) ותא (3,7) הם שכנים - אותה עמודה. עם זאת, אם הערך האפשרי היחיד לתא (4,9,2) היה 7 (במקום 1, 2, 7) זה לא היה קונפליקט. תאים אלו אינם שכנים.

סיכום בדיקת שפיות

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

פתרון לחזרה לאחור: תהליך חיפוש

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

מעקב אחר החיפוש

המערך גשש עוקב אחר המטלות שבוצעו

  1. קול 1 הוא המונה
  2. Col 2 הוא מספר האפשרויות הזמינות להקצאה לתא זה
    • 1 פירושו אפשרות אחת זמינה, 1 פירושו שתי אפשרויות וכו'.
    • 0 פירושו - אין אפשרות זמינה או איפוס ל-0 (ללא ערך מוקצה) וחזרה לאחור
  3. קול 3 הוא התא שהוקצה לו מספר אינדקס ערך (1 עד 81)
  4. Col 4 הוא הערך שהוקצה לתא בהיסטוריית המסלול
    • ערך של 9999 אומר שהתא הזה היה כאשר נמצא המבוי הסתום
    • הערך של מספר שלם בין 1 ל-9 כולל, הוא הערך שהוקצה לתא זה בשלב זה של תהליך החיפוש.
    • ערך של 0 אומר שהתא הזה צריך הקצאה

מערך המעקב משמש לתמיכה בתהליך החיפוש. המערך HIST יש את אותו מבנה כמו הגשש אבל שומר את ההיסטוריה של כל תהליך החיפוש. בטבלה 6 יש חלק מ-TRACKHIST למשל 1. הוא מוסבר ביתר פירוט בחלק מאוחר יותר.

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

קיים תהליך יומן אופציונלי שבו תהליך החיפוש כותב כל שלב.

התחלת החיפוש

עם ביצוע הנהלת חשבונות ובדיקת שפיות, כעת נוכל להתחיל בתהליך החיפוש. השלבים הם:

  1. האם נותרו תאים שצריכים ערך? - אם לא, אז סיימנו.
  2. עבור כל תא שצריך ערך, מצא את כל האפשרויות המועמדות עבור כל תא. בטבלה 4 יש ערכים אלה בתחילת תהליך הפתרון. בכל איטרציה, זה מתעדכן כדי להתאים לערכים שהוקצו לתאים.
  3. הערך את האפשרויות בסדר זה.
    • אם לתא יש אפס אפשרויות, הפעל מעקב לאחור
    • מצא את כל התאים עם אפשרות אחת, בחר אחד מהתאים האלה, בצע את ההקצאה הזו,
      1. ועדכן את טבלת המעקב, הפתרון הנוכחי ו-PAV.
    • אם לכל התאים יש יותר מאפשרות אחת, בחר תא אחד וערך אחד ועדכן
      1. ועדכן את טבלת המעקב, הפתרון הנוכחי ו-PAV

נשתמש בטבלה 6 שהיא חלק מההיסטוריה של תהליך הפתרון (הנקרא TRACKHIST) כדי להמחיש כל שלב.

באיטרציה הראשונה (CTR=1), תא 70 (שורה 8, קול 7, תיבה 9) נבחר להקצאת ערך. יש רק מועמד (7), והערך הזה מוקצה לתא 70. בנוסף, הערך 7 מתווסף לווקטור של ערכים שהוקצו קודם לכן (PAV) עבור תא 70.

באיטרציה השנייה תא 30 מוקצה הערך 1. לתא זה היו שני ערכים מועמדים. הערך המועמד הקטן ביותר מוקצה לתא (רק כלל שרירותי כדי להקל על ההיגיון).

התהליך של זיהוי תא שצריך ערך והקצאת ערך עובד מצוין עד איטרציה (CTR) 20. תא 9 צריך ערך, אבל מספר המועמדים הוא אפס. ישנן שתי אפשרויות:

  • אין פתרון לחידה הזו.
  • אנחנו מבטלים (בחזרה) חלק מהמשימות ויוצאים לדרך אחרת.

חיפשנו את הקצאת התא הקרובה ביותר לכך, שבה הייתה יותר מאפשרות אחת. בדוגמה זו, זה התרחש באיטרציה 18, כאשר לתא 5 מוקצה הערך 3, אך היו שני ערכים מועמדים לתא 5 - ערכים 3 ו-8.

בין תא 5 (CTR = 18) לתא 9 (CTR = 20), לתא 8 מוקצה הערך 4 (CTR=19). החזרנו את התאים 8 ו-5 לרשימת "צריך ערך". זה נלכד בערכים השני והשלישי של CTR=20, כאשר הערך מוגדר ל-0. הערך 3 נשמר בווקטור PAV עבור תא 5. כלומר מנוע החיפוש לא יכול להקצות את הערך 3 לתא 5.

מנוע החיפוש מתחיל שוב כדי לזהות ערך עבור תא 5 (כאשר 3 כבר לא אופציה) ומקצה את הערך 8 לתא 5 (CTR=21). זה ממשיך עד שלכל התאים יש ערך או שיש תא ללא אפשרות ואין נתיב חזרה. הפתרון מופיע בטבלה 7.

שימו לב, כאשר יש יותר ממועמד אחד לתא, זהו סיכוי לעיבוד מקביל.

השוואה לפתרון אופטימיזציה של MILP

ברמת פני השטח, הייצוג של פאזל סודוקו שונה באופן דרמטי. גישת הבינה המלאכותית משתמשת במספרים שלמים ולפי כל מדד היא ייצוג הדוק ואינטואיטיבי יותר. בנוסף, בודקי השפיות מספקים מידע מועיל כדי ליצור ניסוח חזק יותר. הייצוג של MILP הוא אינסופי בינאריות (0/1). עם זאת, הקבצים הבינאריים הם ייצוגים רבי עוצמה בהתחשב בחוזקם של פותרי MILP מודרניים.

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

הפיצוץ האחרון של השימוש בתכנות אילוצים ותוכנות כגון פותר מקומי הבהירה את החשיבות של שימוש בשיטות AI עם שיטות האופטימיזציה המקוריות כמו תכנות ליניארי וריבועים קטנים.

בול זמן:

עוד מ ארקייבה