All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > General
Knight's Tour (Posted on 2003-08-21) Difficulty: 5 of 5
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)

See The Solution Submitted by Gamer    
Rating: 4.2500 (4 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution solution | Comment 1 of 4
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
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (3)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information