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)

Try a 7x7 board. --Paddy3118 03:24, 31 May 2011 (UTC)

I will. At this point there is something wrong with this solution. I will have to come back to it later (possibly this weekend). This was implemented from the WP description which talks about sets. I think the heart of the problem lies in the used of unordered sets everywhere and I will have to walk through some comparative examples side by side. This wouldn't be the first time I've been burned by a vague WP algorithm description. I'll have to borrow one of the other solutions and add code to show me the order squares get presented. --Dgamey 09:48, 31 May 2011 (UTC)

Confirmed that I sometimes get incomplete tours on 7x7 with Warnsdorff using the move list order in the Perl code. Leaving the any-size-board generalization out of code on page until I handle that case. --Markjreed 12:47, 31 May 2011 (UTC)

I believe that you've got to filter the output of the Warnsdorff algorithm in case it fails to do a tour. (That is, apply the “if at first you don't succeed” principle.) I don't know what the probability of failure is though. You might want to add the checks for impossibility (see the WP page) to your code though. –Donal Fellows 13:50, 31 May 2011 (UTC)

C++ formatting

I edited the C++ to remove some of the changes made. Several are fairly pointless (such as adding const to all the local variables; the compiler is smart enough to figure that out if it even makes a difference), and most were just reformatting it to someone else's formatting preferences (++i vs i++, etc). If there were a sitewide C++ formatting guide (a possibility suggested on the C++ discussion page, but not currently implemented) I (or whoever) can format it to fit that. MagiMaster 03:43, 31 May 2011 (UTC)