Talk:Knight's tour: Difference between revisions
→Incomplete Tours and Warnsdorff
(→C++ formatting: Just pointing out distinctions, and avoiding making direct edits.) |
|||
Line 51:
::: 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. –[[User:Dkf|Donal Fellows]] 13:50, 31 May 2011 (UTC)
:::: The probability of failure depends on the board size and the tiebreak rule (move consideration order, for a first- or last-wins algorithm); for random move selection, it's about 25% on a 7x7 board. The order that I picked happens to work 100% of the time for an 8x8 board, but a general solution requires a more complex algorithm. The Ganzfried paper cited above includes one such, Squirrel's algorithm, which adjusts the ordering of the moves after certain landmarks in the progress of the tour. --[[User:Markjreed|Markjreed]] 02:29, 1 June 2011 (UTC)
== C++ formatting ==
| |||