Talk:Knight's tour

Wow, this was found fast. I was still prepping my first couple implementations.:) Markjreed 02:09, 30 May 2011 (UTC)

Added my original perl solution and sample output; moved out of draft status. Markjreed 02:48, 30 May 2011 (UTC)

References

The following had more than I needed to know about the problem A Simple Algorithm for Knight’s Tours by Sam Ganzfried. --Paddy3118 07:22, 29 May 2011 (UTC)

I discovered this weekend that Warnsdorff sometimes generates incomplete tours. This is discussed in Granzfried (above) and also in Mordecki.

[http://www.cmat.edu.uy/~mordecki/articles/warnsdorff.pdf Counting Knight's Tours through the Randomized Warnsdor� Rule, Cancela & Mordecki, 2006] --Dgamey 11:05, 30 May 2011 (UTC)
Estimating the efficiency of backtrack programs, Knuth, 1974 --Dgamey 11:36, 30 May 2011 (UTC)
Knight's Tours, Hill & Tostado, 2004 --Dgamey 19:56, 30 May 2011 (UTC)

Incomplete Tours and Warnsdorff

While implementing the Icon/Unicon version over the weekend, I noticed that the algorithm frequently produced incomplete or dead-ended tours. A little investigation proved insightful:

backtracking unless it can be limited dramatically will be inefficient (Knuth)
the order the Knight's moves are presented for selection (beyond accessibility) appears to have an effect (Granzfried)
the algorithm can be probabilistically tuned (Mordecki)
most papers investigating Warnsdorff indicate that it is imperfect

I haven't measured the hit/miss rate of the Unicon version of the algorithm. There are some aspects that differ from other implementations posted that may be responsible. It would be interesting to compare completion rates of the various implementations. Possible areas of consideration/cause for variance in efficiency:

using ordered sets to resolve tie breakers. The method (in Unicon) used to generate the 8 possible Knight moves is different and other implementations tend to present them in a given order.

--Dgamey 13:21, 30 May 2011 (UTC)

I did implement Roths extension, which is to break ties by chosing the point furthest from the centre:

<lang python>def accessibility(board, P, boardsize=boardsize, roths_extension=True):

   access = []
   brd = copy.deepcopy(board)
   for pos in knightmoves(board, P, boardsize=boardsize):
       brd[pos] = -1
       if not roths_extension:
           access.append( ( len(knightmoves(brd, pos, boardsize=boardsize)),
                            pos ) )
       else:
           access.append( ((len(knightmoves(brd, pos, boardsize=boardsize)),
                            -(complex(*pos) - (boardsize/2. + boardsize/2.j)).__abs__()),
                           pos) )
       brd[pos] = 0
   return access</lang>

I didn't really have time to measure its effectiveness though. --Paddy3118 13:27, 30 May 2011 (UTC)

The Perl solution is deterministic, and produces complete tours for all 64 start squares. So it must be something in the ordering of the move list. Markjreed 01:54, 31 May 2011 (UTC)