On 5/27/07, Devon McCormick <[EMAIL PROTECTED]> wrote:
http://www.jsoftware.com/jwiki/MeteorPuzzlePreliminaries .
Yeah, essentially I've been thinking of the problem as: [1] Construct all possible boards with one piece on it. There's a few hundred possible boards for each piece, so a total of a few thousand possible boards. [2] Find all non-overlapping combinations of these boards. The problem is that "non-overlapping" isn't much of a constraint by itself -- search space fans out rather quickly. So you get significant advantage from eliminating possibilities early on. For example: If a piece on a board marks off an open position which can't be covered by any other non-overlapping pieces, that board position is irrelevant. Also, if the pieces on a board divide the board into regions which are not an even multiple of five, that combination can be discarded. (I think I can do this by doing transitive closure on reachable open positions, then examining the size of connected regions.) Finally, unfortunately, J doesn't pack bit vectors, so its notation is less convenient than I'd like. (This exercise has strongly tempted me to write up a model for packed bit vectors for each of J's significant boolean primitives. Also, personally I think I could live with a constraint that "if the last dimension of a multi-dimensional bit array is less than four, boolean arrays will be less efficient than historically." Since, at least hypothetically speaking, this only matters for large boolean arrays, and arranging for a different axis to be last should often be possible. -- Raul ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
