Ένας γρίφος που στηρίζεται στα Λατινικά Τετράγωνα

Οι κανόνες είναι απλοί. Οι γρίφοι μπορεί να είναι αρκετά προκλητικοί και μερικές φορές εθιστικοί. Εκατομμύρια ανθρώπων στην Ιαπωνία, τη Μεγάλη Βρετανία, και σε πολλά άλλα μέρη του κόσμου διαπιστώνουν πως η μέρας τους είναι ανούσια εάν δεν επιλύσουν την τελευταία έκδοση ενός απλού γρίφου, που ονομάζεται sudoku. Το Sudoku σημαίνει στα ιαπωνικά "μονός αριθμό". Ο γρίφος αποτελείται χαρακτηριστικά από ένα πλέγμα 9 x 9. Μερικά από τα κενά περιέχουν αριθμούς ενώ τα περισσότερα είναι άδεια. Στόχος είναι να συμπληρώσουμε τα κενά με τα ψηφία από το 1 έως το 9 έτσι ώστε κάθε σειρά, κάθε στήλη, και καθένα από τα επιμέρους 3 x 3 τετράγωνα που αποτελούν το πλέγμα να περιέχουν μόνο ένα από τα εννέα ψηφία. Πρόκειται βασικά για γρίφο λογικής, και δεν εμπλέκονται τα μαθηματικά στην επίλυσή του. Τα ψηφία θα μπορούσαν να είναι εννέα διαφορετικά γράμματα, σχήματα ή χρώματα. Βέβαια υπάρχουν τα μαθηματικά και η πληροφορική, που ασχολούνται με την ανάλυση των γρίφων και τη δημιουργία προγραμμάτων για την άμεση επίλυσή τους. Ένα πλέγμα sudoku είναι μια ειδική περίπτωση ενός μαθηματικού αντικειμένου, που ονομάζεται Λατινικό Τετράγωνο. Ένα λατινικό τετράγωνο αποτελείται από σύνολα αριθμών, από το 1 έως το ν που τοποθετούνται σε ένα τετραγωνικό σχέδιο έτσι ώστε καμία σειρά ή στήλη να μην περιέχει τον ίδιο αριθμό δύο φορές. Σειρά Αριθμός Λατινικών Τετραγώνων 1 1 2 2 3 12 4 576 5 161280 6 812851200 7 61479419904000 8 108776032459082956800 Υπάρχουν δύο Λατινικά Τετράγωνα της σειράς 2 (ν = 2), 12 της σειράς 3 και 576 της σειράς 4. Ανάλογα με τον αριθμό των ενδείξεων και το μέγεθος του πλέγματος, οι γρίφοι sudoku μπορούν να είναι εξαιρετικά δύσκολοι ως προς τη λύση τους. Οι Τακαγιούκι Γιάτο και Τακαχίρο Σέτα, του πανεπιστημίου του Τόκιο έχουν αποδείξει ότι η επίλυση των γρίφων sudoku ν x ν ανήκει γενικά σε μια κατηγορία υπολογιστικών προβλημάτων που περιγράφονται ως πρόβλημα - NP. Ένα πρόβλημα NP είναι αυτό για το οποίο είναι σχετικά εύκολο να ελεγχθεί εάν μια δεδομένη απάντηση είναι σωστή αλλά μπορεί να απαιτήσει πολύ χρόνο για να λυθεί από οποιαδήποτε άμεση διαδικασία, ειδικά καθώς το ν γίνεται όλο και μεγαλύτερο. Πράγματι, όσο αυξάνει ο αριθμός ν, αυξάνει εκθετικά ο χρόνος επίλυσης του γρίφου με τη χρήση υπολογιστή. Κ Ο Ρ Η Ο Κ Η Ρ Η Ρ Κ Ο Ρ Η Ο Κ Τα λατινικά τετράγωνα έχουν τις ρίζες τους στους μεσαιωνικούς χρόνους. Ο Λέοναρντ Ούλερ (1707 - 1783) ήταν ο πρώτος μαθηματικός που τα μελέτησε συστηματικά. Εισήγαγε έναν ιδιαίτερο τύπο λατινικού τετραγώνου (Ελληνο - Ρωμαϊκό Τετράγωνο) ως ένα νέο είδος "μαγικού τετραγώνου". Όπως στο sudoku, στις σειρές και στις στήλες ενός λατινικού τετραγώνου δεν είναι απαραίτητο να τοποθετηθούν αριθμοί. Οποιοιδήποτε σύνολο ν διαφορετικών συμβόλων, μπορεί να χρησιμοποιηθεί. Στο διπλανό πίνακα φαίνεται ένα λατινικό τετράγωνο 4 x 4 βασισμένο στη λέξη "ΚΟΡΗ". Ο πρόσθετος περιορισμός σε έναν γρίφο sudoku 9 x 9 είναι τα μικρότερα τετράγωνα των 3 x 3 που περιέχουν επίσης κάθε ένα από τα εννέα ψηφία μειώνοντας τον τεράστιο αριθμό των πιθανών 9 x 9 λατινικών τετραγώνων σε έναν μικρότερο αλλά τεράστιο αριθμό: 6.670.903.752.021.072.936.960. Λύνοντας ένα γρίφο sudoku είναι ισοδύναμο με το να "χρωματίζουμε" κατάλληλα μία γραφική παράσταση: σειρά σημείων (κορυφές) και γραμμών (άκρες). Σε αυτήν την περίπτωση, η γραφική παράσταση έχει 81 κορυφές, μία για κάθε κελί του πλέγματος. Ανάλογα με το γρίφο, μόνο ορισμένα ζευγάρια κορυφών ενώνονται με κάθε άκρη. Δεδομένου ότι μερικές κορυφές έχουν κάποιο "χρώμα" (επιλεγμένο από εννέα δυνατότητες), το πρόβλημα είναι να "χρωματιστούν" οι υπόλοιπες κορυφές έτσι ώστε οποιεσδήποτε δύο κορυφές που ενώνονται από μια άκρη να μην έχουν το ίδιο "χρώμα". Yato, T. & Seta, Τ.: Complexity and completeness of finding another solution and its application to puzzles (αρχείο .pdf) London Times sudoko page Γρίφοι sudoku Προγράμματα για την επίλυση του γρίφου Λατινικά Τετράγωνα

sciencenews.gr

Δημοσίευση: Φεβρουαρίου 09, 2010