Μια λύση για το Sudoku με βάση την τεχνητή νοημοσύνη

Μια λύση για το Sudoku με βάση την τεχνητή νοημοσύνη

Χρονική σήμανση: 29 Ιανουαρίου 2024 9:40 π.μ.
Κόμβος πηγής: 3091242

Στις 29 Ιανουαρίου είναι η Εθνική Ημέρα Παζλ και για τον εορτασμό, δημιουργήσαμε ένα διασκεδαστικό ιστολόγιο που περιγράφει λεπτομερώς πώς να λύσετε το Sudoku χρησιμοποιώντας τεχνητή νοημοσύνη (AI).

Εισαγωγή

Πριν wordle, τη Σουντόκου παζλ ήταν η οργή και εξακολουθεί να είναι πολύ δημοφιλές. Τα τελευταία χρόνια, η χρήση του βελτιστοποίηση Οι μέθοδοι επίλυσης του παζλ ήταν ένα κυρίαρχο θέμα. Βλέπω «Επίλυση παζλ Sudoku με χρήση βελτιστοποίησης στο Arkieva".

Επί του παρόντος, η χρήση της τεχνητής νοημοσύνης επικεντρώνεται στη μηχανική μάθηση, η οποία περιλαμβάνει ένα ευρύ φάσμα μεθόδων από την παλινδρόμηση λάσο έως την ενισχυτική μάθηση. Η χρήση του AI έχει επανεμφανίστηκε για την αντιμετώπιση σύνθετων προγραμματισμός προκλήσεις. Μια μέθοδος, η αναζήτηση με backtracking, χρησιμοποιείται συνήθως και είναι ιδανική για το Sudoku.

Αυτό το ιστολόγιο θα παρέχει μια λεπτομερή περιγραφή σχετικά με τον τρόπο χρήσης αυτής της μεθόδου για την επίλυση του Sudoku. Όπως αποδεικνύεται, το «backtracking» μπορεί να βρεθεί μέσα σε μηχανές βελτιστοποίησης και μηχανικής εκμάθησης και αποτελεί ακρογωνιαίο λίθο των προηγμένων ευρετικών που χρησιμοποιεί η Arkieva για τον προγραμματισμό. Ο αλγόριθμος υλοποιείται σε μια "Γλώσσα Προγραμματισμού Πίνακα", μια γλώσσα προγραμματισμού προσανατολισμένη στις λειτουργίες που χειρίζεται πλούσιο σύνολο δομών συστοιχιών.

Βασικά στοιχεία του Sudoku

Από τη Βικιπαίδεια: Το Sudoku είναι ένα παζλ που βασίζεται στη λογική, συνδυαστική τοποθέτηση αριθμών. Ο στόχος είναι να γεμίσετε ένα πλέγμα 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 , 9). Το αναγνωριστικό πλαισίου καθορίζεται από τον τύπο BOX_ID = {3x(δάπεδο((ROW_ID-1) /3)} + οροφή (COL_ID/3). Για το κελί (5,7), 6 = 3x(δάπεδο(5-1 ))/3) + οροφή (8/3)= 3×1 + 3 = 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) και στη συνέχεια να προσπαθήσετε να βρείτε υποψήφιες τιμές για ένα άλλο κελί.

A Backtracking Solution: Starting Components

Δομή Πίνακα

Το σημείο εκκίνησης είναι να αποφασίσετε για μια δομή πίνακα για την αποθήκευση του προβλήματος της πηγής και την υποστήριξη της αναζήτησης. Ο Πίνακας 3 έχει αυτή τη δομή πίνακα. Η στήλη 1 είναι ένα μοναδικό ακέραιο αναγνωριστικό για κάθε κελί. Οι τιμές κυμαίνονται από 1 έως 81. Η στήλη 2 είναι το αναγνωριστικό σειράς του κελιού. Η στήλη 3 είναι το αναγνωριστικό της στήλης του κελιού. Η στήλη 4 είναι το αναγνωριστικό πλαισίου. Η στήλη 5 είναι η τιμή στο κελί. Παρατηρήστε ότι σε ένα κελί χωρίς τιμή δίνεται η τιμή μηδέν αντί για κενό ή μηδενικό. Αυτό διατηρεί έναν "πίνακα μόνο ακέραιων αριθμών" - πολύ ανώτερη για απόδοση.

Στο 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
ΜΑΤ[1 2 3; 4 5] ασφαλίζει τις σειρές 1, 2, 3 και μόνο τις στήλες 4 και 5
1 2
1 0
1 0
(MAT[;5]=0)/MAT[;1] βρίσκει όλα τα κελιά που χρειάζονται μια τιμή.

ΕΙΣΑΓΕΤΕ ΠΙΝΑΚΑ 3

Έλεγχος υγιεινής: Αντίγραφα

Πριν ξεκινήσετε την αναζήτηση, είναι σημαντικό να ελέγξετε τη λογική! Αυτή είναι η εφικτή λύση εκκίνησης. Εφικτό για το Sudoku, υπάρχουν τώρα διπλότυπα σε οποιαδήποτε γραμμή, στήλη ή πλαίσιο. Η τρέχουσα λύση εκκίνησης, για παράδειγμα, 1 είναι εφικτή. Ο Πίνακας 4 έχει ένα παράδειγμα όπου η αρχική λύση έχει διπλότυπα. Η σειρά 1 έχει δύο τιμές 2. Η περιοχή 1 έχει δύο τιμές 2. Η συνάρτηση "SANITY_DUPE" χειρίζεται αυτήν τη λογική.

Έλεγχος υγιεινής: Επιλογές για κύτταρα χωρίς τιμές

Μια πολύ χρήσιμη πληροφορία θα ήταν όλες οι πιθανές τιμές για ένα κελί χωρίς τιμή. Αν δεν υπάρχουν υποψήφιοι, τότε αυτός ο γρίφος δεν είναι λύσιμος. Ένα κελί δεν μπορεί να λάβει μια τιμή που έχει ήδη διεκδικήσει ο γείτονάς του. Χρησιμοποιώντας τον Πίνακα 1 για το κελί (1,3,'1' – αυτό το τελευταίο 1 είναι το πλαίσιο), οι γείτονές του είναι η σειρά 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) . Η ενότητα "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. Εάν ένα κελί που χρειάζεται μια τιμή, δεν έχει υποψήφιους, τότε δεν υπάρχει πιθανή λύση σε αυτό το παζλ. Η λίστα υποψήφιων τιμών για κάθε κελί μπορεί να χρησιμοποιηθεί για τη μείωση του χώρου αναζήτησης – τόσο για backtracking όσο και για βελτιστοποίηση.
  3. Η ικανότητα εύρεσης συγκρούσεων προσδιορίζει το παζλ δεν είναι εφικτή – δεν έχει λύση – χωρίς διαδικασία αναζήτησης. Επιπλέον, προσδιορίζει τα «προβληματικά κελιά».

A Backtracking Solution: Διαδικασία αναζήτησης

Με τις βασικές δομές δεδομένων και τον έλεγχο της λογικής, στρέφουμε την προσοχή μας στη διαδικασία αναζήτησης. Το επαναλαμβανόμενο θέμα είναι και πάλι, η δημιουργία δομών δεδομένων για την υποστήριξη της αναζήτησης.

Παρακολούθηση της Αναζήτησης

Η συστοιχία Ιχνηλάτης παρακολουθεί τις εργασίες που έγιναν

  1. Το Col 1 είναι ο μετρητής
  2. Η στήλη 2 είναι ο αριθμός των διαθέσιμων επιλογών για εκχώρηση σε αυτό το κελί
    • 1 σημαίνει 1 διαθέσιμη επιλογή, 2 σημαίνει δύο επιλογές κ.λπ.
    • 0 σημαίνει – δεν υπάρχει διαθέσιμη επιλογή ή επαναφορά στο 0 (χωρίς εκχωρημένη τιμή) και backtracking
  3. Η στήλη 3 είναι το κελί στο οποίο έχει εκχωρηθεί ένας αριθμός ευρετηρίου τιμής (1 έως 81)
  4. Η στήλη 4 είναι η τιμή που έχει εκχωρηθεί στο κελί στο ιστορικό κομματιού
    • Η τιμή 9999 σημαίνει ότι αυτό το κελί ήταν όταν βρέθηκε το αδιέξοδο
    • Η τιμή ενός ακέραιου αριθμού μεταξύ 1 και 9, είναι η τιμή που έχει εκχωρηθεί σε αυτό το κελί σε αυτό το σημείο της διαδικασίας αναζήτησης.
    • Η τιμή 0 σημαίνει ότι αυτό το κελί χρειάζεται ανάθεση

Ο πίνακας παρακολούθησης χρησιμοποιείται για την υποστήριξη της διαδικασίας αναζήτησης. Η συστοιχία ΤΡΑΚΙΣΤΑΡ έχει την ίδια δομή με τον ιχνηλάτη, αλλά διατηρεί το ιστορικό ολόκληρης της διαδικασίας αναζήτησης. Ο Πίνακας 6 έχει μέρος του TRACKHIST για παράδειγμα 1. Επεξηγείται λεπτομερέστερα σε επόμενη ενότητα.

Επιπλέον, ο πίνακας Pav (ένα διάνυσμα ενός διανύσματος), παρακολουθεί τις τιμές που είχαν εκχωρηθεί προηγουμένως σε αυτό το κελί. Αυτό διασφαλίζει ότι δεν θα επανεξετάσουμε μια αποτυχημένη λύση – παρόμοια με αυτή που γίνεται στο TABU.

Υπάρχει μια προαιρετική διαδικασία καταγραφής όπου η διαδικασία αναζήτησης καταγράφει κάθε βήμα.

Έναρξη της Αναζήτησης

Με την τήρηση βιβλίων και τον έλεγχο της λογικής, μπορούμε πλέον να ξεκινήσουμε τη διαδικασία αναζήτησης. Τα βήματα είναι:

  1. Έχουν μείνει κάποια κελιά που χρειάζονται μια τιμή; – αν όχι, τότε τελειώσαμε.
  2. Για κάθε κελί που χρειάζεται μια τιμή, βρείτε όλες τις υποψήφιες επιλογές για κάθε κελί. Ο Πίνακας 4 έχει αυτές τις τιμές στην αρχή της διαδικασίας επίλυσης. Σε κάθε επανάληψη, αυτό ενημερώνεται για να χωρέσει τις τιμές που έχουν εκχωρηθεί στα κελιά.
  3. Αξιολογήστε τις επιλογές με αυτή τη σειρά.
    • Εάν ένα κελί έχει ΜΗΔΕΝΙ επιλογές, τότε εφαρμόστε το backtracking
    • Βρείτε όλα τα κελιά με μία επιλογή, επιλέξτε ένα από αυτά τα κελιά, κάντε αυτήν την ανάθεση,
      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 Optimization Solution

Σε επίπεδο επιφάνειας, η αναπαράσταση του παζλ Sudoku είναι δραματικά διαφορετική. Η προσέγγιση της τεχνητής νοημοσύνης χρησιμοποιεί ακέραιους αριθμούς και με οποιοδήποτε μέτρο είναι μια πιο σφιχτή και πιο διαισθητική αναπαράσταση. Επιπλέον, τα πούλια υγιεινής παρέχουν χρήσιμες πληροφορίες για να φτιάξετε μια ισχυρότερη σύνθεση. Η αναπαράσταση MILP είναι ατελείωτη δυαδικά (0/1). Ωστόσο, τα δυαδικά είναι ισχυρές αναπαραστάσεις δεδομένης της ισχύος των σύγχρονων επιλυτών MILP.

Ωστόσο, εσωτερικά, ο επιλύτης MILP δεν διατηρεί τα δυαδικά, αλλά χρησιμοποιεί μια μέθοδο αραιής διάταξης για να εξαλείψει την αποθήκευση όλων των μηδενικών. Επιπλέον, οι αλγόριθμοι για την επίλυση δυαδικών αρχείων δεν προέκυψαν παρά τις δεκαετίες του 1980 και του 1990. Το έγγραφο του 1983 από Crowder, Johnson και Padberg αναφέρει μια από τις πρώτες πρακτικές λύσεις βελτιστοποίησης με δυαδικά αρχεία. Σημειώνουν τη σημασία της έξυπνης προεπεξεργασίας και των μεθόδων διακλάδωσης και δέσμευσης ως καθοριστικής σημασίας για μια επιτυχημένη λύση.

Η πρόσφατη έκρηξη της χρήσης προγραμματισμού περιορισμών και λογισμικού όπως π.χ τοπικός λύτης κατέστησε σαφή τη σημασία της χρήσης μεθόδων τεχνητής νοημοσύνης με τις αρχικές μεθόδους βελτιστοποίησης, όπως ο γραμμικός προγραμματισμός και τα ελάχιστα τετράγωνα.

Σφραγίδα ώρας:

Περισσότερα από Η Αρκίεβα