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?

(In reply to computer solution by Charlie)

While all the 15-position paths (14 moves) have either D or M as their one missing square, so that none includes both D and M, 13-move paths (which include 14 squares) include some in which both D and M are present, but all of these terminate with either the D or the M:

AGIBHJCENLFDKM
AGIBHJCENLFMKD
AGIBHJCLNEKDFM
AGIBHJCLNEKMFD
AGIOHJCENLFDKM
AGIOHJCENLFMKD
AGIOHJCLNEKDFM
AGIOHJCLNEKMFD
AGNECJHBIOFDKM
AGNECJHBIOFMKD
AGNECJHOIBKDFM
AGNECJHOIBKMFD
AGNLCJHBIOFDKM
AGNLCJHBIOFMKD
AGNLCJHOIBKDFM
AGNLCJHOIBKMFD
AJCENGIBHOFDKM
AJCENGIBHOFMKD
AJCENGIOHBKDFM
AJCENGIOHBKMFD
AJCLNGIBHOFDKM
AJCLNGIBHOFMKD
AJCLNGIOHBKDFM
AJCLNGIOHBKMFD
AJHBIGNECLFDKM
AJHBIGNECLFMKD
AJHBIGNLCEKDFM
AJHBIGNLCEKMFD
AJHOIGNECLFDKM
AJHOIGNECLFMKD
AJHOIGNLCEKDFM
AJHOIGNLCEKMFD

Posted by Charlie on 2009-05-05 17:51:17