Το Σκακιστικό Πρόβλημα των 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 κατηγορίας.

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

 

2ο Σαμιακό Ατομικό Σκακιστικό Πρωτάθλημα

1. ΠΡΟΚΗΡΥΞΗ: Ο Σκακιστικός Όμιλος Σάμου «Μέλισσος» προκηρύσσει το 2ο Σαμιακό Ατομικό Σκακιστικό Πρωτάθλημα.

2. ΔΙΟΡΓΑΝΩΣΗ ΑΓΩΝΩΝ: Τους αγώνες συνδιοργανώνουν το Τμήμα Μαθηματικών του Πανεπιστημίου Αιγαίου και ο Σκακιστικός Όμιλος Σάμου «Μέλισσος».

3. ΗΜΕΡΟΜΗΝΙΑ & ΧΩΡΟΣ ΑΓΩΝΩΝ: Οι αγώνες θα διεξαχθούν την Κυριακή 26 Απριλίου 2015 στην Εμπορική Σχολή στο Καρλόβασι.

4. ΔΙΚΑΙΩΜΑ ΣΥΜΜΕΤΟΧΗΣ: Έχουν όλοι οι φοιτητές και οι φοιτήτριες της Σχολής Θετικών Επιστημών του Πανεπιστημίου Αιγαίου καθώς και όλοι οι ενήλικες που το επιθυμούν.

5. ΔΗΛΩΣΕΙΣ ΣΥΜΜΕΤΟΧΗΣ: Δηλώσεις συμμετοχής μέχρι και την Παρασκευή 24 Απριλίου 2015 είτε στο τηλέφωνο: 2273035794 είτε στο email: nikosrokopanos@gmail.com είτε στην ιστοσελίδα του Σκακιστικού Ομίλου Σάμου: www.chess-samos.eu

Η τελική επιβεβαίωση των δηλωθέντων συμμετοχών (και τυχόν νέες συμμετοχές) θα πραγματοποιηθεί με τη φυσική παρουσία των συμμετεχόντων, στο χώρο των αγώνων, την Κυριακή 26 Απρίλη 2015 (10:00 – 10:15).

ΑΦΙΣΑ ΠΑΝΕΠΙΣΤΗΜΙΑΚΟ 2015 - ΕΙΚΟΝΑ

Αναλυτικά η προκήρυξη εδώ ΠΑΝΕΠΙΣΤΗΜΙΑΚΟ ΠΡΩΤΑΘΛΗΜΑ 2015