Η απόδειξη των 17

Αντίθετα με το σταυρόλεξο, οι πιθανές λύσεις του οποίου είναι τόσο περισσότερες όσο μεγαλύτερες είναι οι διαστάσεις του σταυρόλεξου και όσο περισσότερες γλώσσες χρησιμοποιούμε, το sudokou έχει ακριβώς 6.670.903.752.021.072.936.960 δυνατές λύσεις. 

Για να βρούμε μία από αυτές, χρειαζόμαστε τη βοήθεια του δημιουργού του κάθε προβλήματος-γρίφου. Η βοήθεια αυτή δίνεται με τη μορφή μιας ομάδας από τα ψηφία 1-9 της λύσης, τα οποία εμφανίζονται εξ' αρχής σε ορισμένα από τα 81 τετραγωνάκια.

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

Από καιρό υπήρχαν γνωστές λύσεις sudokou που είναι μοναδικές για 17 συμπληρωμένα τετραγωνάκια, ενώ δεν υπήρχε καμία γνωστή που να δίνει μοναδική λύση με συμπληρωμένα 16. Ετσι είχε δημιουργηθεί η άποψη ότι για να έχει ένα πρόβλημα sudokou μία μοναδική λύση χρειάζεται να δίνονται τουλάχιστον 17 συμπληρωμένα τετραγωνάκια.

Μια ομάδα των ιρλανδών μαθηματικών με επικεφαλής τον Gary McGuire απέδειξε ότι αυτή η υπόθεση είναι σωστή, αφού κατάφερε να μειώσει δραστικά τον τεράστιο αριθμό των δυνατών λύσεων, αφαιρώντας όλες τις περιπτώσεις που είναι ισοδύναμες.

Στη συνέχεια, η ομάδα προγραμμάτισε έναν ηλεκτρονικό υπερυπολογιστή με τέτοιον τρόπο ώστε να καταστεί δυνατό να διερευνηθεί αν έστω και ένα από τα 5,5 δισεκατομμύρια των υπολοίπων συνδυασμών, μπορεί να λυθεί μοναδικά με συμπληρωμένα μόνο 16 τετραγωνάκια. 

Το πρόγραμμα που έγραψε η ομάδα «έτρεξε» σε έναν υπερυπολογιστή Silicon Graphics, αποτελούμενο από 640 επεξεργαστές Intel Xeon, για 12 μήνες, από τον Ιανουάριο ως τον Δεκέμβριο του 2011. Το αποτέλεσμα ήταν ότι δεν εντοπίστηκε καμία λύση που να βρίσκεται με μοναδικό τρόπο, αν δοθούν συμπληρωμένα 16 μόνο τετραγωνάκια. 

Ετσι προκύπτει ότι ο ελάχιστος αριθμός των συμπληρωμένων τετραγώνων πρέπει να είναι 17, αφού για τον αριθμό αυτόν υπάρχουν ήδη γνωστά προβλήματα με μοναδικές λύσεις. (Σημ.: Στο internet θα βρείτε πολλές αναφορές όπου σαν απάντηση αναφέρεται ο αριθμός 16 και αυτό οφείλεται σε μια αρχική λάθος μετάφραση του αγγλικού κειμένου που στην συνέχεια «αντιγράφηκε» ασύστολα...)

Από τη σπαζοκεφαλιά στο γονιδίωμα

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

Τέτοια εφαρμογή είναι, για παράδειγμα, η ανάλυση της ακολουθίας των γονιδίων στο DNA του ανθρώπου και των άλλων ζώων και φυτών. Συγκεκριμένα, οι συσκευές ανάλυσης DNA του μέλλοντος προβλέπεται ότι θα είναι ικανές να αναλύουν το γονιδίωμα δεκάδων χιλιάδων δειγμάτων ταυτόχρονα, χάρη σε μια μορφή στατιστικής προσέγγισης που συνδέεται με το πρόβλημα επίλυσης ενός προβλήματος sudokou. Για τον λόγο αυτόν άλλωστε ονομάζεται και DNA-Sudoku.

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