Hi, people!
dobrichev, thank you for your help! The task of doing exhaustive search for the pattern having 2 whole filled bands and the rest band with 2 empty boxes and one non-empty box, which must contain given clue's configuration, is not so complicated. You described surely possible method of searching. I used similar, but slightly different method.
First of all, if a pattern has 2 different puzzles which have the same completions (variants of empty cells filling), those puzzles have the same number of solutions with the same completitions. (It can be proved.) So, it is not necessary to check out all possible puzzles for given pattern. It is sufficient to check out (does a puzzle have unique or multiple solutions?) puzzles having different completions only. For a given completion it is sufficient to check out arbitrary puzzle having this completion, because all puzzles of the same pattern having the same completions have the same number of solutions.
It is convenient to study completions for patterns considered because these patterns have large number of filled cells (54+). If a pattern would have less than a half of grid cells (40 or less cells), it would be more convenient to check out puzzles instead of completions.
Overall procedure of exhaustive search for puzzles having unique solutions (for given pattern) should looks like the following.
1. Loop over all completions (partially filled band B123).
2. For each completion we must find solution grid treating completion's cells as clues and other cells - as empty cells.
3. Found solution then should be transformed to a puzzle by setting empty all cells not participating the pattern.
4. Then we should find solutions (no more than 2 solutions) of the produced puzzle.
5. If the produced puzzle has unique solution - given pattern has valid puzzles, if it has multiple solutions (2 solutions at least) we should go to the step 1 to consider next completion.
Band B123 of any solution grid can be transformed to lexicographical order (see article "Mathematics of Sudoku I" by Bertram Felgenhauer and Frazer Jarvis). So, we can consider not completions, but whole filled bands B123:
- Code: Select all
+-----+-----+-----+
|1 2 3|4 A B|C D E|
|4 5 6|x x x|x x x|
|7 8 9|x x x|x x x|
+-----+-----+-----+
where A > 4, B > A, D > C, E > D.
It is well known that there are 36288 non-isomorphic such band configurations (see "Mathematics of Sudoku I").
Refined procedure of exhaustive search for puzzles having unique solutions for given pattern consists of 2 parts.
Part 1
1. Loop over 36288 non-isomorphic lexicographically ordered band configurations.
2. For each band configurations find solution grid treating band's cells as clues and other cells - as empty cells. Write to the file all solution grids (36288).
Both steps are done by simple backtracking solver. This procedure takes less than 1 second.
Part 2
3. Read solution grids from the file.
4. Tansform each solution grid to a puzzle by setting empty all cells not participating the pattern.
5. Find solutions (no more than 2 solutions) of the puzzle. (Done by simple backtracking solver.)
6. If the puzzle has unique solution - given pattern has valid puzzles, if the puzzle has multiple solutions (2 solutions at least) - continue loop - go to the step 3.
This procedure takes about 1 second.
Surely it is possible to use 416 band configurations, but this approach has some disadvantages. For example, instead of using permanent box B1 pattern, we must check out 6 x 6 = 36 variants of box pattern (to account for all possible rows/columns permutations in the box B1). Additionally we must repeat this procedure for all 3 boxes (B1, B2, B3). So, 416 variants transformes to 36 x 3 x 416 = 44928 variants (slightly more than 36288).
When box pattern has some symmetry, we can reduce number of generated solution grid several times. But it is not worth doing because of short execution time of the program.
When I've done exhaustive search for the pattern having 2 whole filled bands and the rest band with 1 empty box and 2 boxes containing only 1 filled cell each, I could not use lexicographically ordered band because r2c4 clue prohibits swapping boxes B2/B3 and swapping column c4 with c5/c6 columns. So, we have such band B123 configuration.
- Code: Select all
+-----+-----+-----+
|1 2 3|x A B|C D E|
|4 5 6|x x x|x x x|
|7 8 9|x x x|x x x|
+-----+-----+-----+
where B > A, D > C, E > D.
There are 217728 such configurations. We can reduce this number twice by rejecting isomorphic configurations because of possible swapping columns c2/c3 and relabelling (to restore right digits order in the box B1). Program execution time - less 5 seconds.
Serg
Edited: I corrected some typos.
