Γρίφος χωρίς λύση

Μια ομάδα ερευνητών από το Πανεπιστήμιο του Σαιντ Άντριους προσκαλεί τους προγραμματιστές ηλεκτρονικών υπολογιστών σε όλο τον κόσμο να λύσουν έναν σκακιστικό γρίφο, γνωστό ως Qeens Puzzle, και να κερδίσουν 1 εκ. δολάρια. Ο γρίφος, ο οποίος έχει λυθεί από σκακιστές στο παρελθόν, προκαλεί πονοκέφαλο στους προγραμματιστές, αφού υποψιάζονται ότι ένα πρόγραμμα υπολογιστή θα χρειαζόταν χιλιάδες χρόνια για να τον λύσει. Το βραβείο του 1 εκ. δολαρίων προσφέρει το περίφημο Clay Mathematics Institute της Αμερικής.Ο επιστήμονας των υπολογιστών Ian Gent και οι συνεργάτες του πιστεύουν αν ένα πρόγραμμα μπορούσε, τελικά, να λύσει τον γρίφο, θα ήταν τόσο ισχυρό και αποτελεσματικό που θα ήταν ικανό, επίσης, να αποκρυπτογραφήσει τους ασφαλέστερους και ισχυρότερους κωδικούς στο Διαδίκτυο.
Ο γρίφος Queens Puzzle έγινε γνωστός το 1850, καθώς ένας σκακιστής αντιμετώπισε την πρόκληση να τοποθετήσει οκτώ βασίλισσες σε μια τυπική σκακιέρα, έτσι ώστε να μην μπορούν δύο από αυτές να επιτεθούν η μία στην άλλη. Αυτό σημαίνει ότι ο παίκτης θα πρέπει να τοποθετήσει μία βασίλισσα σε κάθε σειρά, έτσι ώστε δύο από τις βασίλισσες να μην βρίσκονται στην ίδια στήλη, ούτε, όμως, και στην ίδια διαγώνιο. Αν και το πρόβλημα λύθηκε από ανθρώπους, όταν η σκακιέρα αύξησε εντυπωσιακά το μέγεθός της, κανένα πρόγραμμα υπολογιστή δεν έχει καταφέρει, μέχρι σήμερα, να δώσει λύσει στον γρίφο.

St Andrews University – School of Computer Science – Impossible Chess Puzzle. Picture Shows; Professor, Ian Gent, right, with Dr Peter Nightingale from St Andrews Universities School of Computer Science pictured at Falkland Palace, Wednesday, 17 August 2017.
©Stuart Nicol Photography, 2017

Ο λόγος για τον οποίο τέτοιου είδους προβλήματα είναι τόσο δύσκολο να λυθούν από τους υπολογιστές έχει σχέση με το γεγονός ότι το πρόγραμμα του υπολογιστή έχει τόσες πολλές επιλογές να εξετάσει, που η έρευνά του μπορεί να διαρκέσει χρόνια. Ο αλγόριθμος, σε αυτή τη διαδικασία, εξετάζει κάθε πιθανή επιλογή και επιστρέφει στην αρχή μέχρι να εντοπίσει τη σωστή απάντηση.
« Ωστόσο, όλα αυτά είναι θεωρητικά. Στην πράξη, κανείς δεν έχει καταφέρει να παρουσιάσει, έως τώρα, ένα πρόγραμμα ικανό να λύσει το πρόβλημα γρήγορα. Η έρευνα, μας έχει δείξει ότι – για πρακτικούς λόγους – κάτι τέτοιο είναι αδύνατον να συμβεί», σημειώνουν οι ερευνητές. Διατηρούν, όμως, μια μικρή αμφιβολία. Για αυτό, υπενθυμίζουν, ότι είναι τόσο υψηλή και η αμοιβή που προσφέρουν σε όποιον καταφέρει να βρει μια γρήγορη λύση στο διάσημο πρόβλημα.

Πηγή : www.st-andrews.ac.uk  Θαλής και Φίλοι του Γ. Καρουζάκη