Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm currently stuck on a problem from my computer theory class homework. The question asks me to prove, using induction, that any chessboard of size $n \times 3$, where $n$ is even and $\geq 10$, will have a closed knight's tour. I've worked on the problem for a couple hours but can't seem to find any insight into the solution. I can't even figure out the tour for what I think is the base case, $n = 10$. Any tips or hints as to how I might go about proving this?

The question itself comes with a hint, saying that there will be two base cases. At first I thought this meant that I would have to show a closed knight's tour for one value of $n < 10$, which might give me a helpful property during the induction step, but having checked the Wiki article on closed knight's tours I understand now that there is no value of $n < 10$ for which a closed knight's tour is possible. In that case, maybe one base case chessboard can be broken down into subchessboards in one way that reveals a closed knight's tour, that extends to some values of $n$, while another can be broken down in a different way that extends to some other values of $n$? I'm not really sure how to interpret the hint and since I can't even figure out a single closed knight's tour I'm effectively stumped.

Some definitions that come with the question:

In chess, a knight’s move consists of travelling two squares in one direction (horizontally or vertically, but not diagonally) and then one square at 90 degrees to these.

A closed knight’s tour is a sequence of knight moves that touch upon every square on the board exactly once and end on a square from which one is a knight’s move away from the beginning square.

I don't want the full solution to the problem, but would appreciate some help as to how I should go about approaching it, since I'm currently completely stuck.

share|improve this question

3 Answers 3

If I saw correctly, the cases $n=10$ and $n=12$ can be found in Hill's and Tostado's paper.

share|improve this answer
    
Given these two, your challenge is to find a way to append 12 more squares (extending the rectangle by 4 rows of 3) to an existing solution. Maybe you can see how to remove the link between a corner square and the one next to the other corner, then tour the new squares from one and return to the other. –  Ross Millikan Oct 1 '11 at 21:55

Once you figure out the base cases $n=10$ and $n=12$ you should prove the induction step which is: if there is a closed knight's tour on the board of the size $n\times 3$ there is one on the board of the size $(n+4)\times 3$. This suffices to prove the claim for all even $n\geq 10$ since it holds for both of the base cases.

Hint: Assume you have a closed knight's tour on the board of the size $n\times 3$. In this tour there is a move from the square $(n-1,3)$ to the square $(n,1)$ (I'm using the convention that the leftmost upper corner square is called $(1,1)$ and the rightmost lower corner square is called $(n,3)$). Now remove this move from the tour and imagine there is a $4\times 3$ board added to the right of your original board.

The task is to visit all the squares of this new $4\times 3$ board starting from the square $(n-1,3)$ and ending to such a square that you can move to $(n,1)$. The first move is obvious: it is from $(n-1,3)$ to $(n+1,2)$. There are two possibilities where the last move must land so that you can move to $(n,3)$: they are $(n+1,3)$ and $(n+2,2)$. When you succeed at this task you have managed to replace the move $(n-1,3)\to(n,1)$ in the original tour with a string of moves which cover the added piece of board. The result is a closed knight's tour on the board of size $(n+4)\times 3$ and the induction step is completed.

share|improve this answer

Schwenk’s base cases can be found along the right-hand edge of Fig. 6 of this paper. Since the boards are $3\times 10$ and $3\times 12$, it seems likely that the induction step involves extend a solution for a $3 \times n$ board to a solution for a $3\times(n+6)$ board. However, I’ve not seen Schwenk’s argument, so take this with a grain of salt.

A rather different approach is used in the paper Knight’s Tour here. It might be a little easier. I’ll give you the idea without any of the details.

The authors find two disjoint non-closed half-tours on a $3\times 8$, one starting at the upper left corner and ending at the lower right corner, the other starting at the upper right corner and ending at the lower left corner; between them they cover the board. They call this an extension board; any number of these can be chained together to make longer extension boards. They also find what they call tab boards of sizes $3\times 7$, $3\times 9$, $3\times 11$, and $3\times 13$. Each of these boards admits a complete (non-closed) tour that starts in the upper left corner and ends at the square diagonally below and to the right of the starting point. Thus, if the board were now to be extended to the left, it would be possible to extend the tour by jumping to the cell immediately to the left of the original upper left corner. It’s not hard to see how to combine tab and extension boards to get closed knight’s tours on boards of sizes $3\times 2n$ for $n\ge 7$; the $3\times 10$ and $3\times 12$ cases are handled individually.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.