Most, if not all, chess players are aware of the Knight Tour. For non chessplayers, it is a challenge where you have to visit every square on the chessboard once and only once with a knight (moving legally of course). The first solutions to this problem probably date back the the 9th century, and since then various approaches to solving the problem have been developed.
Obviously one trick is to simply memorise the sequence of squares for a re-entrant tour (where the finish square is a knights move away from the start square) as you can then start on any square on the board and still have a solution. However if you want to solve it for yourself, Warnsdorff's algorithm might be helpful Basically you move the knight to a square with the fewest squares to move to (although when I tried this I trapped the knight!).
There is a substantial amount of mathematical research on this topic, dating back to Euler. It is also related to various mathematical 'colouring' problems, as the knight must always move to a square of the opposite colour it stands on (a fact which leads to a quick answer to the question of the maximum number of knghts on a chess board where they don't attack each other).
Wikipedia has a page devoted to the Knights Tour, including information on tours of non 8x8 boards. I also came across a discussion of the Knights Tour in the book "Mathematical Conversations" where is has a number of problems associated with it. Here are two simple ones which I think can be solved with a little bit of thought, and the information in this blog.
(A) Take away the h file and the 8th rank from a normal chess board, leaving a 7x7 board. Why can't a knight perform a knights tour on this board, if it starts on a white square?
(B) Using the same board, can a knight end its tour on square adjacent to it starting square (orthogonal, not diagonal)?
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment