Εγκυκλοπαίδεια του Sudoku · Μαθηματικά και πληροφορική

Τα μαθηματικά του Sudoku

Ενημερώθηκε στις 2026-10-05

Ένα λατινικό τετράγωνο με επιπλέον τετράγωνα

Σε ένα λατινικό τετράγωνο, κάθε σύμβολο εμφανίζεται μία φορά σε κάθε γραμμή και κάθε στήλη. Ένα συμπληρωμένο Sudoku είναι ένα λατινικό τετράγωνο μεγέθους 9 με μία ακόμη συνθήκη: καθένα από τα εννέα τετράγωνα 3×3 περιέχει επίσης κάθε ψηφίο μία φορά.

Πηγές: Wikipedia: Latin square

Πόσα πλέγματα υπάρχουν

Οι Μπέρτραμ Φελγκενχάουερ (Bertram Felgenhauer) και Φρέιζερ Τζάρβις (Frazer Jarvis) μέτρησαν τα συμπληρωμένα πλέγματα 9×9 το 2005: υπάρχουν 6.670.903.752.021.072.936.960, περίπου 6,67 × 10²¹. Πολλά από αυτά είναι το ίδιο πλέγμα σε διαφορετική μορφή. Αν μετρήσουμε δύο πλέγματα ως ένα όταν μπορούμε να μετατρέψουμε το ένα στο άλλο αλλάζοντας την αντιστοίχιση των ψηφίων, περιστρέφοντας ή κατοπτρίζοντας το πλέγμα ή αναδιατάσσοντας γραμμές και στήλες με τρόπους που διατηρούν την εγκυρότητά του, απομένουν 5.472.730.538 ουσιαστικά διαφορετικά πλέγματα. Τον αριθμό αυτό υπολόγισαν οι Εντ Ράσελ (Ed Russell) και Φρέιζερ Τζάρβις.

Πηγές: Felgenhauer and Jarvis, Enumerating possible Sudoku grids (2005), OEIS A107739: number of Sudoku grids, Wikipedia: Mathematics of Sudoku

Το ελάχιστο των 17 στοιχείων

Κανένα τυπικό Sudoku 9×9 με 16 ή λιγότερα δεδομένα ψηφία δεν έχει ακριβώς μία λύση. Οι Γκάρι ΜακΓκουάιρ (Gary McGuire), Μπάστιαν Τούγκεμαν (Bastian Tugemann) και Ζιλ Σιβαριό (Gilles Civario) το έδειξαν με εξαντλητική αναζήτηση μέσω υπολογιστή και ανακοίνωσαν το αποτέλεσμα τον Ιανουάριο του 2012. Το 17 είναι το ελάχιστο, αλλά δεν αποτελεί εγγύηση: πολλά πλέγματα με 17 δεδομένα ψηφία εξακολουθούν να έχουν περισσότερες από μία λύσεις.

Πηγές: McGuire, Tugemann and Civario, There is no 16-Clue Sudoku (arXiv 1201.0749)

Το Sudoku ως χρωματισμός γραφήματος

Σχεδίασε μία κορυφή για καθένα από τα 81 κελιά και σύνδεσε δύο κορυφές όποτε τα κελιά τους ανήκουν στην ίδια γραμμή, στήλη ή τετράγωνο. Αυτό το γράφημα Sudoku έχει 810 ακμές και κάθε κορυφή έχει ακριβώς 20 γείτονες. Η επίλυση του γρίφου σημαίνει επέκταση του χρωματισμού που ορίζουν τα δεδομένα ψηφία, ώστε οι συνδεδεμένες κορυφές να μην έχουν ποτέ το ίδιο χρώμα. Χρειάζονται τουλάχιστον εννέα χρώματα, επειδή κάθε γραμμή, στήλη και τετράγωνο είναι μια ομάδα εννέα κορυφών που συνδέονται όλες μεταξύ τους, και κάθε συμπληρωμένο πλέγμα δείχνει ότι τα εννέα αρκούν.

Πηγές: Wikipedia: Sudoku graph

Δύσκολο γενικά, γρήγορο για τα 9×9

Για πλέγματα Sudoku που μπορούν να μεγαλώνουν χωρίς όριο (n²×n² με τετράγωνα n×n), η απόφαση αν ένα μερικώς συμπληρωμένο πλέγμα μπορεί να ολοκληρωθεί είναι πρόβλημα NP-πλήρες, ένα αποτέλεσμα που δημοσίευσαν οι Τακαγιούκι Γιάτο (Takayuki Yato) και Τακαχίρο Σέτα (Takahiro Seta) το 2003. Τα αποδοτικά προγράμματα υπολογιστή συνήθως λύνουν τους συνηθισμένους γρίφους 9×9 σε κλάσμα του δευτερολέπτου, αν και ο χρόνος εξαρτάται από το πρόγραμμα, τον υπολογιστή και τον γρίφο.

Πηγές: Wikipedia: Mathematics of Sudoku, Wikipedia: Sudoku solving algorithms, Peter Norvig: Solving Every Sudoku Puzzle

Δες επίσης

Πηγές

Όλα τα άρθρα →