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

Για πάρα πολλά χρόνια το σταυρόλεξο ήταν μια πολύ διαδεδομένη διανοητική απασχόληση που σχεδόν όλα τα έντυπα, εφημερίδες και περιοδικά, προσέφεραν στους αναγνώστες τους. Σήμερα το ενδιαφέρον των αναγνωστών έχει αρχίσει να τραβάει ένα άλλο είδος «σπαζοκεφαλιάς», το σουντόκου (sudoku), που ζητάει από τον λύτη να μαντέψει τη θέση αριθμών και όχι λέξεων. Το σουντόκου φαίνεται ότι ταιριάζει περισσότερο στο εφαρμοσμένο πνεύμα της εποχής, αφού απαιτεί κυρίως συνδυαστικό μυαλό και όχι εγκυκλοπαιδικές γνώσεις. Γι’ αυτό και έχει αποκτήσει φανατικούς οπαδούς, όχι μόνο μεταξύ των καθημερινών αναγνωστών των εντύπων αλλά και μεταξύ των επιστημόνων. Ετσι μια ομάδα μαθηματικών από το Πανεπιστήμιο του Δουβλίνου προσπάθησε να απαντήσει στο ερώτημα «ποιο είναι το ελάχιστο πλήθος μονοψήφιων αριθμών που χρειάζεται να τοποθετηθεί σε ένα σουντόκου, έτσι ώστε το παιχνίδι να έχει μια μοναδική λύση;». Υστερα από έναν χρόνο υπολογισμών σε έναν ηλεκτρονικό υπερυπολογιστή, κατέληξαν ότι χρειάζονται τουλάχιστον 17 αριθμοί. Η στρατηγική που ανέπτυξαν για τη λύση του προβλήματος αναμένεται να βοηθήσει σημαντικά σε άλλες, φαινομενικά ασύνδετες, περιοχές σύγχρονης ερευνητικής δραστηριότητας, όπως για παράδειγμα στην αποκρυπτογράφηση του DNA.

Κληρονομιά του Οϊλερ

Το σουντόκου, με τη μορφή που είναι γνωστό σήμερα, έχει πολύ σύντομη ιστορία, αφού παρουσιάστηκε για πρώτη φορά στο ευρύ κοινό από τον ιαπωνικό εκδοτικό οίκο Nicoli, ο οποίος ειδικεύεται σε πνευματικά παιχνίδια, μόλις το 1986. Στόχος του παιχνιδιού είναι να συμπληρωθούν τα 81 στοιχεία ενός πίνακα 9×9 (δηλαδή με 9 σειρές και 9 στήλες) με τους μονοψήφιους ακέραιους αριθμούς από το 1 ως το 9 με τέτοιον τρόπο ώστε ο ίδιος αριθμός να μην εμφανίζεται δύο φορές στην ίδια σειρά, στην ίδια στήλη ή στον καθένα από τους 9 υποπίνακες διαστάσεων 3×3 που περιέχονται στον «μεγάλο» πίνακα 9×9. Η βασική ιδέα του παιχνιδιού όμως είναι πολύ παλιά, αφού έχει αποτελέσει αντικείμενο δημοσιεύσεων του μεγάλου ελβετού μαθηματικού Οϊλερ (Euler), ήδη από τον 18ο αιώνα.

Αντίθετα με το σταυρόλεξο, οι πιθανές λύσεις του οποίου είναι τόσο περισσότερες όσο μεγαλύτερες είναι οι διαστάσεις του σταυρόλεξου και όσο περισσότερες γλώσσες χρησιμοποιούμε, το σουντόκου έχει ακριβώς 6.670.903.752.021.072.936.960 (δηλαδή περίπου 6,7 δισεκατομμύρια τρισεκατομμυρίων) δυνατές λύσεις. Για να βρούμε μία από αυτές, χρειαζόμαστε τη βοήθεια του δημιουργού του κάθε προβλήματος-γρίφου. Η βοήθεια αυτή δίνεται με τη μορφή μιας ομάδας από τα ψηφία 1-9, τα οποία έχουν προτοποθετηθεί σε ορισμένα από τα 81 τετραγωνάκια. Συνήθως δίνονται καμιά 25αριά, αλλά από την εποχή που πρωτοεμφανίστηκε το παιχνίδι εμφανίστηκε και το ερώτημα «ποιος είναι ο ελάχιστος αριθμός δοσμένων ψηφίων, έτσι ώστε το συγκεκριμένο πρόβλημα σουντόκου να έχει μόνο μία λύση;».

Το ερώτημα είναι αντίστοιχο με ένα απλό πρόβλημα πρόσθεσης στην αριθμητική. Αν γνωρίζουμε ότι δύο αριθμοί έχουν άθροισμα 10 και ο ένας από αυτούς είναι το 3, τότε το πρόβλημα έχει μόνο μία λύση: ο άλλος αριθμός είναι το 7. Αν όμως γνωρίζουμε ότι τρεις αριθμοί έχουν άθροισμα 10, τότε πρέπει να γνωρίζουμε τους δύο, αν θέλουμε το πρόβλημα να έχει μία μοναδική λύση. Αν γνωρίζουμε μόνο τον έναν, π.χ. το 2, τότε δυνατές λύσεις για τους υπόλοιπους δύο μπορεί να είναι τόσο το 3 με το 5, όσο και το 1 με το 7. Στο σουντόκου είναι εύκολο να δείξουμε ότι 7 ψηφία δεν είναι αρκετά για μία μοναδική λύση, αφού τα δύο εναπομένοντα (ως τα 9) ψηφία είναι δυνατό να αλλάξουν αμοιβαία θέση σε μια λύση, έτσι ώστε να δώσουν μια δεύτερη. Από καιρό υπήρχαν γνωστές λύσεις σουντόκου που είναι μοναδικές για 17 συμπληρωμένα τετραγωνάκια, ενώ δεν υπήρχε καμία γνωστή που να δίνει μοναδική λύση με συμπληρωμένα 16. Ετσι είχε δημιουργηθεί η άποψη ότι για να έχει ένα πρόβλημα σουντόκου μία μοναδική λύση χρειάζεται να δίνονται τουλάχιστον 17 συμπληρωμένα τετραγωνάκια. Η ομάδα των ιρλανδών μαθηματικών απέδειξε ότι αυτή η υπόθεση είναι σωστή, ο τρόπος που το κατάφεραν όμως είναι αξιοσημείωτος.

Ανεξάρτητες και «εξαρτημένες» λύσεις

{{{ moto }}}Κατ’ αρχάς μπορεί να δείξει κανείς ότι από τα περίπου 7 δισεκατομμύρια τρισεκατομμυρίων δυνατών λύσεων, «μόνο» οι 5.472.730.538 είναι ανεξάρτητες, αφού από κάθε λύση μπορούμε να πάρουμε μιαν άλλη, απλά εναλλάσσοντας τις θέσεις δύο γραμμών ή δύο στηλών ή εναλλάσσοντας τις θέσεις ενός ψηφίου, π.χ. του 1, με αυτές ενός άλλου, π.χ. του 3. Αλλά και αυτός ο αριθμός (5,5 δισεκατομμύρια περίπου) είναι πολύ μεγάλος, επειδή αν θέλουμε να ελέγξουμε το κατά πόσον καθεμία από αυτές τις λύσεις μπορεί να βρεθεί αν δοθούν μόνο 16 συμπληρωμένα τετραγωνάκια, απαιτείται να κάνουμε περίπου 34 τετράκις εκατομμύρια δοκιμές, αριθμός που μαθηματικά ισούται με όλους τους συνδυασμούς των 81 δυνατών θέσεων ανά ομάδες των 16.

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

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

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

Ο κ. Χάρης Βάρβογλης είναι καθηγητής του Τμήματος Φυσικής του ΑΠΘ.