Μελετήστε προσεκτικά αυτόν τον κώδικα και ανακαλύψτε έναν έξυπνο τρόπο να χρησιμοποιήσετε την αναδρομή για να λύσετε αυτούς τους δύσκολους γρίφους sudoku.
Το Sudoku είναι ένα δημοφιλές παζλ αριθμών που αποτελείται από ένα πλέγμα 9x9 με ψηφία από το 1 έως το 9. Το παζλ περιλαμβάνει έναν συνδυασμό αριθμών και μερικά κενά, τα οποία πρέπει να συμπληρώσετε.
Κατά τη συμπλήρωση των κενών διαστημάτων, κάθε γραμμή, στήλη και υπο-πλέγμα 3x3 πρέπει να περιέχει όλα τα ψηφία από το 1 έως το 9.
Ένα απλό σενάριο Python μπορεί να σας βοηθήσει να λύσετε ένα παζλ Sudoku. Μπορεί να αναλύσει όλα τα κενά κενά στον πίνακα Sudoku και να βρει έναν πιθανό αριθμό για να συμπληρώσει κάθε κενό διάστημα.
Πώς να δημιουργήσετε και να εμφανίσετε τον πίνακα Sudoku
Μέσα σε ένα σενάριο Python, θα χρειαστεί να χρησιμοποιήσετε μια λίστα πινάκων για να αποθηκεύσετε τις τιμές του άλυτου παζλ Sudoku.
Ο κώδικας που χρησιμοποιείται σε αυτό το έργο είναι διαθέσιμος σε αυτό Αποθετήριο GitHub υπό την άδεια του MIT.
- Μέσα σε ένα νέο σενάριο Python που ονομάζεται sudoku.py, αποθηκεύστε όλες τις τιμές για το πλέγμα 9x9. Κάθε σειρά και στήλη αντιπροσωπεύουν τους εννέα αριθμούς κατά μήκος και κάτω από το παζλ Sudoku. Προσθέστε 0 για να αναπαραστήσετε τα κενά που χρειάζονται επίλυση:
σανίδα = [
[5, 3, 0, 0, 7, 0, 0, 0, 0],
[6, 0, 0, 1, 9, 5, 0, 0, 0],
[0, 9, 8, 0, 0, 0, 0, 6, 0],
[8, 0, 0, 0, 6, 0, 0, 0, 3],
[4, 0, 0, 8, 0, 3, 0, 0, 1],
[7, 0, 0, 0, 2, 0, 0, 0, 6],
[0, 6, 0, 0, 0, 0, 2, 8, 0],
[0, 0, 0, 4, 1, 9, 0, 0, 5],
[0, 0, 0, 0, 8, 0, 0, 7, 9]
] - Μέσα σε μια νέα συνάρτηση που ονομάζεται print_board, χρησιμοποιήστε έναν βρόχο for για να επεξεργαστείτε κάθε σειρά στο πλέγμα:
defprint_board(σανίδα):
Για σειρά σε εύρος(9): - Για να διαχωρίσετε κάθε σειρά σε τρίτες, ελέγξτε αν η σειρά διαιρείται με το τρία και προσθέστε μια γραμμή:
αν σειρά % 3 == 0και σειρά != 0:
Τυπώνω("- - - - - - - - - - - - - - ") - Εντός κάθε σειράς, πραγματοποιήστε κύκλο σε κάθε στήλη. Μπορείτε επίσης να χωρίσετε τις στήλες σε τρίτα ελέγχοντας εάν η στήλη διαιρείται με τρία:
Για διάσελο σε εύρος(9):
αν col % 3 == 0και col != 0:
Τυπώνω(" | ", τέλος="") - Εκτυπώστε την αριθμητική τιμή που είναι αποθηκευμένη στο πλέγμα. Εάν η στήλη είναι η τελευταία στήλη για τη συγκεκριμένη σειρά, προσθέστε μια γραμμή διακοπής, έτσι ώστε η ακόλουθη σειρά να εμφανίζεται σε μια νέα γραμμή:
αν col == 8:
εκτύπωση (board[row][col])
αλλού:
print (str (board[row][col]) + " ", τέλος="") - Καλέστε τη συνάρτηση για να εκτυπώσετε τον πίνακα:
print_board (σανίδα) - Σε μια γραμμή εντολών, μεταβείτε στο φάκελο όπου αποθηκεύσατε το σενάριο python, για παράδειγμα:
cd Επιτραπέζιος υπολογιστής - Χρησιμοποιήστε την εντολή python για να εκτελέσετε το σενάριο Sudoku. Δείτε το παζλ τυπωμένο στην οθόνη:
python sudoku.py
Πώς να προσδιορίσετε τα κενά για επίλυση
Μπορείτε να διασχίσετε τις λίστες για να βρείτε τα κενά που αποτελούνται από 0. Αυτά καθορίζουν ποιοι χώροι χρειάζονται επίλυση.
- Σε μια νέα συνάρτηση που ονομάζεται find_empty(), κάντε βρόχο σε κάθε γραμμή και στήλη στον πίνακα:
deffind_empty(σανίδα):
Για σειρά σε εύρος(9):
Για διάσελο σε εύρος(9): - Εάν η τιμή του τρέχοντος κελιού είναι 0, επιστρέψτε την τρέχουσα θέση του κενού κελιού:
αν board[row][col] == 0:
ΕΠΙΣΤΡΟΦΗ (σειρά, στήλη) - Εάν το σενάριο φτάσει στο τέλος της συνάρτησης, αυτό σημαίνει ότι το σενάριο δεν μπορούσε να βρει κανένα κελί με την τιμή 0. Σε αυτήν την περίπτωση, μην επιστρέψετε τίποτα:
ΕΠΙΣΤΡΟΦΗΚανένας - Σε μια νέα συνάρτηση που ονομάζεται solve(), χρησιμοποιήστε τη συνάρτηση find για να βρείτε τον πρώτο κενό χώρο στον πίνακα:
defλύσει(σανίδα):
find = find_empty (σανίδα) - Η συνάρτηση find_empty() επιστρέφει τη θέση του κελιού σε μορφή πλειάδας, για παράδειγμα, (0, 2). Αποθηκεύστε αυτές τις τιμές χωριστά στο σειρά και διάσελο μεταβλητές. Διαφορετικά, επιστρέψτε true για να δηλώσετε ότι δεν υπάρχουν κενά κενά για επίλυση:
ανδεν εύρημα:
ΕΠΙΣΤΡΟΦΗΑληθής
αλλού:
row, col = βρίσκω
Πώς να λύσετε το παζλ για κάθε γραμμή, στήλη και πλέγμα 3x3
Τώρα που μπορείτε να προσδιορίσετε τον πρώτο κενό χώρο προς επίλυση, θα πρέπει να προσπαθήσετε να βρείτε έναν κατάλληλο αριθμό για να γεμίσετε αυτόν τον χώρο και να λύσετε το παζλ.
Χρήση αναδρομής, καλέστε τη συνάρτηση solve() μέσα της για να δοκιμάσετε κάθε πιθανό συνδυασμό τιμών και για όλους τους άλλους χώρους.
- Μέσα στη συνάρτηση solve(), αφού βρείτε τον πρώτο κενό χώρο, πραγματοποιήστε κύκλο σε κάθε αριθμό από το 1 έως το 9. Αυτοί οι αριθμοί αντιπροσωπεύουν τους πιθανούς αριθμούς που θα μπορούσαν να γεμίσουν τον άλυτο χώρο:
Για αρ σε εύρος(1, 10): - Εισαγάγετε τον πίνακα, τον πιθανό αριθμό και τη θέση του κενού κελιού σε μια νέα συνάρτηση. Η νέα συνάρτηση θα επιστρέψει true εάν αυτός ο αριθμός είναι ένας έγκυρος αριθμός που μπορεί να λύσει αυτόν τον κενό χώρο. Εάν είναι έγκυρος, αντιστοιχίστε αυτόν τον αριθμό στο κελί στον πίνακα:
αν is_valid (board, num, (row, col)):
board[row][col] = αρ - Δημιουργήστε τη συνάρτηση is_valid(), με αντίστοιχες παραμέτρους:
defείναι έγκυρο(πίνακας, αριθμός, θέση): - Χρησιμοποιήστε τη συνάρτηση για να ελέγξετε εάν η τοποθέτηση του αριθμού σε αυτή τη θέση παραβιάζει οποιονδήποτε κανόνα του παιχνιδιού Sudoku. Πρώτα, ελέγξτε εάν αυτός ο αριθμός υπάρχει ήδη στη γραμμή ή στη στήλη του κελιού:
Για διάσελο σε εύρος(9):
αν σανίδα[θέση[0]][col] == αρ και θέση[1] != col:
ΕΠΙΣΤΡΟΦΗΨευδήςΓια σειρά σε εύρος(9):
αν board[row][pos[1]] == αρ και θέση[0] != σειρά:
ΕΠΙΣΤΡΟΦΗΨευδής - Αποκτήστε το πλέγμα 3x3 στο οποίο ανήκει το κελί. Μπορείτε να το κάνετε αυτό διαιρώντας τη θέση του κελιού με τρία:
box_row = pos[0] // 3
box_col = pos[1] // 3 - Για κάθε γραμμή και στήλη σε αυτό το πλέγμα 3x3, ελέγξτε αν ο αριθμός υπάρχει ήδη. Εάν ναι, επιστρέψτε το false:
Για σειρά σε εύρος (box_row*3, box_row*3 + 3):
Για διάσελο σε εύρος (box_col*3, box_col*3 + 3):
αν board[row][col] == αρ και (σειρά, στήλη) != θέση:
ΕΠΙΣΤΡΟΦΗΨευδής - Εάν το σενάριο φτάσει στο τέλος της λειτουργίας, αυτό σημαίνει ότι κανένας από τους κανόνες του Sudoku δεν απέτυχε. Επιστροφή αλήθειας:
ΕΠΙΣΤΡΟΦΗΑληθής - Η συνάρτηση is_valid() ελέγχει μόνο εάν η τοποθέτηση αριθμού είναι έγκυρη, αλλά αυτό δεν σημαίνει ότι είναι η σωστή απάντηση στη συνολική λύση. Μέσα στη συνάρτηση solve(), καλέστε ξανά τη συνάρτηση solve() με τον ενημερωμένο πίνακα. Η συνάρτηση solve() μπορεί να φτάσει σε μια κατάσταση όπου δεν μπορεί πλέον να χρησιμοποιεί αριθμούς για να γεμίσει κενά. Σε αυτήν την περίπτωση, ολόκληρη η συνάρτηση επιστρέφει false, επαναφέρει το συγκεκριμένο κελί στο 0 και κάνει backtrack. Η συνάρτηση solve() επιστρέφει true μόνο όταν το σενάριο μπορεί να γεμίσει όλα τα κενά:
Για αρ σε εύρος(1, 10):
αν is_valid (board, num, (row, col)):
board[row][col] = αρ
αν λύνω (σανίδα):
ΕΠΙΣΤΡΟΦΗΑληθής
board[row][col] = 0ΕΠΙΣΤΡΟΦΗΨευδής - Για να ξεκινήσετε να λύνετε το παζλ, καλέστε τη συνάρτηση solve() με τον αρχικό πίνακα, στο κάτω μέρος του σεναρίου, αφού δηλώσετε τη συνάρτηση solve():
λύνω (σανίδα) - Εκτυπώστε το τελικό αποτέλεσμα:
Τυπώνω("Λύθηκε:")
print_board (σανίδα) - Στη γραμμή εντολών, χρησιμοποιήστε την εντολή python για να εκτελέσετε ξανά το σενάριο. Δείτε το λυμένο παζλ τυπωμένο στην οθόνη:
python sudoku.py
Δημιουργία παιχνιδιών με χρήση Python
Το Sudoku είναι μόνο ένα από τα πολλά παιχνίδια που μπορείτε να δημιουργήσετε και να λύσετε χρησιμοποιώντας την Python. Μπορείτε να χρησιμοποιήσετε την Python για να δημιουργήσετε διάφορα άλλα παιχνίδια, όπως ένα συνονθύλευμα λέξεων, ένα παιχνίδι περιπέτειας που βασίζεται σε κείμενο ή ένα παιχνίδι με χρώματα, για να αναφέρουμε μόνο μερικά.