Ah yes this thread, I sort of forget to ever update it.
Ok, in a sort of high level overview, the best algorithm I know for generating instances is this:
- generate a fully filled in board (using that pseudocode algorithm from the opening post, there are some issues)
- try some random subsets of those bits as instances, try to solve them to find out whether they're solvable instances
- from all solvable instances, take the hardest one
So, how to select a fully filled board.
In 8x8 puzzles, there are only 4111116 such configurations (much fewer if you don't count symmetric solutions, there are many sorts of symmetry). For other sizes, the number is similarly "unexpectedly low" (compared to the full 2^size)
Select a random number up to the number of possible configurations, generate boards in lexicographical order until you reach that index (alternatively: store them all in the program, that array is pretty small). That's surprisingly fast if you use the following tricks:
- consider only valid rows. There's no point in doing it bit by bit. Do a whole row at the time. There are only 34 possible rows of length 8.
- consider only rows that don't immediately violate the no-3-in-a-row rule vertically.
- consider only rows that don't immediately violate the 4-zeroes-per-column rule, using the column-counting approach from the pseudocode in my first post. The last row is implied by the column counts.
Using those 3 tricks, the only constraint you can violate is no-two-equal-columns, that's why I concentrated on that. That's a pretty annoying check to do.
Tip: you can use (797 * row) >> 8 to map the 34 valid length-8-rows to non-overlapping indexes in [0, 64]. Using that, you can check for duplicate columns by
transposing the board and then ORing together 1 << row_to_index(rows in the transposed board). If that has fewer than 8 set bits, at least one column appears twice.
Still it's probably not fast enough (may take a second, or several on slower hardware) and there a big speed difference between high indexes and low indexes. You can cut that time down enormously by storing an array of how many boards there are if you start with a certain row. That array is only 34 (for 8x8) ints long, and is in fact perfectly symmetrical around the middle, so you can store only half of it if you want (not that it matters..)
Changing the indexes of the boards slightly, leaving perfect lexicographical order behind, the symmetry around the middle is due to the fact that the last half of the boards is the same as the first half, but both reversed in order an inverted in its bits. You can cut it in half there, and when generating a random board, choose which half and which index within that half.
Similar trickery can be done with the second row, cutting the time it takes down so much that you can afford to do a binary search over all the boards (you don't need that, I just needed it because I wanted to find the indexes of the rotated and mirrored boards (the index of the inverted board can be found trivially due to the symmetry that I already mentioned) - I was building a database with Very Hard Instances and thought I might as well put all symmetrically equivalent boards in it as well).
Then, how to solve an instance.
Filling the cells implied by the no-3-in-a-row rule is easily done with some bitmath.
The rest is more complicated, but it can still be done iteratively. No need to do a recursive search.
For this, I use a lookup table to handle all cases where cell(s) can be filled in just to do knowledge about the row it's in. That handles everything you can fill in using any combination of no-3-in-a-row and 4-zeroes-per-row.
That doesn't do everything, obviously. First, it disregards columns, but that's easy: just transpose the board and try again.
Second, it disregards things you can know from the no-equal-rows rule. For that I enumerate all possible rows, test them against the currently filled in cells in the row, then against any surrounding rows for the no-3-in-a-row rule, then against the currently already completed rows, and then against the column-counts. If it passes all those tests, then it's possible to fill in this row here. All possible rows for one position are combined to see if they have any bits that are always the same, those bits are "filled in".
Then the board is transposed and the same is done for the columns. Until either there is no change or the board is completely filled. If it's completely filled, then the instance is solvable.
Ok, so now, how to test how hard an instance is.
For this, I actually generate the specific moves that you would play. A "move" is when you have some reason to fill in a cell. Generating actual moves is harder and especially more verbose than implicitly having moves as in the solver. And there's an other problem: when there are multiple moves, not all of them are created equal - some lead to easier total paths to the end. To avoid scoring puzzles too high, I use A* to find the easiest path to the solution (A* yes so it has a heuristic - a very bad one though, the number of cells currently not filled in. That only works if you score the hardness of moves in a certain way. Be very careful that you don't accidentally make a non-admissible heuristic, I spent several days debugging that).
Show Posts
