pistopoihsh agglikwn LTE golearn AEP
skaki
Το πρόβλημα των 8 Βασιλισσών είναι ένα από τα πιο διαδεδομένα παιχνίδια προγραμματισμού το οποίο μπορεί να το βρει κανείς και στο Φωτόδεντρο, το Πανελλήνιο Αποθετήριο Μαθησιακών Αντικειμένων για την πρωτοβάθμια και τη δευτεροβάθμια εκπαίδευση

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

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

1.png

Με το συγκεκριμένο πρόβλημα μπορούν να ασχοληθούν μαθητές της Γ Λυκείου, οι οποίοι καλούνται να τοποθετήσουν 8 βασίλισσες σε μια σκακιέρα 8x8 με τέτοιο τρόπο, ώστε καμία βασίλισσα να μην απειλείται από την άλλη.

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

Το συγκεκριμένο πρόβλημα αποτελεί ένα από τα βασικά μαθήματα εισαγωγής στην τεχνητή νοημοσύνη, με τις πιθανές τοποθετήσεις των 8 βασιλισσών σε μια σκακιέρα 8x8 να είναι 4.426.165.368, ενώ με τον περιορισμό ότι τοποθετούμε μια βασίλισσα ανά γραμμή οι πιθανές τοποθετήσεις πέφτουν στον αριθμό 16.777.216 και αποδεικνύεται ότι το πρόβλημα έχει 92 διαφορετικές λύσεις.

Τι γίνεται όμως αν θέλουμε να τοποθετήσουμε ένα μεγαλύτερο αριθμό από βασίλισσες, όπως για παράδειγμα 1000 βασίλισσες σε μια τετράγωνη σκακιέρα 1000x1000;

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

Το 1869 δόθηκε και η γενική μορφή του προβλήματος (n-queens) το οποίο έμεινε αναπάντητο για πολλές δεκαετίες έχοντας πονοκεφαλιάσει μαθηματικούς, σκακιστές και πληροφορικούς, αφού κανείς δεν είχε καταφέρει να βρει έναν αλγόριθμο που να τον λύνει εύκολα και αποτελεσματικά. Βρετανοί ερευνητές μάλιστα, πριν από λίγα χρόνια είχαν πει ότι κανένας υπολογιστής δεν θα τα καταφέρει ποτέ, προσφέροντας αμοιβή 1.000.000 δολάρια σε όποιον αποδείξει ότι κάνουν λάθος!

Όλα αυτά μέχρι πριν λίγο καιρό, όταν ο Michael Simkin, μαθηματικός στο Κέντρο Επιστημών και Ερευνών στο Harvand, έδωσε μια σχεδόν οριστική απάντηση. Υπολόγισε ότι υπάρχουν (0,143n)n τρόποι να μπορούν να τοποθετηθούν οι βασίλισσες, ώστε καμία να μην επιτίθεται στην άλλη σε γιγάντιες σκακιέρες nχn.Αν για παράδειγμα έχουμε 1.000.000 βασίλισσες, ο τύπος αυτός δίνει μια τελική απάντηση με 5 εκατομμύρια ψηφία.

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

"Πιστεύω ότι πρέπει να τελειώσω με αυτό το πρόβλημα, όχι επειδή δεν έχω κάτι άλλο να κάνω με αυτό, αλλά επειδή ονειρευόμουν το σκάκι για χρόνια και πρέπει πλέον να προχωρήσω με τη ζωή μου και σε άλλα πράγματα."

 

Θανάσης Κοπάδης

Μαθηματικός - Συγγραφέας

Google news logo Ακολουθήστε το Alfavita στo Google News

Όλες οι σημαντικές και έκτακτες ειδήσεις σήμερα

Το πιο γρήγορο τεστ ευφυΐας στον κόσμο: Δείτε με τρεις ερωτήσεις αν έχετε IQ πάνω απ’ το μέσο όρο

ΑΣΕΠ: Ποια σεμινάρια Πανεπιστημίων μοριοδοτούν στους Πίνακες ΕΙΔΙΚΗΣ αλλά και ΓΕΝΙΚΗΣ - ΠΡΟΣΟΧΗ ΣΤΟ ΘΕΣΜΙΚΟ ΠΛΑΙΣΙΟ

Πίνακες αναπληρωτών ΕΑΕ: Προλαβαίνετε να πάρετε 11 μόρια έως τις 23 Μαϊου

Η 1η Πανεπιστημιακή Επιμόρφωση στον Αυτισμό από το Παν.Πατρών με Μοριοδοτούμενο Πιστοποιητικό

ΑΣΕΠ: Το ΠΙΟ ΕΥΚΟΛΟ online Lower - Proficiency για Ενήλικες σε 2 ημέρες Μόνο 111 ευρώ

ECDL | Πιστοποίηση Υπολογιστών για ΑΣΕΠ μόνο 95 ευρώ μέσα σε 2 ημέρες

νέα από το Ethnos logo

σχετικά άρθρα

Κυριάκος Μητσοτάκης
Φοιτητική στέγη όχι... «κατ' ανάγκη δωρεάν» προανήγγειλε ο Μητσοτάκης
ΣΔΙΤ για τις φοιτητικές εστίες των πανεπιστημίων της χώρας προανήγγειλε ο Κυριάκος Μητσοτάκης - Κάνει λόγο για «φτηνή και ανταγωνιστική φοιτητική...
Φοιτητική στέγη όχι... «κατ' ανάγκη δωρεάν» προανήγγειλε ο Μητσοτάκης
zetta makri
Άδειες ανατροφής νεοδιόριστων: Δίνονται αναδρομικά όταν το επιτρέπει ο νόμος
Οι άδειες ανατροφής νεοδιόριστων εκπαιδευτικών και μελών ΕΕΠ και ΕΒΠ δίνονται αναδρομικά όταν το επιτρέπει ο νόμος και όταν πληρούνται οι...
Άδειες ανατροφής νεοδιόριστων: Δίνονται αναδρομικά όταν το επιτρέπει ο νόμος
Bullying στα σχολεία: «Χτυπούσαν τον γιο μου κάθε μέρα, του έσπασαν το χέρι»
Νέο περιστατικό bullying σε σχολείο έρχεται στο φως της δημοσιότητας χρόνια μετά - «Χτυπούσαν τον γιο μου κάθε μέρα, του έσπασαν το χέρι»,...
Bullying στα σχολεία: «Χτυπούσαν τον γιο μου κάθε μέρα, του έσπασαν το χέρι»