Το Σκακιστικό Πρόβλημα των 8 Βασιλισσών

n_queens_0Ένα πολύ γνωστό σκακιστικό πρόβλημα είναι αυτό των 8 Νταμών. Πώς μπορούμε να τοποθετήσουμε 8 Βασίλισσες σε μια κανονική (8×8) σκακιέρα χωρίς καμία από τις ντάμες να επιτίθεται στην άλλη;

Το ερώτημα τέθηκε για πρώτη φορά από τον Μαξ Μπέζελ (Γερμανός δημιουργός σκακιστικών προβλημάτων) το 1848. Δύο χρόνια αργότερα o Φράνζ Νάουκ έδωσε την λύση και μάλιστα μεγάλωσε τη διάσταση του προβλήματος. Το ερώτημα πλέον αφορούσε n αριθμό νταμών σε μια σκακιέρα που αποτελείται από n x n τετράγωνα! Από τότε πολλοί διάσημοι μαθηματικοί, όπως ο Γκάους, εργάστηκαν για τη λύση του.

Κάποια χρόνια αργότερα ο Γκάρντερ έκανε το πρόβλημα ακόμα πιο δύσκολο. Τοποθέτησε 3 λευκές και 5 μαύρες ντάμες σε μια σκακιέρα διαστάσεων 5X5 με τέτοιο τρόπο ώστε καμία του ενός χρώματος να μην επιτίθεται σε κάποια του αντίθετου. Σε αυτο το πρόβλημα υπάρχει μόνο μία λύση!

Στις ημέρες μας το Πανεπιστήμιο του St. Andrews της Σκωτίας προκαλεί προγραμματιστές από όλο τον κοσμό να λύσουν το πρόβλημα για πολύ υψηλές τιμές του n. Λύσεις μπορούν να προκύψουν για όλους τους φυσικούς αριθμούς (με εξαίρεση n=2 και n=3). Οι ερευνητές Τζέντ και Ναιτνγκέηλ αν και είδαν ότι η απάντηση για μια σκακιέρα με 64 τετράγωνα έρχεται σε κλάσματα του δευτερολέπτου, όταν η σκακιέρα γίνει 100×100 ή 1000×1000 οι υπολογιστές δεν μπορούν να ανταπεξέλθουν εντός ενός λογικού χρονικού πλαισίου και κάνουν αναφορά ότι θεωρητικά μπορεί να χρειαστούν έως και 1000 χρόνια!

eightqueens01Στον παραπάνω πίνακα παρουσιάζονται οι 12 πιθανές λύσεις που αφορούν μια κανονική σκακιέρα με 64 τετράγωνα.

Σας προκαλούμε να το δοκιμάσετε και εσείς στο παρακάτω σύνδεσμο.

Η σύγχρονη μελέτη του προβλήματος στην πραγματικότητα δεν αφορά απλά την επίλυση του παραπάνω κλασικού προβλήματος. Η συνεισφορά της έχει να κάνει με το γνωστό στους επιστημονες της πληροφορικής P vs NP πρόβλημα και την θεωρία της πολυπλοκότητας.

Αυτό που μένει να αποδειχθεί είναι αν η λύση στο πρόβλημα τον n-Βασιλισσών σε μια n x n σκακιέρα ( με μερικές μάλιστα βασίλισσες να έχουν τοποθετηθεί εξ αρχής) μπορεί να προσφέρει στην λύση κάθε προβλήματος της NP (Ο ορισμός της κλάσης NP έχει ως εξής: Η κλάση NP περιλαμβάνει όλα τα προβλήματα απόφασης για τα οποία αν μας δοθεί ένα πιστοποιητικό της απάντησης ΝΑΙ, μπορούμε να επαληθεύσουμε σε πολυωνυμικο χρόνο ότι είναι σωστής κατηγορίας). Αν το παραπάνω ισχύει τότε κάθε αλγόριθμος ο οποίος μπορεί αν επιλύσει το εν λόγω πρόβλημα θα μπορεί να λύσει και κάθε άλλο της NP κατηγορίας.

Εδώ μπορείτε να βρείτε την σχετική μελέτη.

 

Leave a Reply

Your email address will not be published. Required fields are marked *