Thanks Raul, as always, for your comments.
I realize that the comments in the code do not explain what I am
doing, so here's a shot.
I calculate all possible placements of each shape on the board, and
call this a "piece". I also find the board graph, where the vertices
are cells, and there is an edge if the cells are neighbors.
Some pieces are bad in that they leave the empty cells with connected
components ("islands") that are not all multiples of 5: we detect and
remove these. We also precalculate whether a pair of pieces has
non-empty intersection.
The problem is to find all 2098 solutions, not any solution (as in the
Knight's Tour). I use the following method (xtend1):
Given a current position (which can be described by a list of piece
numbers), I find the first empty cell. I have previously calculated
all the pieces which begin at this cell, and I select only the unused
shapes. For each of these candidate piece numbers, I check for
non-intersection with the existing position. This is done through
table lookup. Each survivor is appended to a copy of the existing
list. For breadth first search, we extend the list of lists (xtend);
for depth first search we extend one and stack the rest.
The fast solutions have used extensive calculation of islands. I know
a number of ways to do this in J, but none has proved fast enough.
Similarly if I precompute bad pairs of pieces (those giving bad
islands) I can drastically reduce the run time at the much greater
cost of doing the precomputation. Part of the reason for using the
first empty cell to continue a position was to reduce the number of
bad islands lying undetected for a long time.
I agree that using symmetry should speed things up by a factor of 4,
but the rest is still too slow.
Any help would be appreciated.
Best wishes,
John
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
