2
$\begingroup$

It is generally difficult to determine whether a (large) graph have no Hamilton cycle (As opposed to determining whether it has any Euler circuit). This example illustrates a method (which sometimes work) to indicate that a graph has no Hamilton cycle.

a. Show that if m and n are odd integers (not both = 1), a Knight is not in Following features visit all the squares on an m × n 'chessboard' just once, return to the starting point. (A knight goes in a move two squares forward and one to the side.)

b. Show the same thing for a board of size 4 × n, n integer.

I know when is a hamilton cycle we visit every vertirce in the graph. I draw this in paint but i was very weird?? Somebody with a hint?

$\endgroup$
  • $\begingroup$ "a runner is not in Following features visit all the squares on an m × n 'chessboard' just once, return to the starting point." $\endgroup$ – model_checker Nov 12 '16 at 19:22
  • $\begingroup$ I didn't get this line. Please rephrase this properly. $\endgroup$ – model_checker Nov 12 '16 at 19:23
  • $\begingroup$ Sorry i mean a Knight in chess i shall edit it! $\endgroup$ – user3704516 Nov 12 '16 at 19:27
  • $\begingroup$ Are you still there Shrey Aryan? $\endgroup$ – user3704516 Nov 12 '16 at 19:32
  • $\begingroup$ Yes! I am here... $\endgroup$ – model_checker Nov 12 '16 at 19:45
3
$\begingroup$

Both parts are well-known (see, for instance, Theorem in [Schw], and short proofs in [GT]) and easy to prove.

a. It is well-known that the chessboard cells are colored black and white and when Knight moves it changes color of its cell. Therefore each Hamiltonian Knight cycle on the chessboard has an equal numbers of black and white cells. So if such a cycle exists then the chessboard also has an equal numbers of black and white cells, which doesn’t hold when both $m$ and $n$ are odd. Or see Theorem 2.5 from [McG,L].

b. See, for instance, Theorem 3.15 from [McG,L]

References

[GT] Rob Gaebler, Tsu-wang Yang, Knight's Tours (August 13, 1999).

[McG,L] Kevin McGown, Ananda Leininger, Knight’s Tour.

[Schw] Allen J. Schwenk, Which Rectangular Chessboards Have a Knight's Tour?, Mathematics Magazine, Vol. 64, No. 5 (Dec., 1991), pp. 325-332.

Additional references

http://www.borderschess.org/KnightTour.htm

http://users.cecs.anu.edu.au/~bdm/papers/knights.pdf

http://blog.wolfram.com/2014/09/04/solving-the-knights-tour-on-and-off-the-chess-board/

http://www.sciencedirect.com/science/article/pii/S0166218X04003488

http://algorithms.tutorialhorizon.com/backtracking-knights-tour-problem/

$\endgroup$
  • $\begingroup$ But does it return to the starting point?? $\endgroup$ – user3704516 Nov 13 '16 at 13:19
  • $\begingroup$ @JonasBo It depends on the definition of the tour. In closed tours Knigth have to return to the starting point, in open - not necessarily. $\endgroup$ – Alex Ravsky Nov 13 '16 at 13:44
  • $\begingroup$ Is it the same algorithm? $\endgroup$ – user3704516 Nov 13 '16 at 14:30
  • $\begingroup$ @JonasBo The families of boards admitting open tour a bit differs from the family admitting a closed one, see, for instance, section ‘Existence’ in the Wikipedia article and, especially [GT]. Concerning the algorithms to construct these tours, I thing that they should be slightly different. You can read more about them in the above references. I also add some references which I found but not looked at (yet). $\endgroup$ – Alex Ravsky Nov 13 '16 at 16:36
4
$\begingroup$

There's a really pretty proof for part (b), which the accepted answer does not do justice to by hiding it under links.

We consider two colorings of the $4 \times n$ board. The first is the usual black and white coloring:

black-and-white

Each knight move must be to a square of another color, so the colors alternate black-white-black-white in any knight's tour.

The second coloring is to color the top and bottom rows blue and the middle rows orange:

blue-and-orange

From a blue square, a knight can only go to orange squares. The reverse is not true, but in a closed tour, there are $2n$ blue squares and $2n$ orange squares, and blue squares cannot be adjacent, so the colors alternate blue-orange-blue-orange in any closed tour.

Assume for contradiction that a closed knight's tour exists. We can start the closed tour anywhere we like, so let's start at the top left square, which is white in the first coloring and blue in the second. Both groups of colorings alternate, so the next square is black/orange, the one after that is blue/white again, the one after that is black/orange again, and we can never get to a white/orange or black/blue square.

So a closed knight's tour cannot exist.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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