champagne wrote:One question as I see you have cross checked all serg's findings.
What has been the process to prove that each of these 40 patterns can not produce puzzles (I know that at least one is trivial).
Is it just reasoning or any other method.
We both used a clever idea that
Red Ed had mentioned years ago.
He used it to show that this pattern (I think) has no puzzles:
- Code: Select all
+-------+-------+-------+
| x x x | x x x | x x x |
| x x x | . . . | x x x |
| x x x | . . . | x x x |
+-------+-------+-------+
| x . . | . . . | . . x |
| x . . | . . . | . . x |
| x . . | . . . | . . x |
+-------+-------+-------+
| x x x | . . . | x x x |
| x x x | . . . | x x x |
| x x x | x x x | x x x |
+-------+-------+-------+
It's a neat idea, but unfortunately it's only practical for patterns with many automorphisms, and a relatively small number of empty cells.
The idea is to show that every "essentially distinct" way of filling the empty cells, either
A) cannot be extended to a complete grid, or
B) contains an unavoidable set.
In the code, the genral idea is enumerate the ED fills for empty cells, and for each one:
1) Treat it as a puzzle, and use a brute force solver, to try to find one solution -- if none exists, condition A is satisfied.
2) If a solution is found, clear the cells that should be empty in the pattern; treat that as a 2nd puzzle; and use the brute force solver to try to find
two solutions. If two solutions exist, then condition (B) is satisfied (and vica-versa). If one solution exists, it's a counterexample to the proposition that the pattern has no valid puzzles.
To see that the method is valid, suppose the pattern had a valid puzzle. Then its solution could be transformed to make the values in the empty cells, match one of the ED empty cell fills -- one that would: A') have an extension to a complete grid, and B') not contain an unavoidable set.
I don't know the details of how
Serg did his testing.
For me, I had special code for each pattern.
It almost always broke the empty cell pattern into 2 overlapping parts, and produced short lists of fills satisfying (A) and (B) above.
[ That was a poor wording: lists where each has an extension to a complete grid, and none contains an unavoidable set ]. Then it then combined fills from each list, them to produce fills for the full empty cell pattern. For some patterns, it was necessary to apply a small set of transformations to the fills from one of the lists, before combining with the fills from the other list. For some patterns, the code finished in seconds, and for others, it took minutes or hours.
As for how to come up with a list of patterns to test, that's another long story.
Also added: About the last paragraph above ... in more detail, the two parts of the empty cell pattern, overlapped in box 1. "Essentially distinct" was also too general. More correct, is essentially distinct with respect to transformations that leave box 1 in its place. Also, for me, the 2nd list was often longer than necessary, depending on how much work I was willing to do in tranforming fills from the first list, before combining them with fills from the 2nd list. For anyone comtemplating trying this, the bit about combining patterns from two lists of "(mostly) essentially distinct" fills, can be very tricky. You need to think carefully, to make sure that in testing the combinations, you are guaranteed to hit a morph of each ED "combined" pattern, at least once -- twice is OK, but you need to ensure that nothing would be missed. Reducing one of the lists by too many "equivalence transformations", can be fatal.
[/quote]