I have been trying to find a mathematical proof that the knight (the chess piece) can, given enough moves, reach all of the squares on the board.
Can someone help? I tried solving this myself, using probability theory, but did not manage to do it. Any ideas?

Can you show that, given enough moves, the knight can move to any of the adjacent squares?
Because if you can, then it can just keep on repeating those patterns.
Of course, it needs to be able to move to the left square using moves to the right of that square and so on, so that it can reach the sides. But that's not hard to do.

Well, Brighteye's suggestion also needs to take into account the restriction on board size. A knight that jumps 8,1 squares can reach any square on a larger board but not a normal chess board, so you need to show that it can reach an adjacent square without having to go more than a certain distance away.

I don't suppose it counts as mathematical if you give an example? :p

My suggestion: Start by showing that if a knight starts in the corner of a 3x3 area, it can eventually jump to any square but the middle one.
1 4 7
6 X 2
3 8 5
Then show that you can connect such rings to cover the whole board.

Get a chessboard. IIRC the knight can visit every square without visiting a square more than once. It doesn't take long to work out IIRC.

As to can it simply visit any square: all you need to do is show that it can visit any adjacent square and you can repeat that translation any number of times in any direction. This is trivial.

Ty, but i am looking for a mathematical proof. :) I know that all the moves can be noted, and shown as true, but this is not a proof. I also thought of breaking the thing up to smaller parts, for example four, and presenting that the moves are symetrical in ways to the ones done in the one fourth of the board. Still this is not a proof though.. (albeit not an elegant one).

I mentioned probability theory because i think it can provide one. Only i cannot think of how to do it. In each position the knight if found it has a maximum of 8 moves (for example near the center of the board) and a minumum of 2 moves (near/in the corners). So a type which would calculate the degree to which the moves get less or more, in relation to the position in the board, in theory would be the key to solving the problem.

You can move to an adjacent square without going over any border that may be present in the direction of the move using a series of 5 translations:

(5 moves from position 1 to position 6)
http://forums.civfanatics.com/uploads/58764/knight_moves.JPG

Shoddy paint image, sorry.

Formalise those translations as co-ordinates. You should be able to do the same wherever your border is.

Well what i am looking for is a compact way of presenting all of that in a few lines. It is obvious of course that you can write a progression from any square showing that given enough moves you can get to any other square. But i am not looking for the simple answer that the knight can indeed reach any square.
I was thinking of this problem:

a) present that the knight can reach every square in the board.
b) present a type which calculates the least amount of moves that the knight has to make to get to any given square.

So co-ordinates would not help; i am looking for something else. ;)

I don;t see how you're going to manage without co-ordinates tbh. And to obtain b, will likely not be simple without a lot of repetition of slightly different translations.

To sum up: if you're looking for somethig simple and elegant I think you are unlikely to find it. :(

Yeah,"b" is in the heart of the problem, since "a" would just be a special case of it. I believe that there is a simple and elegant way of presenting everything, but i cannot think of one for this either :D

Gah. Lost the reply I was typing up due to unexpected crash.

Brennan: Your solution is wasteful.
4 1 X X
X X X 2
X 3 X X
is shorter and simpler, and has the useful property of being contained within a 4x4 area, meaning it can be put in a quarter board.

Varwnos: What prevents you from simply using a Knight's Tour or the like as a proof by example?

Gah. Lost the reply I was typing up due to unexpected crash.

Brennan: Your solution is wasteful.
4 1 X X
X X X 2
X 3 X X
is shorter and simpler, and has the useful property of being contained within a 4x4 area, meaning it can be put in a quarter board.Yeah, i was sure I had a shorter solution but got fixated on that first move. Head Cold interfering with brain at the moment. :(

You could prove this by double induction of sorts, but there's way too many special cases.

You basically gotta show that you can get from (1,1) to any (i,j), which wouldn't be that hard, if it wasn't for the edges ;) I don't think it's possible to produce an elegant proof for this...

unless you can use the fact that the board is symmetric somehow to avoid the edge problem.

http://en.wikipedia.org/wiki/Knights_tour

Schwenk's Theorem,

For any m × n board with m less than or equal to n, a knight's tour is present unless one or more of these three conditions hold:

1) m and n are both odd
2) m = 1, 2, or 4; m and n are not both 1
3) m = 3 and n = 4, 6, or 8

For detailed explanations of the theorem and the conditions, do a Google Search for Schwenk's Theorem, or pick up John Watkin's Across the Board: The Mathematics of Chessboard Problems, which has a great section on the Knight's Tour problem.

Very interesting ArneHD :)

I will check Schwenk's Theorem Verge, ty as well :)

I think you might do it as a series problem, with each square on the board corresponding to a number in the ordinal sense. If not that then maybe it can be done recursively?

Ty, but i am looking for a mathematical proof. :) I know that all the moves can be noted, and shown as true, but this is not a proof. I also thought of breaking the thing up to smaller parts, for example four, and presenting that the moves are symetrical in ways to the ones done in the one fourth of the board. Still this is not a proof though.. (albeit not an elegant one

Well, if you are doing it mathematically then you can set it up as:

Assume starting position of (1,1), variation of (x,y) where 1 =< abs(x + y) =< 3 and x & y are both integers.

All board spaces may be obtained via rotations of the travel from (1,1) --> (2,3) --> (3,1) --> (1,2).

Shortest number of moves from one arbitrary point (A,B) to another (L,M) should be able to computed.