Taking a 4 by 5 grid, How many possible Knight's tours are there starting in the upper left corner and ending in the lower right? (Reflections and rotations don't count)
(A Knight's move is as in chess, an L shaped move, 2 squares in one direction and 1 square in the other direction.)
A Knight's tour is visiting every square once and only once (and the square you start on is considered "visited" for these problems)
There are 12 ways altogether of making a knight's tour starting at the upper left corner and going to the lower right corner. The specification of the starting and ending positions as well as the non-square rectangular shape of the board prevent there being variations that are strict reflections or rotations of the board.
However, there is another symmetry involved: ten of the twelve ways consist of five pairs that are the reverse of one another. That is, if the path taken by the knight is retraced backwards from the end to the beginning, but considering the board rotated 180 degrees, the result is the other solution of the pair. If those are counted as being mere reflections, then the number of possible "ways" goes down to 7. Two ways are their own rotated reverse, and five pairs are mutual rotated reverses.
On the below list, the squares are marked with the order in which the knight occupies the square. The solutions are numbered. A solution which is the rotated reverse of a previous solution is marked also with which numbered solution it is the reverse of. The two solutions that are their own rotated reverse are marked with an asterisk.
The list is:
1 18 3 14 7
4 13 8 19 10 1
17 2 11 6 15
12 5 16 9 20
---------------
1 18 3 14 7
10 13 6 19 4 2
17 2 11 8 15
12 9 16 5 20
---------------
1 18 9 14 5
8 13 4 19 10 3
17 2 11 6 15
12 7 16 3 20
---------------
1 18 5 14 7
10 13 8 19 4 4
17 2 11 6 15
12 9 16 3 20
---------------
1 18 5 14 9
6 11 8 19 4 5 *
17 2 13 10 15
12 7 16 3 20
---------------
1 12 5 16 9
6 15 10 19 4 6 rev 1
11 2 13 8 17
14 7 18 3 20
---------------
1 12 5 16 9
6 17 10 13 4 7
11 2 19 8 15
18 7 14 3 20
---------------
1 18 5 14 9
6 15 10 19 4 8 rev 3
11 2 17 8 13
16 7 12 3 20
---------------
1 18 5 12 9
6 15 10 19 4 9 rev 4
17 2 13 8 11
14 7 16 3 20
---------------
1 16 5 12 9
6 13 10 19 4 10 rev 2
17 2 15 8 11
14 7 18 3 20
---------------
1 18 7 14 3
6 13 2 19 10 11 rev 7
17 8 11 4 15
12 5 16 9 20
---------------
1 12 7 16 3
6 17 2 11 8 12 *
13 10 19 4 15
18 5 14 9 20
---------------
The program to produce this is:
DECLARE SUB showSoln ()
DECLARE SUB nextMove (soFar!, row!, col!)
DIM SHARED maxRow, maxCol, lastMove, tot
maxRow = 4: maxCol = 5
lastMove = maxRow * maxCol
DIM SHARED board(maxRow, maxCol)
DIM SHARED hist(100, maxRow, maxCol)
board(1, 1) = 1
OPEN "kngttour.txt" FOR OUTPUT AS #1
nextMove 1, 1, 1 ' 1 move so far, at 1,1
CLOSE
PRINT tot
END
SUB nextMove (soFar, row, col)
newMove = soFar + 1
FOR r = row - 2 TO row + 2 STEP 4
IF r > 0 AND r <= maxRow THEN
FOR c = col - 1 TO col + 1 STEP 2
IF c > 0 AND c <= maxCol THEN
IF board(r, c) = 0 THEN
board(r, c) = newMove
IF newMove = lastMove THEN
IF r = maxRow AND c = maxCol THEN
tot = tot + 1
showSoln
END IF
ELSE
nextMove newMove, r, c
END IF
board(r, c) = 0
END IF
END IF
NEXT
END IF
NEXT
FOR r = row - 1 TO row + 1 STEP 2
IF r > 0 AND r <= maxRow THEN
FOR c = col - 2 TO col + 2 STEP 4
IF c > 0 AND c <= maxCol THEN
IF board(r, c) = 0 THEN
board(r, c) = newMove
IF newMove = lastMove THEN
IF r = maxRow AND c = maxCol THEN
tot = tot + 1
showSoln
END IF
ELSE
nextMove newMove, r, c
END IF
board(r, c) = 0
END IF
END IF
NEXT
END IF
NEXT
END SUB
SUB showSoln
FOR r = 1 TO maxRow
FOR c = 1 TO maxCol
hist(tot, r, c) = board(r, c)
NEXT
NEXT
FOR r = 1 TO maxRow
FOR c = 1 TO maxCol
PRINT #1, USING \"###\"; board(r, c);
NEXT
IF r = INT(maxRow / 2) THEN
PRINT #1, USING \"####\"; tot;
FOR i = 1 TO tot
Rev = 1
FOR cChk = 1 TO maxCol
FOR rChk = 1 TO maxRow
IF board(rChk, cChk) + hist(i, maxRow - rChk + 1, maxCol - cChk + 1) <> lastMove + 1 THEN
Rev = 0
EXIT FOR
END IF
NEXT
IF Rev = 0 THEN EXIT FOR
NEXT
IF Rev THEN EXIT FOR
NEXT
IF Rev THEN
IF i = tot THEN
PRINT #1, " *";
ELSE
PRINT #1, " rev"; i;
END IF
END IF
END IF
PRINT #1,
NEXT
PRINT #1, STRING$(maxCol * 3, "-")
END SUB
|
|
Posted by Charlie
on 2003-08-21 08:56:00 |
solution
