August 26, 2024

P91 - Knight's tour.

Another famous problem is this one: How can a knight jump on an N×Nchessboard in such a way that it visits every square exactly once?

Hints: Represent the squares by pairs of their coordinates of the form (XY), where both X and Y are integers between 1 and N. (Alternately, define a Point class for the same purpose.) Write a function jumps(N, (XY)) to list the squares that a knight can jump to from (XY) on a N×N chessboard. And finally, represent the solution of our problem as a list of knight positions (the knight's tour).

It might be nice to find more than one tour, but a computer will take a long time trying to find them all at once. Can you make a lazy list that only calculates the tours as needed?

Can you find only "closed tours", where the knight can jump from its final position back to its starting position?

Be first to comment
Leave a reply