Φίλοι του αλλοδαπού

Εισαγωγή

Sudoku, επίσης γνωστή ως "Number Place" είναι ένα λογικό παιχνίδι στόχος του οποίου είναι σχετικά απλή: με βάση τους αριθμούς που ήδη έχουν δοθεί σε θέση για κάθε ένα από τα κύτταρα του, έναν αριθμό που δεν είναι ήδη είτε στο ίδιο στην ίδια στήλη ή γραμμή, είτε στο ίδιο τεταρτημόριο ή τομέα.

Sudoku μοντέλα διαφοροποιούνται μεταξύ τους, αλλά το πιο διαδεδομένο, αποτελείται από 9 γραμμές από στήλες 9, 9 πλατείες, καθένα από τα 9 τεταρτημόρια της και σε κάθε ένα από σειρές και στήλες του θα πρέπει να τεθεί καλεί αριθμούς 1 έως 9. Ένα παράδειγμα θα μπορούσε να είναι:

Παρουσίαση του διαλύματος

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

Η ιδέα της υπαναχώρηση, αν δεν έχετε καταλάβει ακόμη, φαίνεται αρκετά καλά σε αυτά τα παραδείγματα από τον Επίσκοπο και το πιόνι, το τρέχει από τον βασιλιά και την n-Πρόχειρα.

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

Ψήφισμα Process

Το διοικητικό συμβούλιο του Sudoku για να λύσει δίνεται από έναν γονέα "Sol [1 .. 9,1 .. 9] του 0 .. 9" όπου η Sun [i, j], αντιπροσωπεύει την αξία που έχει το κελί, που αντιστοιχεί σε 0 με κενό τετράγωνο. Χρησιμοποιεί μια μήτρα βοηθητικό "αρχική [1 .. 9 1 .. 9] του Bool" όπου οι αρχικές [i, j] αντιπροσωπεύει ένα κελί με την αρχική αξία δεν μπορεί να αλλάξει και να αντιστοιχεί στο κελί "Sol [i, j] ".

Όταν η διακλάδωση δέντρο της εξερεύνησης, θα κάνουμε μόνο αν η μερική λύση είναι ότι εμείς αντιμετωπίζουμε k-πολλά υποσχόμενη, είναι ότι, αν μετά από μια τέτοια μερική λύση μπορεί να συνεχίσει να δημιουργεί μερικές λύσεις. Για να αντιμετωπιστεί αυτό το σημείο, χρησιμοποιούμε βοηθός λειτουργία που ονομάζεται "es_factible.

Το δέντρο πλοήγησης που δημιουργούνται θα έχει τα ακόλουθα χαρακτηριστικά:

• Ύψος = m + 1: m Όντας ο αριθμός των κενών κιβωτίων αρχικά.
• Αριθμός των παιδιών του κάθε κόμβος = 9: Ένα παιδί για κάθε δυνατή τιμή της θ κυττάρων

Λήψη

Το πρόγραμμα που έχω κάνει περιλαμβάνει όλα τα αρχεία κειμένου που βρίσκονται στο debug φάκελο του έργου και η διαδικασία δημιουργεί μια λύση αρχείο για κάθε sudoku και μια γενική περίληψη αρχείο με το χρόνο που απαιτείται για την επίλυση κάθε μία από αυτές. Αφήνω τον πηγαίο κώδικα, καθώς και έκθεση σε pdf.