1793 - Sudoku vs Νόηση

Ν. Λυγερός

Ιστορικά δεδομένα

Ως παίγνιο, το Sudoku δημιουργήθηκε το 1979 από τον Howard Garns. Ως ονομασία, το Sudoku διαμορφώνεται το 1984 από τον Nikoli που χρησιμοποιεί την ιαπωνική έκφραση Suji wa dokushin ni kagiru που σημαίνει το ψηφίο πρέπει να είναι μοναδικό, για να το καθορίσει. Μετατρέπεται σε Sudoku ακολουθώντας την παράδοση που κάνει χρήση του πρώτου Kanji για να δημιουργήσει μια σύντομη λέξη. Το 1986, οι κανόνες του παιγνίου αλλάζουν έτσι ώστε το ανώτατο όριο των αποκαλύψεων να είναι 30 και οι γρίλες να είναι συμμετρικές. Το 1989, βγαίνει το πρώτο λογισμικό για Commodore 64 που παράγει Sudoku. Το 1995, ο Yoshimits Kanai εκδίδει λογισμικό για το Macintoch και το 1996 για το Palm. To 2005, το Sudoku γνωρίζει διεθνή επιτυχία και γίνεται πια μόδα. Η μελέτη μας έχει ως σκοπό την αναγνώριση του υπόβαθρου αυτής της παγκόσμιας μόδας. Για να εξετάσουμε το φαινόμενο Sudoku, χρησιμοποιούμε μαθηματικά και γνωστικά εργαλεία.

Μαθηματικά δεδομένα

Ως μαθηματική οντότητα, το Sudoku είναι μια εκφυλισμένη περίπτωση των λατινικών τετραγώνων. Ως γενικό πρόβλημα, ανήκει στην κατηγορία NP-complet. Αυτό σημαίνει, όσο δεν υπάρχει απόδειξη του NP=P, ότι δεν υπάρχει πολυωνιμικός αλγόριθμος για να λύσει Sudoku δίχως όριο τάξης. Όμως για μικρές τάξεις, το Sudoku δεν είναι υπολογιστικά δύσκολο. Το 2005, ο Bertram Felgenhauer και ο Franzer Jarvis απέδειξαν ότι υπάρχουν 6.670.903.752.021.072.936.960 διαφορετικά Sudoku. Στην πραγματικότητα, αυτός ο αριθμός που ισούται με 9!*72²*7²* 27704267971 δεν αντιπροσωπεύει την πολυπλοκότητα του Sudoku ως παιγνίου διότι δεν κάνει χρήση των συμμετριών του προβλήματος. Ο Franzer Jarvis και o Ed Russel απέδειξαν ότι οι μη ισομορφικές λύσεις είναι 5.472.730.538. Αυτός ο αριθμός είναι υπολογιστικά πολύ μικρός και επιτρέπει μια ολοκληρωτικη ανάλυση του προβλήματος. Πρακτικά αυτό σημαίνει ότι ένας κλασικός αλγόριθμος του τύπου backtracking λύνει το Sudoku και το ίδιο ισχύει και για έναν πεπερασμένο αυτόματο που γνωρίζει αυτό που ονομάζουμε το δέντρο του παιγνίου. Η επίλυση του Sudoku ερμηνεύεται στη θεωρία γραφημάτων ως ένα ειδικό πρόβλημα χρωματισμού κορυφών. Μπορούμε όμως να εξετάσουμε την επίλυση και ως ένα πρόβλημα δυναμικού προγραμματισμού. Και στις δύο εκδοχές, αυτό σημαίνει ότι η στρατηγική είναι μόνο και μόνο τακτική. Με άλλα λόγια, είμαστε στο πλαίσιο της θεωρίας αποφάσεων, δηλαδή σ’έναν ειδικό τομέα της θεωρίας παιγνίων. Επιπλέον, οι κανόνες του Sudoku επιτρέπουν τη χρήση των μεθόδων X-wing και Swordfish. Συνεπώς, ο προγραμματισμός της επίλυσης του Sudoku δεν είναι μόνο κλασικός αλλά και απλός. Όπως ήδη το γράψαμε, ακόμα και ένας αλγόριθμος του τύπου backtracking που δεν χρησιμοποιέι τη δομή του προβλήματος παρά μόνο σταδιακά, λύνει το Sudoku σε χρόνο της τάξης του δευτερολέπτου. Η επίλυση μπορεί να γίνει και με τον λογικό προγραμματισμό με γλώσσες του τύπου LispProlog ή Scheme. Σε αυτήν την περίπτωση, χρησιμοποιείται όλη η δομή του προβλήματος για να εξεταστούν οι λιγότερες πιθανές περιπτώσεις. Επιπλέον, όπως υπάρχει εξ ορισμού μοναδική λύση, η επίλυση είναι πάντα εφικτή. Αν θέλουμε όμως έναν πιο αποτελεσματικό αλγόριθμο, τότε η μεθοδολογία του Donald Knuth με χρήση καταλόγων διπλά αλυσιδωτών είναι ιδανική. Σε αυτήν την περίπτωση, ο χρόνος της επίλυσης του Sudoku είναι της τάξης του χιλιοστού του δευτερολέπτου.

Γνωστικά δεδομένα

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

Συμπεράσματα

Τα μαθηματικά αποδεικνύουν την ελάχιστη πολυπλοκότητα του Sudoku. Η γνωστική ανάλυση αποδεικνύει το ελάχιστο βάθος του. Η επίλυση του Sudoku είναι μεθοδολογικά ισόμορφη με ένα απλό πρόβλημα γραμμικής άλγεβρας. Συνεπώς, δεν μπορεί να προσφέρει τίποτα παραπάνω από μια άσκηση. Άρα η εξάσκηση δεν αυξάνει οποιαδήποτε νοητική ικανότητα. Αντιθέτως, με την παρόδο του χρόνου, ο εγκέφαλος λειτουργεί αυτόματα και δεν ερευνά έξυπνες λύσεις. Αντιλαμβανόματε, λοιπόν, ότι το Sudoku είναι μόνο και μόνο φαινομενικά ένα παίγνιο σκέψης. Πράγμα το οποίο το κάνει ιδανικό για μια κοινωνία του θεάματος. Το Sudoku εκτός από το να εξασφαλίσει μια εύκολη διασκέδαση, παρουσιάζει όλες τις αναγκαίες προδιαγραφές για να γίνει φαινόμενο μόδας. Είναι απλό, ενώ φαίνεται δύσκολο. Είναι αυτόματο, ενώ φαίνεται έξυπνο. Δεν λειτουργεί με αριθμούς, ενώ φαίνεται αριθμητικό. Όμως όλο αυτό το πλαίσιο προκαλεί ένα ερώτημα : Ποιος είναι ο λόγος της προώθησής του εφόσον δεν είναι αυτό που φαίνεται; Ας ελπίσουμε ότι είναι μόνο μια μόδα διότι και οι μόδες έχουν ένα καλό στοιχείο, περνούν.