Transcript The Knight’s Tour

The Knight’s Tour
By
Colleen Raimondi
The Knight’s Tour



The Knight’s Tour is a geometrical problem
played on a chessboard.
It consists of moving a knight on a
chessboard in such a way that will hit every
cell once and only once.
There are many, many different solutions for
this problem.
Knight’s Tour Terms

Re-entrant: the last cell that the knight lands
on to finish the problem is also a cell that the
first cell, that the knight started from,
commands .

Cell: each square on a chessboard.
Re-entrance





On a board containing an even number of cells the
solution may or may not be re-entrant.
You cannot have a solution be re-entrant on a board
that contains an odd number of cells.
Reason: If a knight begins on a white cell, its first
move will end up on a black cell, and its next move
to a white cell, and so on.
That is why if the solution passes through all the
cells, on a board with an odd number of cells, the
last move will leave it on a cell of the same color of
the cell which it started from.
Therefore these cells cannot be connected by one
move.
Different Solutions




De Moivre Solution
Euler Solution
Vandermonde Solution
Warndorff Solution
De Moivre









These solutions pertain to an ordinary eight by eight chessboard
(64 cells).
Divide the board into an inner 4x4 square that is bordered by an
outer ring of two cells deep.
Either start the path in the outer circle or by starting in the inner
square.
If you start from the outer circle, the knight needs to move
around the outer circle in one direction to fill it up completely.
Only go into the inner square when it is absolutely necessary
When the outer ring is filled up, there are only a few cells left in
the inner square.
You can pass through these pretty easily with a little ingenuity.
If you start from the inner square, you have to reverse the
process.
You can apply this method to different variations of square and
rectangle boards.
An Example of De Moivre
Euler 1759

Euler would start by randomly moving a
knight over a board until there were no more
moves available to it. Doing this carefully left
a few cells on the board that were not hit by
the knight and he would label these cells
a,b,…. His method consisted of establishing
certain rules by which these labeled cells
could be inserted into the knight’s path, and
also rules to make the solution re-entrant.
Euler’s Method
Let us take the example of a path formed by the knight of
1,2,3,…, 59,60; and with four cells left empty to be labeled
a,b,c,d.
55 58 29 40 27 44 19 22
60
39 56
43
30 21
26
45
57
54 59
28
41 18
23
20
38 51 42 31 8 25
53 32 37 a 47 16
46
17
9
24
50
3
1
4
52
36 7
12 15
34 5
33
48
b
14
c
10
49
35
6
11
d
13
2
Euler’s Method
We need to begin by making the path from 1 to 60 re-entrant.
Cell 1 commands a cell p, where p is 32, 52, or 2. Cell 60 commands
a cell q, where q is 29, 59, or 51.
If any of the values of p and q differ by 1 then we can make the path
re-entrant.
For this case we have p=52 and q=51. So the cells 1, 2, 3,…, 51;
60, 59,…, 52 form a re-entrant path of 60 moves.
Therefore, if we replace the numbers 60, 59,…, 52 by 52, 53,…, 60,
the steps will numbered successively.
Euler’s Method
57
54
29
40
27
44
19
22
52
39 56
43
30
21
26
45
55
58
53
28
41
18
23
20
38
51
42
31
8
25
46
17
59
32
37
a
47
16
9
24
50
3
60
33
36
7
12
15
1
34
5
48
b
14
c
10
4
49
2
35
6
11
d
13
Euler’s Method
Next, we need to add the cells a,b,d to this path.
In the new path of 60 cells a commands the cells 51, 53, 41, 25, 7,
5, and 3.
It does not matter which of these we pick, for the example we will
pick 51.
We want to make 51 the last cell of the path of 60 cells so that we
can continue with a,b,d.
To do this we want to add 9 to every number in path of 60 cells.
Then replace 61, 62,…, 69 with 1, 2,…, 9, then we will have a path
that starts from the cell initially occupied by 60, the 60th move is on
the cell initially occupied by 51, and the 61st, 62nd, 63rd moves will
be on the cells a, b, d in that order.
Euler’s Method
Replaced 61, 62,…, 69 with 1,
2,…, 9 and a,b,d with 61, 62, 63
Added 9 to all cells
66 63 38 49 36 53 28 31
6
3
61 48 65 52 39 30 35
54
1
48 5
52
39 30
35
54
64 67 62 37 50 27 32 29
4
7
37
50 27
32
29
47 60 51 40 17 34 55 26
47 60 51
40
17 34
55
26
68 41 46 a
8
41
59
12 9
10
59
56 25
18 33
12 69 42 45 16
21 24
23
c
19
13 58 11 44 15 20
d
22
10 43 14 57 b
38 49
2
53 28
31
61 56 25
18 33
42
45 16
21 24
43 14 57
62 23
c
19
15 20
63
22
13 58
46
36
11 44
Euler’s Method
We still have to introduce the cell c to the path.
Since c now commands the new cell number 25, and
63 commands the cell now numbered 24, we can use
the method we used earlier to make the path reentrant.
In fact the cells numbered 1, 2,.., 24; 63, 62,..,25, c
form a knight’s tour.
Therefore we need to replace 63, 62,..,25 by the
numbers 25, 26,…63, and then we can label c with 64.
Euler’s Method
6
3
50 39
1
40 5
36
49 58
53
34
4
7
51
38 61
56
59
48
17 54
33
62
2
41 28 37
42
52
35 60
57
27 32 63
18 55
46
43 16
21 24
45 14 31
26 23
64 19
15 20
25
8
47
29
12 9
10
13 30
11 44
22
Euler’s Method
The last thing we have to do is make the solution re-entrant.
First we need to get cell 1 and cell 64 near each other. Do this by taking
one of the cells commanded by 1, like 28, so 28 commands 1 and 27.
Therefore the cells 64, 63,…, 28; 1, 2,…, 27 form a path. We represent
this by replacing the cells numbered 1, 2,…, 27 by 27, 26,…,1.
The cell now occupied by 1, commands the cells 26, 38, 54, 12, 2, 14, 16,
28, and the cells commanded by 64 are 13, 43, 63, 55.
The cells 13 and 14 are consecutive, and therefore the cells 64, 63,…,14;
1, 2,…,13 form a path.
We need to replace the numbers 1, 2,…,13 with 13, 12,…1. By doing this
we achieve a re-entrant solution that covers the entire board.
Euler’s Method
Final Board: Replaced 1,
Replaced 1, 2,…, 27 by
27, 26,…,1.
22 25
50 39
52
35 60
2,…,13 with 13, 12,…1
57
22 25
50 39
52
35 60
57
27
40 23
36
49 58
53
34
27
40 23
36
49 58
53
34
24
21 26
51
38 61
56
59
24
21 26
51
38 61
56
59
41 28 37
48
11 54
33
62
41 28 37
48
3
54
33
62
1
32 63
13 32 63
4
55
46
43 12
7
4
29
16 19
46
43 2
7
2
64 9
18
45 14 31
12 9
64 5
1
11
20 47
42
29
16 19
18
45 14 31
15 30
17 44
5
13 8
10 55
3
6
20 47
15 30
42
17 44
6
10
8
Vandermonde’s Method




Cover the board by two or more independent paths taken
at random, and then to connect the paths.
Define the position of a cell was by a fraction x/y, where
the numerator x is the number of the cell from one side of
the board, and the denominator y is its number from the
adjacent side of the board.
In a series of fractions representing a knight’s path, the
difference between the numerators of two consecutive
fractions can be only one or two, while the corresponding
difference between their denominators must be two or
one respectively.
Also x and y cannot be less than 1 or greater than 8.
Vandermonde’s Method
1
1
2
3
4
5
6
7
8
2 3 4 5 6 7 8
5/5,
8/2,
7/1,
6/6,
2/6,
3/5,
3/1,
4/2,
4/4,
8/8,
8/4,
4/3,
6/1,
5/2,
5/4,
1/8,
1/4,
2/3,
3/4,
5/6,
6/7,
7/2,
2/4,
7/3,
6/4,
4/6,
3/7,
2/2,
1/1,
1/5,
7/5,
8/6,
5/1,
4/5,
8/1,
8/5,
2/5,
1/6,
4/1,
3/2,
2/7,
8/7,
7/8,
6/3
5/3,
6/2,
7/7,
1/7,
2/8,
3/3,
1/3,
4/8,
6/8,
5/7,
7/4,
8/3,
5/8,
3/8,
4/7,
1/2,
2/1,
3/6,
7/6,
6/5,
Warnsdorff’s Method



His rule is that the knight must be moved
always to one of the cells from which it will
command the fewest number of cells not
already touched upon.
The solution is not symmetrical or reentrant
In most cases a single false step, except in
the last three of four moves will not affect
the result.
http://w1.859.telia.com/~u85905224/knight/eWarnsd.htm