Ποιος είναι ο ελάχιστος αριθμός γνωστών αριθμών για λύση στο Sudoku;


Μια από τις δυσκολότερες μαθηματικές σπαζοκεφαλιές με βάση το Sudoku φαίνεται πως κατάφερε να λύσει ένας Ιρλανδός μαθηματικός.

Το ερώτημα της συγκεκριμένης σπαζοκεφαλιάς είναι πολύ απλό: ποιος είναι ο ελάχιστος αριθμός θέσεων που πρέπει να είναι συμπληρωμένες από τηνα αρχή στο Sudoku ώστε να έχει το παιχνίδι μία και μοναδική λύση.
Μπορεί να φαίνεται απλό σαν ερώτημα, αλλά η εύρεση και η απόδειξη μιας λύσης ταλαιπώρησε ουκ ολίγους μαθηματικους εδώ και χρόνια, και για την οριστική  λύση επιστρατεύτηκε ένας υπερυπολογιστής ο οποίος μετά από αρκετές μέρες υπολογισμών έφτασε στο αποτελέσμα: 16. Τόσες είναι οι ελάχιστες θέσεις που πρέπει να είναι από την αρχή συμπληρωμένες στο Sudoku για να υπάρχει μοναδική λύση. 
Για όσους δεν τον γνωρίζουν, το Sudoku είναι ένα ιαπωνικό παιχνίδι υπολογισμού όπου ο παίκτης καλείται να συμπληρώσει έναν πίνακα διαστάσεων 9 x 9 χρησιμοποιώντας μόνο τους αριθμούς από το 1 έως το 9 με στόχο να μην επαναλαμβάνεται ο ίδιος αριθμός στην ίδια γραμμή, στην ίδια στήλη, ή στον ίδιο υποπίνακα 3 επί 3.
Για να ξεκινήσει το παιχνίδι, όμως, πρέπει να είναι συμπληρωμένες κάποιες θέσεις στον πίνακα από την αρχή. Φυσικά, όσο περισσότερες είναι οι συμπληρωμένες θέσεις, τόσο πιο εύκολη είναι λύση του παιχνίδιου. Συνήθως στα κλασικά παιχνίδια Sudoku δίνονται 25 συμπληρωμένοι αριθμοί.
Ωστόσο, υπήρχε η εικασία ότι ο ελάχιστος δυνατός αριθμός γνωστών θέσεων στον Sudoku ήταν 16. Μέχρι σήμερα όμως κανείς δεν είχε φτιάξει ένα Sudoku με 16 γνωστούς αριθμούς, το οποίο να έχει μία και μοναδική λύση. Άλλωστε για να επιβεβαιώσει κανείς την εικασία θα έπρεπε να λύσει όλα τα πιθανά παιχνίδια με 16 συμπληρωμένες θέσεις, πράγμα που θα χρειαζόταν αρκετά χρόνια.
Ο ερευνητής Γκάρι ΜακΓκουάιρ του Πανεπιστημιακού Κολεγίου του Δουβλίνου βρήκε μια εναλλακτική για να απλοποιήσει το πρόβλημα. Αντί να επιλύσει όλα τα πιθανά παιχνίδια με 16 γνωστούς αριθμούς, τα ομαδοποίησε βρίσκοντας εκείνες τις διατάξεις οι οποίες είναι ισοδύναμες και οδηγούν σε πολλαπλές λύσεις. Στη συνέχεια, έβαλε τον υπερυπολογιστή να αποκλείσει την ύπαρξη ενός παζλ με 16 γνωστούς αριθμούς  που να μπορεί να αποκλείσει όλες τις παραπάνώ διατάξεις. Μετά από αρκετές μέρες υπολογισμού, ο υπερυπολογιστής έφτασε στο ζητούμενο, αποδεικνύοντας την εικασία...


iefimerida
Επισκεφθείτε την νέα μας διεύθυνση www.alexiptoto.com
Generated image

 
Design by Free WordPress Themes | Bloggerized by Lasantha - Premium Blogger Themes | Affiliate Network Reviews