I had fun doing last week's challenge, no other solutions sent or linked yet, but there's no timelimit; I'll accept entries indefinitely. Other program notes: I think that I'm going to try to post challenges on Monday, my solutions on Thursdays.
Challenge Two
The Knight's Tour is an old math problem: given a standard chessboard and a single knight, can you move the knight such that you land on every square exactly once. The knight must move as per normal chess rules, you can start and end on any square. A slight variation is a closed tour, where the knight ends up one legal move away from the starting point.
The challenge is to produce a program (in any language) that returns a solution to the puzzle.
None of the following are problem requirements, but worth considering:
- generalize the problem, and allow the size of the chess board to be user specified. Schwenk's Theorem provides some board constraints that are known to affect problem satisfiability. (Short version is that there are solutions if at least one dimension is even, and the board is reasonably large.)
- produce only closed path solutions, or allow the user to select
- produce random solutions. There are known to be billions of solutions for the standard board - program so as to find a solution non-deterministically.
- Wikipedia notes that it is possible to solve the general problem in linear time. It's not required that the solution be optimal, but consideration should likely be given to efficiency.
Some notes, none of which are promised to be helpful, but have occurred to me as I posed the problem:
- The solution set can be represented as a sequence of transition pairs - once all the transitions are selected, then the ordering is unambigious.
- All of the knight's moves for a given square are represented by a single vector, reflected horizontally, vertically or diagonally.
