Knight-moving problem

This is the famous Knight-moving problem - with a twist:

(1) Is it possible to move a knight from square to square eventually passing everyone of the 64 squares of the board? Can you start anywhere? Motivation?

(2) If you take one corner square away from the board and pose the same question: Is it possible to move a knight from square to square eventually passing everyone of the 63 squares of the remaining board? Is this harder than the previous problem? Can you start anywhere? Motivation?

(3) If you take the diagonally opposite corner square away from the board as well and pose the same question: Is it possible to move a knight from square to square eventually passing everyone of the 62 squares of the remaining board? Is this harder than the previous problem? Can you start anywhere? Motivation?

Originally posted by FabianFnas
This is the famous Knight-moving problem - with a twist:

(1) Is it possible to move a knight from square to square eventually passing everyone of the 64 squares of the board? Can you start anywhere? Motivation?

(2) If you take one corner square away from the board and pose the same question: Is it possible to move a knight from square to square even ...[text shortened]... e remaining board? Is this harder than the previous problem? Can you start anywhere? Motivation?

I'm inclined to say yes to all questions. You might need to pass several sqaures multiple times, but that wasn't prohibited.

Here is a knight circuit that helps show both 1 and 2:
http://img56.imageshack.us/img56/1386/knightcircuit3mb.gif

1) Yes you can. Also it possible to finish your tour a knight move away from the start point creating a circuit. As by definition this circuit must include every square the existence of such a circuit shows we could start anywhere and complete a tour.

2) As we established in 1 we can start on any square and finish on a square a knight's move away from that square. Now imagine we start our tour from a corner square. We will finish the tour having landed on every square. Now instead imagine the square we started on is the missing one. We simply start on the square that was second in our previous tour and we will now land on every one of the 63 remaining squares. In fact you can be missing any square and still complete a tour of the remaining 63 squares using this method.
However, this method doesn't allow any starting point for the truncated tour. This may or may not be possible.

3) A single knight's move will change the colour of the square the knight is on. Therefore a knight cannot complete a tour of any system that does not contain totals of white and black squares that differ by more than 1. As the two removed squares will be the same colour this new tour cannot be completed.


The only question I haven't answered is whether it is possible to start a tour of a one square missing chessboard from any point.

EDIT: I have assumed that only a single use of each square is allowed. This is the standard condition of the knight's tour problems.

Originally posted by XanthosNZ
The only question I haven't answered is whether it is possible to start a tour of a one square missing chessboard from any point.

I just thought to answer that question, I'll start a tour on e5 or so and see if it works. But then I noticed that even if I find a tour, that doesn't prove you can start anywhere. How to prove that in general? Give a solution for every starting square? There's gotta be a shorter way. I think mirroring eleminates 28 solutions, as starting squares d4 and e5 give same solution if h1 is the missing square. The squares from g2-a8 can't be mirrored, thats why 28. But the remaining 35 starting squares are still alot. Can more be eleminated like that? I'll think more later.

Originally posted by crazyblue
I just thought to answer that question, I'll start a tour on e5 or so and see if it works. But then I noticed that even if I find a tour, that doesn't prove you can start anywhere. How to prove that in general? Give a solution for every starting square? There's gotta be a shorter way. I think mirroring eleminates 28 solutions, as starting squares d4 and e5 ...[text shortened]... 5 starting squares are still alot. Can more be eleminated like that? I'll think more later.

No you can't eliminate any further ones by symmetry.

One way of showing that a given configuration can be solved from any starting position would be to find a circuit in that configuration. If h1 is the missing square then we have 32 Black squares and 31 white squares.
However for a circuit to be possible the first and last square in a sequence must be the opposite colour (otherwise they cannot be one knight move apart). This is not possible for uneven square totals. Therefore a circuit cannot be constructed for a board missing one square (any square).

However, the negative of above does not constitute a proof that it is impossible to construct a knight's tour of an 8x8 board missing one square from every starting position.

I may have missed the point here, but surely if there is one square missing from the board then any tour must start (and end) on a square of the opposite colour to the one removed. This follows from the fact that the tour "removes" squares in strict alternation.
Therefore, for a chess board with one square missing, there can only be 32 possible starting points AND the tour cannot be re-entrant (begin and end on the same square). Sorry if this is what somebody has already established.

Originally posted by howardbradley
I may have missed the point here, but surely if there is one square missing from the board then any tour must start (and end) on a square of the opposite colour to the one removed. This follows from the fact that the tour "removes" squares in strict alternation.
Therefore, for a chess board with one square missing, there can only be 32 possible start ...[text shortened]... (begin and end on the same square). Sorry if this is what somebody has already established.

That works as a proof. If h1 is missing then if the knight were to start on a white square it would describe 31 pairs of squares in the order White then Black. This leaves a last black square which cannot be reached from the final square in the pairs sequence as they are both black.

Therefore it not possible to tour every square on a chessboard missing h1 from a white starting square.

Originally posted by crazyblue
I just thought to answer that question, I'll start a tour on e5 or so and see if it works. But then I noticed that even if I find a tour, that doesn't prove you can start anywhere. How to prove that in general? Give a solution for every starting square? There's gotta be a shorter way. I think mirroring eleminates 28 solutions, as starting squares d4 and e5 5 starting squares are still alot. Can more be eleminated like that? I'll think more later.

e5 is possible. Oh, you solved it. I was reasoning that d5 was impossible... 😉

I lost the "every square once and once only" in the problems, sorry for that.

I see that some has a correct rasoning, some has not.

If I extend the problem(s) with

(4) If the checkboard has (not 8 by 8 squares but) 9 by 9 squares, how much are the problems 1, 2 and 3 changed? Are the answers the same?

Originally posted by FabianFnas
I lost the "every square once and once only" in the problems, sorry for that.

If I extend the problem(s) with

(4) If the checkboard has (not 8 by 8 squares but) 9 by 9 squares, how much are the problems 1, 2 and 3 changed? Are the answers the same?

Apparently any n by n "chessboard" with n >= 5 can be toured. For cases where n is odd, as in your extended example, the tour will not be re-entrant for the reasons given before.

See this link: http://mathworld.wolfram.com/KnightsTour.html

For a 9x9 there will be one more square of one colour than the other. So a tour will not be possible if you remove a square of the colour in the minority. Whether a tour is possible with a square of the majority colour removed is possible would probably require a computer search to determine. Any takers...?

Originally posted by howardbradley
For a 9x9 there will be one more square of one colour than the other. So a tour will not be possible if you remove a square of the colour in the minority. Whether a tour is possible with a square of the majority colour removed is possible would probably require a computer search to determine. Any takers...?

http://www.eng.unt.edu/~ian/pubs/algoknight.pdf

An interesting series of proofs related to knight's tours. In it we have a proof of a nxn board with a corner missing where n is odd being tourable.

http://img301.imageshack.us/img301/4020/9x9cornermissing5qv.gif
Here is one possible tour on a 9x9 board with the top left corner missing.

Note: The corner of a nxn board where n is odd will always be the majority colour.

You can move a knight on all squares in just as many moves... thats why its a horse and not a man on a horse... because man has a one-track mind.

Originally posted by ChessJester
You can move a knight on all squares in just as many moves... thats why its a horse and not a man on a horse... because man has a one-track mind.

You're really a jester.