Πόσα Sudoku υπάρχουν; Μετρήσεις και μαθηματικά

Πίνακας περιεχομένων

• Πόσα Sudoku υπάρχουν; Μια ακριβής και απλή απάντηση
• Τι σημαίνει «μοναδικό» στη μέτρηση των Sudoku;
• Γιατί το «πόσα Sudoku υπάρχουν» είναι δύσκολο ερώτημα
• Πώς υπολογίστηκε ο αριθμός 6.67×10^21
• Ελάχιστα στοιχεία: γιατί το 17 έχει σημασία στη μέτρηση των γρίφων
• Πόσα πλέγματα Sudoku υπάρχουν και πόσα παζλ Sudoku;
• Πίνακας σύγκρισης
• Πίνακας σύγκρισης
• Δημιουργία στην πράξη: τι βλέπουμε στην πραγματικότητα
• Γιατί αυτό έχει σημασία για παίκτες και σχεδιαστές εφαρμογών
• Πώς μειώνουν οι ερευνητές τα διπλότυπα; (Ουσιαστικά διαφορετικά Sudoku)
• Τι καθορίζει την αύξηση του πλήθους των γρίφων από ένα μόνο πλέγμα;
• Στοιχεία και παραπομπές που μπορείτε να εμπιστευτείτε
• Η άποψη ειδικού για τα πρακτικά όρια
• Σχετικές έννοιες και ορολογία που αξίζει να γνωρίζετε
• Βασικά συμπεράσματα

Πόσα Sudoku υπάρχουν; Για το κλασικό Sudoku 9x9, υπάρχουν 6,670,903,752,021,072,936,960 ολοκληρωμένα πλέγματα λύσης, και τα 5,472,730,538 από αυτά είναι ουσιαστικά διαφορετικά αν λάβουμε υπόψη τις συμμετρίες. Ο ακριβής αριθμός των έγκυρων γρίφων Sudoku με μοναδική λύση δεν είναι γνωστός, αλλά είναι ασύλληπτα μεγαλύτερος από τον αριθμό των πλεγμάτων λύσης.

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

Πόσα Sudoku υπάρχουν; Μια ακριβής και απλή απάντηση

• Ολοκληρωμένα πλέγματα λύσης Sudoku 9x9: 6,670,903,752,021,072,936,960 (περίπου 6.67×10^21), επιβεβαιωμένα με συνδυαστική απαρίθμηση πηγή: Wikipedia.
• Ουσιαστικά διαφορετικά πλέγματα λύσης 9x9 (με αφαίρεση των έγκυρων συμμετριών): 5,472,730,538, αποδεδειγμένα με μείωση μέσω θεωρίας ομάδων πηγή: arXiv.
• Αριθμός έγκυρων γρίφων Sudoku 9x9 (με στοιχεία και μοναδική λύση): άγνωστος ακριβώς, αλλά πολύ μεγαλύτερος από τον αριθμό των πλεγμάτων λύσης, επειδή κάθε πλέγμα μπορεί να δώσει πολλά διαφορετικά παζλ με μοναδική λύση.

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

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

Τι σημαίνει «μοναδικό» στη μέτρηση των Sudoku;

Στη μέτρηση, το «μοναδικό» έχει περισσότερες από μία σημασίες:

• Μοναδική λύση: Ο γρίφος (με τα δοσμένα στοιχεία) έχει ακριβώς ένα ολοκληρωμένο πλέγμα λύσης.
• Ουσιαστικά διαφορετικό: Δύο ολοκληρωμένα πλέγματα θεωρούνται ίδια αν διαφέρουν μόνο κατά επιτρεπτές συμμετρίες (αντιστοίχιση ψηφίων, μεταθέσεις γραμμών/στηλών μέσα σε ζώνες/στοίβες, ανταλλαγή ζωνών/στοίβων ή μεταφορά). Αυτά θεωρούνται ένας «τύπος».

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

Γιατί το «πόσα Sudoku υπάρχουν» είναι δύσκολο ερώτημα

• Πρέπει να αποφασίσετε τι θεωρείται ίδιο παζλ. Θεωρείτε δύο γρίφους που διαφέρουν μόνο στην αντιστοίχιση των ψηφίων ως διαφορετικούς; Πολλοί μαθηματικοί όχι.
• Ο χώρος αναζήτησης των υποσυνόλων στοιχείων είναι συνδυαστικά εκρηκτικός. Ο έλεγχος μοναδικότητας απαιτεί επίλυση, όχι απλή μέτρηση.
• Οι περιορισμοί δυσκολίας έχουν σημασία. Οι σχεδιαστές εφαρμογών ενδιαφέρονται για το «πόσα Sudoku υπάρχουν συγκεκριμένης δυσκολίας», που είναι διαφορετικό φίλτρο.

Όπως σημειώνει η δρ. Lina Park, ερευνήτρια συνδυαστικής: «Η μέτρηση των πλεγμάτων λύσης Sudoku είναι ένα καθαρό πρόβλημα απαρίθμησης. Η μέτρηση όλων των έγκυρων γρίφων με μοναδική λύση είναι διαφορετικό θηρίο, γιατί προσθέτει λογική επίλυσης πάνω στην καθαρή συνδυαστική.»

Πώς υπολογίστηκε ο αριθμός 6.67×10^21

Η καθιερωμένη μέτρηση για το 9x9 χρησιμοποιεί συνδυαστική απαρίθμηση με αποκοπή συμμετριών:

1. Δημιουργούνται κανονικοποιημένοι αντιπρόσωποι δομών τύπου Latin square που είναι συμβατές με τα 3×3 πλαίσια.
2. Εφαρμόζονται δράσεις ομάδων (μεταθέσεις γραμμών/στηλών μέσα σε ζώνες/στοίβες, ανταλλαγές ζωνών/στοίβων, μεταφορά και αντιστοίχιση ψηφίων) ώστε να αποφευχθεί η περιττή επανάληψη.
3. Αθροίζονται οι τροχιές για να προκύψει ο πλήρης αριθμός.

Κύρια στοιχεία συμμετρίας που αναφέρονται συχνά πηγή: Wikipedia:

• Αντιστοίχιση ψηφίων: 9! = 362,880
• Μεταθέσεις γραμμών μέσα σε καθεμία από τις 3 ζώνες: (3!)^3
• Μεταθέσεις στηλών μέσα σε καθεμία από τις 3 στοίβες: (3!)^3
• Ανταλλαγή των 3 ζωνών και των 3 στοίβων: 3! × 3!
• Μεταφορά: ×2
• Μέγεθος γινομένου: περίπου 1.22×10^12 συμμετρίες (όχι κάθε πλέγμα δεν επιτυγχάνει πλήρη τροχιά, αλλά αυτό δίνει την κλίμακα)

Γιατί έχει σημασία αυτό για το «πόσα Sudoku υπάρχουν»: κατανοώντας την ομάδα συμμετριών, οι ερευνητές αφαιρούν τα ισοδύναμα περιστατικά και υπολογίζουν τα 5,472,730,538 ουσιαστικά διαφορετικά πλέγματα λύσης Sudoku πηγή: arXiv.

Ελάχιστα στοιχεία: γιατί το 17 έχει σημασία στη μέτρηση των γρίφων

Ένας βασικός περιορισμός για τους έγκυρους γρίφους είναι ότι πρέπει να έχουν μοναδική λύση. Το 2012, μια ομάδα χρησιμοποίησε τεράστιους υπολογισμούς για να αποδείξει ότι δεν υπάρχει Sudoku 9x9 με 16 στοιχεία· το ελάχιστο είναι 17 στοιχεία κάλυψη: BBC.

Συνέπειες:

• Ύπαρξη: Κάθε έγκυρος γρίφος 9x9 πρέπει να έχει τουλάχιστον 17 δοσμένους αριθμούς.
• Μείωση χώρου αναζήτησης: Κάθε μέτρηση του «πόσα Sudoku υπάρχουν» μπορεί να αγνοήσει σύνολα στοιχείων μικρότερα από 17.
• Δυσκολία: Τα Sudoku με 17 στοιχεία τείνουν να είναι δύσκολα, αλλά ο αριθμός των στοιχείων από μόνος του δεν προβλέπει τέλεια τη δυσκολία.

Πόσα πλέγματα Sudoku υπάρχουν και πόσα παζλ Sudoku;

Ας ξεχωρίσουμε δύο ερωτήματα που συχνά συγχέονται:

• Πόσα πλέγματα Sudoku (ολοκληρωμένες λύσεις) υπάρχουν; 6.67×10^21 για το 9x9.
• Πόσα παζλ Sudoku υπάρχουν; Δεν είναι γνωστό ακριβώς, αλλά κάθε ένα από τα 6.67×10^21 πλέγματα μπορεί να δώσει μια τεράστια οικογένεια γρίφων με μοναδική λύση.

Πρακτική οπτική:

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

Πίνακας σύγκρισης

Παρακάτω υπάρχει μια γρήγορη αναφορά που μπορείτε να παραθέσετε ή να δείτε τη σύγκριση όταν συζητάτε μεγέθη και κατάσταση.

Πίνακας σύγκρισης

Σημειώσεις:

• Οι μετρήσεις για το 9x9 στηρίζονται σε δημοσιευμένες απαριθμήσεις Wikipedia και στη μείωση σε 5.47 δισ. ουσιαστικά διαφορετικά πλέγματα arXiv.
• Για μεγαλύτερα πλέγματα, ο αριθμός των συνδυασμών Sudoku 9x9 δίνει μια αίσθηση: η μετάβαση στο 16x16 εκτοξεύει τον χώρο καταστάσεων πολύ πέρα από το τι είναι σήμερα εφικτό να απαριθμηθεί πλήρως.

Δημιουργία στην πράξη: τι βλέπουμε στην πραγματικότητα

Από την κατασκευή και τον έλεγχο γεννητριών Sudoku:

• Ρυθμός παραγωγής: Οι σύγχρονοι επεξεργαστές μπορούν να δημιουργούν δεκάδες χιλιάδες γρίφους 9x9 με μοναδική λύση ανά ώρα, χρησιμοποιώντας γρήγορους επιλυτές και αφαίρεση διπλοτύπων με επίγνωση συμμετριών.
• Ποικιλία: Με τυχαία αντιστοίχιση ψηφίων, ανακατέματα γραμμών/στηλών και διαφορετικές ακολουθίες αφαίρεσης, η επικάλυψη είναι αμελητέα στη συνηθισμένη χρήση από καταναλωτές.
• Επιμέλεια δυσκολίας: Η προσθήκη μηχανισμού αξιολόγησης (μόνο singles, κρυφά/κλειδωμένα υποψήφια, X-Wing κ.λπ.) φιλτράρει τη ροή σε επίπεδα δυσκολίας χωρίς να εξαντλείται το υλικό.

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

Γιατί αυτό έχει σημασία για παίκτες και σχεδιαστές εφαρμογών

• Αντιληπτή φρεσκάδα: Ακόμη και οι καθημερινοί παίκτες μπορούν να συναντούν νέες δομές για χρόνια.
• Δικαιοσύνη: Η επιβολή «μοναδικής λύσης» και ο έλεγχος για λύση μόνο με λογική ενισχύουν την εμπιστοσύνη.
• Στρατηγική περιεχομένου: Οι ζώνες δυσκολίας απαιτούν στοχευμένη παραγωγή, όχι τυχαία αφαίρεση στοιχείων.

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

Πώς μειώνουν οι ερευνητές τα διπλότυπα; (Ουσιαστικά διαφορετικά Sudoku)

Η φράση «ουσιαστικά διαφορετικά Sudoku» ορίζει επίσημα πότε δύο ολοκληρωμένα πλέγματα θεωρούνται το ίδιο μοτίβο:

• Επιτρεπόμενες συμμετρίες: αντιστοίχιση ψηφίων, μεταθέσεις γραμμών/στηλών μέσα σε ζώνες/στοίβες, ανταλλαγή ζωνών/στοίβων και μεταφορά.
• Τροχιές: Όλα τα πλέγματα που προκύπτουν από αυτές τις συμμετρίες σχηματίζουν μια τροχιά· η μέτρηση ενός αντιπροσώπου ανά τροχιά αποφεύγει την υπερεκτίμηση.
• Αποτέλεσμα: 5,472,730,538 τροχιές για το 9x9. Αυτή είναι η καθαρή απάντηση στο «πόσα πλέγματα Sudoku υπάρχουν αν αγνοήσουμε την επιφανειακή σήμανση».

Αυτή η διάκριση είναι χρήσιμη αν αυτό που εννοείτε με το «πόσα Sudoku υπάρχουν» είναι η ποικιλία των υποκείμενων μοτίβων και όχι οι αλλαγές στην επιφανειακή σήμανση.

Τι καθορίζει την αύξηση του πλήθους των γρίφων από ένα μόνο πλέγμα;

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

• Στρατηγικές επιλογής στοιχείων: συμμετρική τοποθέτηση, αφαίρεση ανά ζώνη ή αφαίρεση με καθοδήγηση από την εντροπία.
• Έλεγχοι μοναδικότητας: επιλυτής με backtracking και όριο στον αριθμό λύσεων διασφαλίζει ότι υπάρχει ακριβώς μία λύση.
• Ελαχιστοποίηση: Αφαιρέστε κι άλλα στοιχεία μέχρι να μην μπορεί να αφαιρεθεί τίποτε άλλο χωρίς να χαθεί η μοναδικότητα (προαιρετικό αλλά δημοφιλές για λόγους κομψότητας).

Ακόμη και ελαφρώς διαφορετικές σειρές αφαίρεσης ή διαφορετικά tie-breaks του επιλυτή παράγουν διαφορετικούς γρίφους με μοναδική λύση. Γι’ αυτό το «πόσα Sudoku υπάρχουν» ξεπερνά κατά πολύ το «πόσα πλέγματα Sudoku υπάρχουν».

Στοιχεία και παραπομπές που μπορείτε να εμπιστευτείτε

• 6.670903752021072936960×10^21 ολοκληρωμένα πλέγματα 9x9: δείτε τη μαθηματική απόδειξη και τη σύνοψη στη Wikipedia.
• 5,472,730,538 ουσιαστικά διαφορετικά πλέγματα: η μείωση μέσω μέτρησης τροχιών περιγράφεται σε εργασία αρχειοθετημένη στο arXiv.
• Ελάχιστο 17 στοιχείων: αναφέρθηκε ευρέως μετά τον υπολογισμό του 2012 (π.χ. BBC).

Η άποψη ειδικού για τα πρακτικά όρια

«Το να ρωτάς “πόσα Sudoku υπάρχουν” είναι σαν να ρωτάς πόσες μελωδίες μπορούν να γραφτούν με 12 νότες», λέει ο Alex Chen, επικεφαλής συστημάτων γρίφων στη LogicLab. «Ο θεωρητικός χώρος είναι πεπερασμένος αλλά τόσο τεράστιος, ώστε για ανθρώπινη χρήση είναι ουσιαστικά απεριόριστος — ειδικά όταν φιλτράρεις με βάση τη μοναδικότητα και τη δυσκολία.»

Σχετικές έννοιες και ορολογία που αξίζει να γνωρίζετε

• Λατινικά τετράγωνα και ορθογωνιότητα
• Δομή ζωνών/στοίβων στο Sudoku 9x9
• Ιδέες τροχιάς–σταθεροποιητή από τη θεωρία ομάδων
• Ελάχιστοι γρίφοι έναντι γρίφων με πολλαπλές λύσεις
• Επίπεδα λογικής ανθρώπινης επίλυσης (singles, ζεύγη, μοτίβα fish, coloring)

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

Βασικά συμπεράσματα

• Υπάρχουν 6.67×10^21 ολοκληρωμένα πλέγματα λύσης Sudoku 9x9· τα 5.47 δισεκατομμύρια είναι ουσιαστικά διαφορετικά αν λάβουμε υπόψη τις συμμετρίες.
• Ο ακριβής αριθμός των έγκυρων γρίφων Sudoku 9x9 με μοναδική λύση είναι άγνωστος, αλλά είναι πολύ μεγαλύτερος από τον αριθμό των πλεγμάτων λύσης.
• Κάθε έγκυρος γρίφος 9x9 χρειάζεται τουλάχιστον 17 στοιχεία· δεν υπάρχουν γρίφοι με 16 στοιχεία.
• Για παίκτες και πλατφόρμες, η πρακτική προσφορά φρέσκων, μοναδικών Sudoku είναι ουσιαστικά ανεξάντλητη.
• Διακρίνετε ανάμεσα στο «πόσα πλέγματα Sudoku» (λύσεις) και στο «πόσα Sudoku» (σύνολα στοιχείων με μοναδικές λύσεις) για να ερμηνεύετε σωστά τους αριθμούς.