Ματ στον μαγικό ίππο: Το τέλος ενός μαθηματικού μυστηρίου 150 ετών

 

Σαν σήμερα ή περίπου σαν σήμερα, το 2003.

Μετά από 61,40 ημέρες υπολογισμών, ένα πρόβλημα ηλικίας 150 ετών που παρέμενε άλυτο βρήκε τελικά απάντηση: 

   "δεν υπάρχει καμία διαδρομή ίππου σε σκακιέρα 8×8 που να σχηματίζει μαγικό τετράγωνο."

Η διαδρομή του ίππου (Knight's Tour) είναι μια ακολουθία κινήσεων ενός ίππου στη σκακιέρα, έτσι ώστε ο ίππος να επισκέπτεται κάθε τετράγωνο ακριβώς μία φορά. Η παλαιότερη γνωστή αναφορά στο πρόβλημα της διαδρομής του ίππου χρονολογείται στον 9ο αιώνα μ.Χ., στο σανσκριτικό έργο του Rudraṭa, Kavyalankara, ένα έργο αφιερωμένο στην ποιητική.

  Αν ξεκινήσουμε από ένα τετράγωνο που αριθμούμε ως «1» και στη συνέχεια αριθμήσουμε διαδοχικά κάθε τετράγωνο στο οποίο μετακινείται ο ίππος, δημιουργείται ένας πίνακας αριθμών 8×8. Αν αυτός ο πίνακας αποτελεί μαγικό τετράγωνο (δηλαδή αν όλες οι γραμμές, οι στήλες και οι διαγώνιοι έχουν το ίδιο άθροισμα), τότε έχουμε κατασκευάσει μια μαγική διαδρομή ίππου (magic knight's tour).

Ωστόσο, σήμερα γνωρίζουμε ότι κάτι τέτοιο δεν είναι δυνατό να συμβεί σε σκακιέρα 8×8.

Ήταν ήδη γνωστό ότι οι μαγικές διαδρομές ίππου δεν μπορούν να υπάρξουν σε σκακιέρες διαστάσεων n×n όταν το n είναι περιττός αριθμός. Επίσης, είχε αποδειχθεί ότι τέτοιες διαδρομές υπάρχουν για όλες τις σκακιέρες μεγέθους 4k×4k, όπου k > 2.

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

Το λογισμικό για τον υπολογισμό γράφτηκε από τον J. C. Meyrignac, ενώ ο Guenter Stertenbrink δημιούργησε την ιστοσελίδα που χρησιμοποιήθηκε για τη συλλογή και τη διάδοση των αποτελεσμάτων σχετικά με όλες τις δυνατές διαδρομές ίππου.

Μετά από 61,40 ημέρες καθαρού χρόνου επεξεργασίας (CPU time) — που αντιστοιχούν περίπου σε 138,25 ημέρες υπολογισμού σε έναν επεξεργαστή 1 GHz — το πρόγραμμα ολοκληρώθηκε στις 5 Αυγούστου 2003.

Η υπολογιστική έρευνα:

-εντόπισε συνολικά 140 διαφορετικές ημιμαγικές διαδρομές ίππου (semimagic knight's tours)(*),

-αλλά απέδειξε για πρώτη φορά ότι καμία μαγική διαδρομή ίππου 8×8 δεν είναι δυνατή.

Έτσι, ένα πρόβλημα που είχε παραμείνει ανοιχτό για περίπου ενάμιση αιώνα βρήκε οριστική λύση:

η περίφημη μαγική διαδρομή ίππου στην κλασική σκακιέρα 8×8 δεν υπάρχει

(*)Η ημιμαγική διαδρομή ίππου (semimagic knight's tour) είναι μια διαδρομή ίππου που έχει μερικές αλλά όχι όλες τις ιδιότητες ενός μαγικού τετραγώνου.