Η εργονομική διαδρομή του ίππου σε σκακιέρα NxN.

Abstract

Υλοποιούμε και διερευνούμε την χρήση του ευριστικού αλγορίθμου που προτάθηκε από τον H. C. Warnsdorff στις αρχές του 19ου αιώνα για το πρόβλημα της εύρεσης της διαδρομής του ίππου και εξετάζουμε την δυνατότητα επέκτασης αυτού για την αποδοτικότερη λύση σε περιπτώσεις «ισοπαλίας». Περιγραφή και εξέταση της διαδικασίας εύρεσης των διαδρομών του ίππου σε σκακιέρες NxN με N ≥ 5.Δίνεται μία καταγραφή των διαφορών για N άρτιο και περιττό καθώς και παραδείγματα με την εφαρμογή του κανόνα του Warnsdorff σε σκακιέρες διάφορων διαστάσεων και με διάφορες λύσεις «ισοπαλίας» με την χρήση της C++. Τέλος, δίνεται η οπτική αποτύπωση διαφόρων διαδρομών και ανάλυση αποτελεσμάτων πολλαπλών διαδρομών με χρήση Matlab.

We apply and also investigate the use of the heuristic algorithm proposed by H. C. Warnsdorff in the early 19th century on the problem of finding the knights path and we examine its possible extension for a more efficient solution in the case of "ties". We describe and review the procedure for discovering knight paths on all chessboards NxN with N ≥ 5. Highlight of differences when N is even and when it is odd. Examples of the application of the rule of Warnsdorff are provided on boards of various sizes and of various solutions of the "ties" with the use of C++. Finally, various visual mapping of knight paths are presented along with a results analysis by use of Matlab