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

 Knights' Tours - Long & Short (Posted on 2009-05-05)
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?

 See The Solution Submitted by brianjn Rating: 4.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 computer solution | Comment 1 of 7

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               7long: AGIBHOFDKENLCJP        15long: AGIBHOFMKENLCJP        15long: AGIOHBKDFLNECJP        15long: AGIOHBKMFLNECJP        15short: AGIOHJP               7short: AGNECJP               7long: AGNECLFDKBIOHJP        15long: AGNECLFMKBIOHJP        15long: AGNLCEKDFOIBHJP        15long: AGNLCEKMFOIBHJP        15short: AGNLCJP               7long: AGPJCENLFDKBHOI        15long: AGPJCENLFDKBIOH        15long: AGPJCENLFMKBHOI        15long: AGPJCENLFMKBIOH        15long: AGPJCLNEKDFOHBI        15long: AGPJCLNEKDFOIBH        15long: AGPJCLNEKMFOHBI        15long: AGPJCLNEKMFOIBH        15long: AGPJHBIOFDKECLN        15long: AGPJHBIOFDKENLC        15long: AGPJHBIOFMKECLN        15long: AGPJHBIOFMKENLC        15long: AGPJHOIBKDFLCEN        15long: AGPJHOIBKDFLNEC        15long: AGPJHOIBKMFLCEN        15long: AGPJHOIBKMFLNEC        15`

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

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

 Search: Search body:
Forums (0)