Το Παζλ των Οκτώ Βασιλισσών: Από τον Gauss στη Μερική Λύση του Χάρβαρντ

Αν αγαπάτε το σκάκι, ίσως έχετε ακούσει το παζλ των οκτώ βασιλισσών. Το ερώτημα είναι απλό στη διατύπωση: πώς μπορεί κανείς να τοποθετήσει οκτώ βασίλισσες σε μια σκακιέρα 8×8, έτσι ώστε καμία βασίλισσα να μην απειλεί κάποια άλλη; Με άλλα λόγια, δεν επιτρέπεται να βρίσκονται στην ίδια γραμμή, στήλη ή διαγώνιο.

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

Οι πρώτες λύσεις και ο Gauss

Ο Carl Friedrich Gauss, το «θαύμα των μαθηματικών», ασχολήθηκε με το παζλ το 1859. Αντί να βασιστεί αποκλειστικά στη μέθοδο δοκιμής και σφάλματος, το μετέτρεψε σε αριθμητικό πρόβλημα και υπολόγισε 72 λύσεις. Στην πραγματικότητα, οι συνολικές λύσεις είναι 92, αλλά αν αφαιρέσουμε τις συμμετρίες (περιστροφές και κατοπτρισμούς), μένουν μόνο 12 μοναδικές.

Οι λύσεις μπορούν να κωδικοποιηθούν με ακολουθίες αριθμών. Για παράδειγμα, η ακολουθία 41582736 δηλώνει τις θέσεις των βασιλισσών: το πρώτο ψηφίο δείχνει σε ποια γραμμή βρίσκεται η βασίλισσα της πρώτης στήλης, το δεύτερο για τη δεύτερη στήλη κ.ο.κ. Έτσι, το «4» σημαίνει βασίλισσα στην τέταρτη γραμμή της πρώτης στήλης, το «1» βασίλισσα στην πρώτη γραμμή της δεύτερης στήλης, και ούτω καθεξής.

Μία από τις πιθανές λύσεις στο παζλ των Οκτώ Βασίλισσες

Από τις 8 βασίλισσες στο πρόβλημα n-Queens

Η πραγματική γοητεία του γρίφου αποκαλύφθηκε όταν γενικεύτηκε: πώς μπορούμε να τοποθετήσουμε n βασίλισσες σε σκακιέρα n×n; Αυτό είναι το γνωστό πρόβλημα των n-Queens.

Όσο το n μεγαλώνει, η δυσκολία εκτοξεύεται. Για μεγάλες σκακιέρες, ακόμη και οι ισχυρότεροι υπολογιστές δυσκολεύονται να βρουν πλήρεις λύσεις. Το πρόβλημα αποτελεί σημείο συνάντησης σκακιού, συνδυαστικής και θεωρίας πολυπλοκότητας.

Η πρόκληση P vs NP

Το n-Queens συνδέεται με ένα από τα μεγαλύτερα ανοιχτά ερωτήματα των μαθηματικών: το P=NP; Αν κάποιος έβρισκε έναν αποδοτικό αλγόριθμο για το n-Queens, θα μπορούσε να χρησιμοποιηθεί για την επίλυση πολλών άλλων προβλημάτων της ίδιας κατηγορίας. Και αυτό θα σήμαινε βραβείο 1 εκατομμυρίου δολαρίων, καθώς το P vs NP είναι ένα από τα Millennium Prize Problems.

Η σύγχρονη πρόοδος του Harvard

Το 2022, ο Michael Simkin από το Harvard University έκανε ένα μεγάλο βήμα. Απέδειξε ότι σε πολύ μεγάλες σκακιέρες, οι βασίλισσες μπορούν να τοποθετηθούν με περίπου $(0,143n)^n$ διαφορετικούς τρόπους χωρίς να απειλεί η μία την άλλη.

Η εργασία του δεν δίνει μια οριστική λύση, αλλά θέτει σαφή όρια: ένα κατώτερο και ένα ανώτερο πλαίσιο για τον αριθμό των λύσεων. Πρόκειται για αποτέλεσμα πέντε ετών έρευνας και θεωρείται ένα από τα σημαντικότερα βήματα στην ιστορία του προβλήματος.

Γιατί έχει σημασία το παζλ;

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

Από τον Gauss του 19ου αιώνα μέχρι τη μερική λύση του Simkin τον 21ο αιώνα, το πρόβλημα εξακολουθεί να εμπνέει μαθηματικούς, προγραμματιστές και ερασιτέχνες του σκακιού. Και το ταξίδι του, όπως φαίνεται, δεν έχει τελειώσει ακόμα.