Essays/Knight's Tour

From J Wiki
Jump to: navigation, search

A knight's tour is a traversal by a knight of a chessboard, visiting each square exactly once.


Depth First Search

ktour uses a depth first search strategy, stopping on finding the first solution (or on failing to find a solution).

NB. knight moves for each square of a (y,y) board
kmoves=: 3 : 0
 t=. (>,{;~i.y) +"1/ _2]\2 1 2 _1 1 2 1 _2 _1 2 _1 _2 _2 1 _2 _1
 (*./"1 t e. i.y) <@#"1 y#.t
)

ktour=: 3 : 0
 if. 1>:y do. i.,~y return. end.
 m=. kmoves y
 p=. *:y
 stack=. ,&.>|.y (<:/~@] #&, * +/ ]) i.>.-:y
 while. #stack do.
  s=. >{:stack
  if. a: e. (((i.p)-.s){m)-.&.><s do.
   if. (#s)=p-1 do. (,~y)$/:s,(i.p)-.s return. end.
   stack=. }:stack continue.
  end.
  stack=. (}:stack),(<s),&.>s-.~({:s){::m
 end.
)

For example:

   ktour 8
 0 11  8  5  2 13 16 19
 9  6  1 12 17 20  3 14
30 27 10  7  4 15 18 21
63 24 31 28 35 22 47 44
32 29 26 23 48 45 36 57
25 62 51 34 39 56 43 46
52 33 60 49 54 41 58 37
61 50 53 40 59 38 55 42

s in ktour is a partial tour. Suppose that relative to s there is an unvisited square having no unvisited neighbor. Then that square must be the final destination and must be one knight move from the last element of s . Otherwise, s can not be the prefix of a tour. The lines

  if. a: e. (((i.p)-.s){m)-.&.><s do.
   if. (#s)=p-1 do. (,~y)$/:s,(i.p)-.s return. end.
   stack=. }:stack continue.
  end.

implements this heuristic. ktour 8 executes 302,701 iterations with these lines and 17,739,768 iterations without.

The stack in ktour is initialized to be the squares of the upper northwest octant. By reflectional and transposal symmetry an octant covers all possible starting positions of a tour.

   y=: 8
   ] i=: y (<:/~@] #&, * +/ ]) i.>.-:y
0 1 2 3 9 10 11 18 19 27
   ] t=: (i.y,y) e. i
1 1 1 1 0 0 0 0
0 1 1 1 0 0 0 0
0 0 1 1 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
   (+.|:) (+.|.) (+.|."1) t
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1

Warnsdorff's Algorithm

Warnsdorff's heuristic algorithm was invented by H.C. Warnsdorff in 1823. The heuristic is to choose a successor having the fewest further moves.

ktourw=: 3 : 0
 M=. >kmoves y
 p=. k=. 0
 b=. 1 $~ *:y
 for. i.<:*:y do.
  b=. 0 k}b
  p=. p,k=. ((i.<./) +/"1 b{~j{M){j=. ({&b # ]) k{M
 end.
 assert. ~:p
 (,~y)$/:p
)

For example:

   ktourw 8
 0 25 14 23 28 49 12 31
15 22 27 50 13 30 63 48
26  1 24 29 62 59 32 11
21 16 51 58 43 56 47 60
 2 41 20 55 52 61 10 33
17 38 53 42 57 44  7 46
40  3 36 19 54  5 34  9
37 18 39  4 35  8 45  6

ktourw is very efficient with ktourw 80 running in about 0.1 seconds.

Collected Definitions

NB. knight moves for each square of a (y,y) board
kmoves=: 3 : 0
 t=. (>,{;~i.y) +"1/ _2]\2 1 2 _1 1 2 1 _2 _1 2 _1 _2 _2 1 _2 _1
 (*./"1 t e. i.y) <@#"1 y#.t
)

ktour=: 3 : 0
 if. 1>:y do. i.,~y return. end.
 m=. kmoves y
 p=. *:y
 stack=. ,&.>|.y (<:/~@] #&, * +/ ]) i.>.-:y
 while. #stack do.
  s=. >{:stack
  if. a: e. (((i.p)-.s){m)-.&.><s do.
   if. (#s)=p-1 do. (,~y)$/:s,(i.p)-.s return. end.
   stack=. }:stack continue.
  end.
  stack=. (}:stack),(<s),&.>s-.~({:s){::m
 end.
)

NB. Warnsdorff's algorithm
ktourw=: 3 : 0
 M=. >kmoves y
 p=. k=. 0
 b=. 1 $~ *:y
 for. i.<:*:y do.
  b=. 0 k}b
  p=. p,k=. ((i.<./) +/"1 b{~j{M){j=. ({&b # ]) k{M
 end.
 assert. ~:p
 (,~y)$/:p
)

From http://xkcd.com/761/

Dfs.png



See also


Contributed by Roger Hui.