| This is a classic problem going back centuries. Its called the problem
of the "Knight's Tour". There are two major variants (with lots of
minor ones, e.g., looking for tours with bilateral symetry), the open
tour and the closed tour. In the closed tour, you must return to your
starting square.
There are lots of heuristics that allow you to find *a* solution more
quickly, with Dan's being one of the best. There are also many
techniques which allow you to avoid bad choices or back out of them
quickly -- these make searching programs quite practical. Here is
one:
Do your work on a single static chessboard data structure which records
where you move from a given square if that has been decided, which
squares are accesible with a knight's move (whether or not those
squares are currently filled) and, for as yet unvisited squares, the
number of unvisited squares accessible from that square. Each
recursively applied move should modify the data structure and then
restore it before returning to the previous move.
Anytime a square has an accessibility of two, it should be immediately
connected to those two squares -- even though this may not connect
(yet) to the continuous path. If the accessibility of any square drops
below 2, the last step should be backed out of. (If an open knights
tour is being done, some extra work must be done here).
This results in a fairly practical program, with only moderate work.
Topher
|
| re .4,
>> with Dan's being one of the best.
If you read the possessive there as suggesting I
discovered it, well, I didn't. :-) I remember reading
about and implementing the heuristic, but it was in the
late 70's and I have no recollection what the source was.
Dan
|