Μαθηματικός του Χάρβαρντ έδωσε λύση σε σκακιστικό πρόβλημα 150 ετών
Το πρόβλημα των n-βασιλισσών εμφανίστηκε σε ένα γερμανικό περιοδικό σκακιού το 1848 και έγινε γνωστό ως το πρόβλημα των 8 βασιλισσών.
Η βασίλισσα, που συχνά λέγεται και ντάμα, είναι το ισχυρότερο κομμάτι στο σκάκι. Μπορεί να κινείται οριζόντια, κάθετα ή διαγώνια όσα τετράγωνα απόσταση θέλει. Επειδή είναι τόσο ισχυρή, συνήθως ανταλλάσσεται μόνο με την αντίπαλη βασίλισσα.
Αυτό σημαίνει πως πρακτικώς είναι υποχρεωμένη να υποχωρεί σε κάθε απειλή. Προτιμάται έτσι γενικά να καθυστερεί η είσοδός της στην αρχή της παρτίδας, ώστε να αναπτυχθούν καλύτερα τα υπόλοιπα κομμάτια.
Εισάγοντας νωρίς την βασίλισσα στην μάχη, είναι πιθανό να ξοδευτεί σε μετακινήσεις της επιπλέον «χρόνος», ο οποίος είναι πολύτιμος για το άνοιγμα. Επιπλέον, αυτή η περιπλάνηση μπορεί να αποδειχτεί επικίνδυνη για ένα τόσο σημαντικό κομμάτι.
Τώρα σκεφτείτε αυτό το παιχνίδι της βασίλισσας: Το πρόβλημα των 8 βασιλισσών είναι από τα πιο διαδεδομένα παιχνίδια προγραμματισμού και απαιτεί να τοποθετηθούν 8 βασίλισσες σε μία σκακιέρα 8x8 με τέτοιο τρόπο έτσι ώστε καμία βασίλισσα να μην απειλείται από την άλλη. Υπάρχουν λοιπόν 92 διαφορετικοί τρόποι που μπορούν να τοποθετηθούν οι βασίλισσες.
Αλλά τι γίνεται αν τοποθετήσετε έναν ακόμη μεγαλύτερο αριθμό από βασίλισσες σε μια σκακιέρα του ίδιου σχετικού μεγέθους, ας πούμε, 1.000 βασίλισσες σε μια τετράγωνη σκακιέρα 1.000 επί 1.000 ή ακόμα και ένα εκατομμύριο βασίλισσες σε μια σκακιέρα παρόμοιου μεγέθους;
Το πρόβλημα των n-βασιλισσών εμφανίστηκε σε ένα γερμανικό περιοδικό σκακιού το 1848 και έγινε γνωστό ως το πρόβλημα των 8 βασιλισσών, ενώ η σωστή απάντηση ήρθε δυο χρόνια αργότερα.
Στη συνέχεια, το 1869, εμφανίστηκε η πιο διευρυμένη εκδοχή του προβλήματος και παρέμεινε αναπάντητη μέχρι τα τέλη του περασμένου έτους, όταν ένας μαθηματικός του Χάρβαρντ έδωσε μια οριστική απάντηση.
Ο Μίκαελ Σίμκιν, ένας μεταδιδακτορικός συνεργάτης στο Κέντρο Μαθηματικών Επιστημών και Εφαρμογών του Harvard, υπολόγισε πως υπάρχουν (0.143n)n τρόποι με τους οποίους οι βασίλισσες μπορούν να τοποθετηθούν χωρίς να επιτίθενται η μία στην άλλη σε μία γιγαντιαία σκακιέρα nxn. Η εξίσωση του Σίμκιν, δεν προσφέρει ακριβή απάντηση αλλά ένα προσεγγιστικό νούμερο στην απάντηση, με το 0.143 να αντιπροσωπεύει ένα μέσο επίπεδο αβεβαιότητας.
Για παράδειγμα σε μία εξαιρετικά μεγάλη σκακιέρα με ένα εκατομμύριο βασίλισσες, το 0.143 θα πολλαπλασιαστεί με το 1.000.000 δίνοντάς μας 143.000. Έπειτα το νούμερο υψώνεται στη δύναμη του 1.000.000 δίνοντάς μας μία απάντηση με πέντε εκατομμύρια ψηφία. Όσον αφορά τη χωροταξική τοποθέτηση, ο Σίμκιν βρήκε πως όσο μεγαλώνει η σκακιέρα και αυξάνονται τα πιόνια, οι διατάξεις που επιτρέπουν τις περισσότερες τοποθετήσεις βασιλισσών τείνουν να τις συγκεντρώνονται στα άκρα της σκακιέρας με λιγότερες βασίλισσες προς το κέντρο της.
«Αν μου έλεγες ότι θέλω να βάλεις τις βασίλισσές σου με τέτοιον τρόπο στον πίνακα, τότε θα μπορούσα να αναλύσω τον αλγόριθμο και να σου πω πόσες λύσεις υπάρχουν που ταιριάζουν με αυτόν τον περιορισμό», είπε ο Σίμκιν.
Ο Σίμκιν εργαζόταν στο πρόβλημα εδώ και πέντε χρόνια, ενώ δηλώνει πως είναι αρκετά κακός παίκτης σκακιού. Υποστηρίζει πως είναι θεωρητικά πιθανό να βρεθεί μία πιο ακριβής απάντηση στο πρόβλημα, αλλά είναι ικανοποιημένος με τη δουλειά του και θα αφήσει κάποιον άλλο να το επιχειρήσει.
Η εργασία για τη λύση του προβλήματος ήταν μια δοκιμασία υπομονής και ανθεκτικότητας. Πριν από τέσσερα χρόνια, ως διδάκτορας στο Εβραϊκό Πανεπιστήμιο της Ιερουσαλήμ, επισκέφτηκε τον μαθηματικό και μάγο του σκακιού Ζουρ Λούρια στο Ελβετικό Ομοσπονδιακό Ινστιτούτο Τεχνολογίας στη Ζυρίχη. Το ζευγάρι συνεργάστηκε και ανέπτυξε νέες τεχνικές για να πάρει μια απάντηση.
Ο Σίμκιν ολοκλήρωσε το διδακτορικό του το 2020 και μετακόμισε στη Βοστώνη για να αρχίσει να εργάζεται στο Χάρβαρντ. Το πρόβλημα ήταν πάντα στο πίσω μέρος του μυαλού του και επανήλθε σε αυτό όταν συνειδητοποίησε ότι έπρεπε να αρχίσει να εστιάζει στους χώρους που θα βρίσκονταν οι βασίλισσες αντί να δίνει ίση βαρύτητα σε κάθε χώρο.
