Λύση στο 150 ετών σκακιστικό πρόβλημα των n-queens δίνει ο μαθηματικός του Χάρβαρντ Michael Simkin, μετά από σχεδόν πέντε χρόνια συνεχούς «μάχης» με τις εξισώσεις.
Το σκάκι μοιάζει ένα απλό παιχνίδι, με 64 μαύρα ή άσπρα τετράγωνα, 16 πιόνια ανά πλευρά και δύο ανταγωνιστές που αγωνίζονται για την κατάκτηση.
Το παιχνίδι ωστόσο, προσφέρει απίστευτα πολύπλοκες δυνατότητες, θέτοντας πλείστες προκλήσεις για τους θεωρητικούς και τους μαθηματικούς του σκακιού, που μπορεί να μείνουν άλυτες για δεκαετίες ή και αιώνες.
Τον Ιούλιο του 2021, μια τέτοια πρόκληση επιλύθηκε τελικά, τουλάχιστον μέχρι ένα σημείο. Ο μαθηματικός Michael Simkin, από το Πανεπιστήμιο του Χάρβαρντ στη Μασαχουσέτη, εστίασε στο πρόβλημα των n-queens που απασχολούσε τους ειδικούς από τη δεκαετία του 1840.
Όσοι γνωρίζουν από σκάκι, θα ξέρουν ότι η βασίλισσα είναι το πιο δυνατό πιόνι στο παιχνίδι, ικανή να μετακινηθεί σε οποιοδήποτε αριθμό τετραγώνων προς οποιαδήποτε κατεύθυνση. Το πρόβλημα των n-queens ωστόσο, θέτει το εξής ερώτημα: «Με έναν ορισμένο αριθμό βασίλισσες (n), πόσες κινήσεις είναι δυνατές όταν οι βασίλισσες απέχουν αρκετά μεταξύ τους, ώστε καμία από αυτές να μην μπορεί να κερδίσει καμία από τις άλλες»;
Για οκτώ βασίλισσες σε ένα τυπικό σκάκι 8 x 8, η απάντηση είναι 92, αν και οι περισσότερες από αυτές είναι περιστρεφόμενες ή ανακλώμενες παραλλαγές μόλις 12 θεμελιωδών λύσεων.
Τι γίνεται όμως με 1.000 βασίλισσες σε ένα σκακιστικό πίνακα διαστάσεων 1.000 x 1.000 τετραγώνων; Τι γίνεται με ένα εκατομμύριο βασίλισσες; Η κατά προσέγγιση λύση του Simkin στο πρόβλημα είναι (0,143n) n – ο αριθμός των βασίλισσων πολλαπλασιασμένος επί 0,143, αυξημένος στη δύναμη του n.
Αυτό που απασχολεί δεν είναι η ακριβής απάντηση, αλλά πόσο πιο κοντά έρχεται κανείς στην κατανόηση της λύσης. Με ένα εκατομμύριο βασίλισσες, ο αριθμός εμφανίζεται ως αριθμός με πέντε εκατομμύρια ψηφία μετά από αυτό. Επομένως δεν το αναπαράγουμε σε αυτό το άρθρο.
Ποικιλία προσεγγίσεων και τεχνικών
Χρειάστηκαν σχεδόν πέντε χρόνια για να καταλήξει ο Simkin με την εξίσωση, με μια ποικιλία προσεγγίσεων και τεχνικών που χρησιμοποιήθηκαν και μερικά εμπόδια στο δρόμο προς μια λύση. Τελικά ο μαθηματικός μπόρεσε να υπολογίσει τα κάτω και τα άνω όρια των πιθανών λύσεων χρησιμοποιώντας διαφορετικές μεθόδους, βρίσκοντας ότι σχεδόν ταιριάζουν.
«Αν μου έλεγες ότι θέλω να βάλεις τις βασίλισσές σου με αυτόν και τον τρόπο στον πίνακα, τότε θα μπορούσα να αναλύσω τον αλγόριθμο και να σου πω πόσες λύσεις υπάρχουν που ταιριάζουν με αυτόν τον περιορισμό», λέει ο Simkin.
«Σε τυπικούς όρους, μειώνει το πρόβλημα σε πρόβλημα βελτιστοποίησης»
Ο Simkin και ο συνάδελφός του Zur Luria, από το Ελβετικό Ομοσπονδιακό Ινστιτούτο Τεχνολογίας της Ζυρίχης, συνεργάστηκαν σε μια παραλλαγή του προβλήματος των n-queens, που είναι γνωστό ως το torodial ή modular problem. Σε αυτό, οι διαγώνιοι τυλίγονται γύρω από τον πίνακα, έτσι μια βασίλισσα θα μπορούσε να μετακινηθεί διαγώνια από τη δεξιά άκρη μιας σανίδας και να εμφανιστεί ξανά στα αριστερά, για παράδειγμα.
Αυτό δίνει σε κάθε βασίλισσα συμμετρία επίθεσης, αλλά δεν λειτουργεί έτσι μια κανονική σκακιέρα. Μια βασίλισσα στη γωνία της σκακιέρας δεν έχει τόσες γωνίες επίθεσης, όσο μια στο κέντρο.
Τελικά, η εργασία των δύο μαθηματικών για το πρόβλημα του δακτυλίου σταμάτησε (αν και δημοσίευσαν κάποια αποτελέσματα), αλλά ο Simkin κατέληξε να προσαρμόσει μερικούς από τους καρπούς αυτής της εργασίας στην τελική του λύση.
Καθώς οι σειρές μεγαλώνουν και ο αριθμός των βασίλισσων αυξάνεται, η έρευνα δείχνει ότι στις περισσότερες επιτρεπόμενες διαμορφώσεις οι βασίλισσες τείνουν να συγκεντρώνονται κατά μήκος των πλευρών της σανίδας, με λιγότερες βασίλισσες στη μέση, όπου εκτίθενται σε επίθεση. Αυτή η γνώση επιτρέπει μια πιο σταθμισμένη προσέγγιση.
Θεωρητικά, μια πιο ακριβής απάντηση στο παζλ n-queen θα πρέπει να είναι δυνατή, αλλά ο Simkin μας έχει φέρει πιο κοντά από ποτέ στην απάντηση και είναι ευτυχής να μεταβιβάσει την πρόκληση σε κάποιον άλλο για να μελετήσει περαιτέρω.
Η μελέτη του Simkin για τη λύση είναι διαθέσιμη στον ιστότοπο του Cornell University arXiv.
Με πληροφορίες από Science Alert
με Αριθμό Μητρώου 12691
