On a 4 x 4 board what is the longest and the shortest 'tour' that a knight may make subject to no valid next destination being available, and not being able to revisit a prior square. The knight starts in the top left cell (A).

A B C D E F G H I J K L M N O P

Dismissing mirrored tours (A-P being the mirror) how many such routes are there?

The program below was initially seeking better and better (shorter and longer) paths, but when it was determined that the shortest and longest were 7 and 15 positions respectively (including the starting and ending positions, so one higher than the number of moves), the program was changed to its current form of choosing only lengths of 7 and 15. Mirrors are excluded by requiring the first move to be from A to G.

DECLARE SUB move ()
DIM SHARED b(4, 4), currR, currC, h$, least, shortH$, most, longH$, sCt, lCt

currR = 1: currC = 1: h$ = "A": b(1, 1) = 1
least = 9999: most = 8

CLS
move
PRINT sCt, lCt

END

 

SUB move
 didOne = 0
 FOR dr = -2 TO 2
   IF dr <> 0 THEN
     absdc = 3 - ABS(dr)
     FOR dc = -absdc TO absdc STEP 2 * absdc
       r = currR + dr: c = currC + dc
       IF r > 0 AND r <= 4 AND c > 0 AND c <= 4 THEN
        IF b(r, c) = 0 THEN
          currR = r: currC = c
          h$ = h$ + MID$("ABCDEFGHIJKLMNOP", (r - 1) * 4 + c, 1)
          b(r, c) = 1

          didOne = 1
          move

          b(r, c) = 0
          h$ = LEFT$(h$, LEN(h$) - 1)
          currR = currR - dr: currC = currC - dc
        END IF
       END IF
     NEXT
   END IF
 NEXT dr
 IF didOne = 0 THEN
 IF LEN(h$) = 7 OR LEN(h$) = 15 THEN
  IF MID$(h$, 2, 1) = "G" THEN
   IF LEN(h$) <= least THEN
    least = LEN(h$): shortH$ = h$
    PRINT "short: "; h$, LEN(h$)
    sCt = sCt + 1
   END IF
   IF LEN(h$) >= most THEN
    most = LEN(h$): longH$ = h$
    PRINT "long: "; h$, LEN(h$)
    lCt = lCt + 1
   END IF
  END IF
 END IF
 END IF
END SUB

short: AGIBHJP               7
long: AGIBHOFDKENLCJP        15
long: AGIBHOFMKENLCJP        15
long: AGIOHBKDFLNECJP        15
long: AGIOHBKMFLNECJP        15
short: AGIOHJP               7
short: AGNECJP               7
long: AGNECLFDKBIOHJP        15
long: AGNECLFMKBIOHJP        15
long: AGNLCEKDFOIBHJP        15
long: AGNLCEKMFOIBHJP        15
short: AGNLCJP               7
long: AGPJCENLFDKBHOI        15
long: AGPJCENLFDKBIOH        15
long: AGPJCENLFMKBHOI        15
long: AGPJCENLFMKBIOH        15
long: AGPJCLNEKDFOHBI        15
long: AGPJCLNEKDFOIBH        15
long: AGPJCLNEKMFOHBI        15
long: AGPJCLNEKMFOIBH        15
long: AGPJHBIOFDKECLN        15
long: AGPJHBIOFDKENLC        15
long: AGPJHBIOFMKECLN        15
long: AGPJHBIOFMKENLC        15
long: AGPJHOIBKDFLCEN        15
long: AGPJHOIBKDFLNEC        15
long: AGPJHOIBKMFLCEN        15
long: AGPJHOIBKMFLNEC        15

There are four of length 7 and twenty-four of length 15.

Posted by Charlie on 2009-05-05 17:34:37