Wow, that’s a lot of clever optimizations, thanks so much for sharing!
4 Likes
It would need a lot more optimization work to be able to handle 9x9 questions, but you could probably use to answer questions about whether various 1-color fillings of the board are possible for anything 8x8 in or smaller in total area, such as if you want to explore the analogous things on rectangular boards 8x7, 9x7, 10x6, etc, and as well as alternative constraints, e.g. you want 2 groups of some sizes rather than exactly 1 group of each of certain sizes.
Or, maybe it could prove 9x9 questions already, it maybe just has to run for weeks (it’s “only” 1000x factor from 7x7 → 8x8, so if hypothetically it would be another 1000x to go to 9x9 that’s actually not out of the question, although impractical for causal use at that point)
3 Likes
Also I do mean it when I say that it can be optimized a lot further. There’s one particular pruning technique that was itself empirically huge on speeding up the 7x7 benchmarking even in its current form, and I’m sure it could be made much stronger.
The relevant context is that the solver tries to fill in the board in strips from the top left corner to the bottom right corner, tracking how many 0s (empty spaces) it’s used vs 1s (stones). Suppose it has still the indicated question mark spots remaining to fill in with 0s and 1s (and I’ve also drawn the bordering 1s and 0s too that the search has already filled in on the previous layer):
ABCDEFGH
8........
7........
6.......1
5......1?
4.....0??
3.....0??
2....0???
1...1????
Basically the lowerrightmost 4 diagonal strips are remaining to decide how to fill in with stones and empty spaces, plus two spots of the fifth diagonal strip, for a total of 12 spots left. (The dotted area in the upper left is all already filled in with some pattern of 1s and 0s that I haven’t bothered drawing, it’s only the lower right that’s left to fill in). Now, let’s also suppose that the groups of size 7, 8, 9 are all fully accounted for already in the part that’s filled in the dotted area in the upper left that I haven’t fully drawn.
Then, right now the logic would say that we need at least two more empty spaces (0s) in the lower right question marks area. If we only had one empty space there, we can at best split it into only 2 groups, and because our biggest unaccounted for groups are the 5 and 6, and 5+6 = 11 which is less than 12, that’s not good enough, so we need at least two empty spaces.
Then the pruning would check that if the total empty spaces used so far + 2 > the total empty spaces we’re allowed (e.g. 19 of them out of 64), then we can terminate this branch of the search as impossible. This kind of pruning trigger a lot because it will be very common for partial solutions to be inefficient on usage of empty spaces, and so by the time it reaches the corner it will have run too low, and then this criterion can cut off entire rest of the tree search on this branch.
But this is far weaker of deduction logic than should be possible. Like, suppose that we had the 6 and 7 left for largest groups unaccounted for, rather than the 5 and the 6. (e.g. the 6 and 7 would be formed by connecting more stones to the 1s at D4, G5, H6, and would split the question mark space between them). Then, the pruning logic right now would only deduce one empty space in the lower right. Because 6+7 = 13 which is greater than 12, so perhaps the lower right is only split into two groups and thus only needs one empty space to do so.
But… the shape of the region remaining means that you can’t actually split it into a 6 and 7 with only a single empty space! You can chop the region into two pieces with only one empty space, by adding it at F1 or H4, but that would split the unassigned region into pieces of size 1 and 10, and perhaps the piece of size 1 would be filled with a stone and connect to some more stones outside this region and in total form a group of some size, but 10 is still too large of a remaining piece to be one group and would need more splitting. So the pruning should be able to infer at least 2 zeros in that case, but it would fail to do so.
Also, we’re not really taking into account the pattern of 1s and 0s bordering, the more 1s we have, the harder splitting becomes and requires more 0s.
It would also be possible to deduce a minimum remaining empty space usage based on the number of groups unaccounted for as well, and the number of regions therefore that the lower right would have to be split into, but that’s not implemented. I initially had a hypothesis that you can at best split a region into N+1 pieces with N empty spaces, but that’s not true that you can at best split a region into N+1 pieces with N zeros, because here:
.....
.....
....?
...??
..???
2 zeros suffices to split the question marks into 4 pieces:
.....
.....
....?
...?0
..?0?
Adding a minimum zero count check based on something like this number of groups remaining would probably help a bit, if you can come up with a strong generalizable criterion for deducing a minimum of how many.
But anyways, because making these kinds of minimum-zero-count deductions stronger depends on reasoning about the exact shape of the lower right region, I’ve had a hard time articulating a principled and easily provably sound criterion for how to do it a lot better than the logic currently does. If anyone can propose significantly better criteria here, it would likely lead to large improvements in the exhaustive search.
3 Likes
Considering arbitrary shapes, it’s 1+3N pieces for N 0s. But that’s most likely not a sharp criterion.
. . . . . . . ? . . . . ? . .
. ? . . . . ? 0 ? . . ? 0 ? .
. . . . . -> . . ? . . -> . . ? . .
. . . . . . . . . . . ? 0 ? .
. . . . . . . . . . . . ? . .
Assuming (a,b) in Region => (a+i, b+j) in Region for i, j >= 0 the best case seems to be:
Region is a right-angled isosceles triangle with leg length K. Use K-1 0s to split off the positions on the hypotenuse, get K pieces on the outside, 1 piece on the inside. The inside piece is a similar triangle with leg length K-2, split it recursively.
Assuming K is even:
K = 2, N = 1 => 2 pieces
K = 4, N = K - 1 + 1 = 4 => K + 2 = 6 pieces
K = 6, N = K - 1 + 4 = 9 => K + 6 = 12 pieces
K = 8, N = K - 1 + 9 = 16 => K + 12 = 20 pieces
Hypothesis: Number of pieces <= N + ceil(sqrt(N))
Example (where K=5 is odd, but the hypothesis still holds):
. . . . ?
. . . ? 0
. . ? 0 ?
. ? 0 ? 0
? 0 ? 0 ?
1 Like