Κάλυψη και αποφυγή εντός της σκακιέρας.

Abstract

Ένα από τα πρώτα προβλήματα που διατυπώθηκαν προς λύση και που να αποδεικνύουν τις δυνατότητες του δομημένου προγραμματισμού είναι η εύρεση όλων των λύσεων του λεγόμενου “Προβλήματος των οκτώ Βασιλισσών ”. Γενικεύοντας και με την βοήθεια τη υπολογιστικής δύναμης που διαθέτουμε σήμερα μπορούμε να βρούμε λύσεις για διαστάσεις σκακιέρας 20x20, ενώ για μεγαλύτερες διαστάσεις ο χρόνος εκτέλεσης είναι απαγορευτικός. Επίσης μπορούμε με την ίδια λογική να ερευνήσουμε τον ελάχιστο αριθμό των βασιλισσών ή άλλων σκακιστικών κομματιών που τοποθετούνται σε μια σκακιέρα έτσι ώστε να μπορούν να την «καλύπτουν» εξ’ ολοκλήρου.

One of the first problems proposed to be solved, demonstrating the potential of structured programming, is finding all the solutions of the so-called “8-queens problem”. Generalizing and with the help of our programming computational power we can find solutions for a chessboard with dimension up to 20x20; for a larger size though the execution time is prohibiting. Also, following the logic of a similar approach, we computed the minimum number of queens and other chess pieces that can be placed on a chessboard in such a way so that they “threaten” the whole board throughout.