Sudoku FlowΠώς οι υπολογιστές λύνουν Sudoku
Ενημερώθηκε στις 2026-10-05
Οπισθοδρόμηση
Ο λύτης δοκιμάζει ένα επιτρεπτό ψηφίο σε ένα κενό κελί και συνεχίζει. Αν κανένα ψηφίο δεν οδηγεί σε λύση, αναιρεί μια προηγούμενη επιλογή και δοκιμάζει μια άλλη. Αν επιλέγεται πρώτα το κελί με τα λιγότερα δυνατά ψηφία, η αναζήτηση συχνά συντομεύει πολύ.
Πηγές: Wikipedia: Sudoku solving algorithms, Peter Norvig: Solving Every Sudoku Puzzle
Ακριβής κάλυψη και Dancing Links
Το Sudoku μπορεί να αναδιατυπωθεί ως πρόβλημα ακριβούς κάλυψης: επιλέγονται τοποθετήσεις έτσι ώστε κάθε κελί, καθώς και κάθε ψηφίο σε κάθε γραμμή, στήλη και τετράγωνο, να καλύπτεται ακριβώς μία φορά. Σε μια εργασία του Νοεμβρίου του 2000, ο Ντόναλντ Κνουθ περιέγραψε το Dancing Links, έναν αποδοτικό τρόπο εκτέλεσης του Αλγορίθμου X, του δικού του αλγορίθμου οπισθοδρόμησης. Όταν εφαρμόζεται στο μοντέλο ακριβούς κάλυψης του Sudoku, βρίσκει γρήγορα όλες τις λύσεις ενός γρίφου.
Πηγές: Wikipedia: Sudoku solving algorithms, Knuth, Dancing links (arXiv cs/0011047, 2000)
Τυχαία αναζήτηση
Ορισμένα προγράμματα γεμίζουν το πλέγμα τυχαία και στη συνέχεια αναδιατάσσουν τους αριθμούς για να μειώσουν το πλήθος των συγκρούσεων, με μεθόδους όπως η προσομοιωμένη ανόπτηση ή οι γενετικοί αλγόριθμοι. Έχουν μελετηθεί ως εναλλακτικές προσεγγίσεις. Το πόσο καλά αποδίδουν εξαρτάται από το πρόγραμμα και τον γρίφο.
Πηγές: Wikipedia: Sudoku solving algorithms
Λύτες που σκέφτονται όπως οι άνθρωποι
Μια μηχανή υποδείξεων έχει διαφορετικό έργο: όχι μόνο να βρει την απάντηση, αλλά και να δείξει το επόμενο βήμα που μπορεί να ακολουθήσει ένας άνθρωπος. Η μηχανή της εφαρμογής μας δοκιμάζει ανθρώπινες τεχνικές με σταθερή σειρά, από τις ευκολότερες, όπως το Κρυφό Μονό, έως τις δυσκολότερες, όπως οι αλυσίδες και τα σχεδόν κλειδωμένα σύνολα, και χρησιμοποιεί την πρώτη που οδηγεί στην τοποθέτηση ενός ψηφίου. Οι δυσκολότερες τεχνικές λειτουργούν αποκλείοντας πρώτα υποψήφια ψηφία. Η δυσκολότερη τεχνική που χρησιμοποιεί σε έναν γρίφο καθορίζει το επίπεδο αυτού του γρίφου στην εφαρμογή.
Πηγές: Τι σου ζητά κάθε επίπεδο δυσκολίας Sudoku
