Valid puzzles for Fractal Pattern

Everything about Sudoku that doesn't fit in one of the other sections

Valid puzzles for Fractal Pattern

Postby Serg » Sat Apr 02, 2011 12:10 pm

Hi, all!
There is well-known Fractal Pattern, having valid 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|
+-----+-----+-----+

I think the problem of finding all valid puzzles for this pattern is rather difficult. blue has done exhaustive search for this pattern (by specially written program) and published his results at "Search for maximal pattern, containing both diagonals" in May, 2010. Maybe he was the first who solved this problem. It turns out that this pattern has 7 non-isomorphic valid puzzles only. Here are all valid puzzles posted by blue.
Code: Select all
120000000450000000009000000000063051000500700000082036000300900000026018000091047
120000000450000000009000000000010080000307201000502607000409806000020040000701502
120000000450000000009000000000302760000010002000406530000090006000804910000501340
120000000450000000009000000000302760000010002000406530000090006000801940000504310
120000000450000000009000000000302560000010002000406730000090006000804910000501340
120000000450000000009000000000302560000010002000406730000090006000801940000504310
120000000450000000009000000000086031000500700000023056000300900000062018000091047

This is the case when random search (generation) doesn't work properly because valid puzzles are very rare (according to my estimates this pattern has about 650 billions non-isomorphic puzzles (valid and not valid)).

blue was so kind to publish algorithm he used for exhaustive search (see cited above thread at setbb.com/sudoku forum). I implemented blue's algorithm and cross-checked results. I've found the same 7 valid puzzles. Here they are in canonicalized form (by gsf's "sudoku" tool, command line: "sudoku -f%#mc my_puzzles.txt >my_puzzles_canon.txt").
Code: Select all
........1......23.......45...1..2...23.46....57.83......6..4...32.68....81.59....
........1......23.......45...1..2...23.46....57.83......6..4...32.68....81.95....
........1......23.......45...1..2...23.46....75.83......6..4...18.59....32.68....
........1......23.......45...1..2...23.46....75.83......6..4...18.95....32.68....
........1......23.......45...1..6...23.47....68.39......7..4...15.98....39.75....
........1......23.......45...1..6...23.47....68.93......7..4...19.58....35.79....
........1......23.......45...2..4...14.26....56.37......5..8...83.92....92.64....

This is the first puzzle in the list presented in more readable form:
Code: Select all
+-----+-----+-----+
|2 . 3|. . .|4 . 6|
|. 1 .|. . .|. 2 .|
|5 . 7|. . .|8 . 3|
+-----+-----+-----+
|. . .|2 . 3|. . .|
|. . .|. 1 .|. . .|
|. . .|4 . 5|. . .|
+-----+-----+-----+
|3 . 2|. . .|6 . 8|
|. 6 .|. . .|. 4 .|
|8 . 1|. . .|5 . 9|
+-----+-----+-----+

So, it took me about 3 months to code program and cross-checked results. Pure CPU time of program running - about 5 hours. The first goal of my posting is to confirm blue's results. But I have the second goal of my posting too. Maybe someone can observe some rules of the puzzles forming. Why are there namely 7 valid puzzles? It is very wondering.

Serg
Serg
2017 Supporter
 
Posts: 513
Joined: 01 June 2010
Location: Russia

Re: Valid puzzles for Fractal Pattern

Postby Serg » Sun Apr 03, 2011 8:22 am

Addendum.
These are all Fractal Pattern's valid puzzles in readable form.
Code: Select all
2 . 3 . . . 4 . 6       2 . 3 . . . 4 . 6       2 . 3 . . . 4 . 6
. 1 . . . . . 2 .       . 1 . . . . . 2 .       . 1 . . . . . 2 .
5 . 7 . . . 8 . 3       5 . 7 . . . 8 . 3       7 . 5 . . . 8 . 3
. . . 2 . 3 . . .       . . . 2 . 3 . . .       . . . 2 . 3 . . .
. . . . 1 . . . .       . . . . 1 . . . .       . . . . 1 . . . .
. . . 4 . 5 . . .       . . . 4 . 5 . . .       . . . 4 . 5 . . .
3 . 2 . . . 6 . 8       3 . 2 . . . 6 . 8       1 . 8 . . . 5 . 9
. 6 . . . . . 4 .       . 6 . . . . . 4 .       . 6 . . . . . 4 .
8 . 1 . . . 5 . 9       8 . 1 . . . 9 . 5       3 . 2 . . . 6 . 8


2 . 3 . . . 4 . 6       2 . 3 . . . 4 . 7       2 . 3 . . . 4 . 7
. 1 . . . . . 2 .       . 1 . . . . . 6 .       . 1 . . . . . 6 .
7 . 5 . . . 8 . 3       6 . 8 . . . 3 . 9       6 . 8 . . . 9 . 3
. . . 2 . 3 . . .       . . . 2 . 3 . . .       . . . 2 . 3 . . .
. . . . 1 . . . .       . . . . 1 . . . .       . . . . 1 . . . .
. . . 4 . 5 . . .       . . . 4 . 5 . . .       . . . 4 . 5 . . .
1 . 8 . . . 9 . 5       1 . 5 . . . 9 . 8       1 . 9 . . . 5 . 8
. 6 . . . . . 4 .       . 7 . . . . . 4 .       . 7 . . . . . 4 .
3 . 2 . . . 6 . 8       3 . 9 . . . 7 . 5       3 . 5 . . . 7 . 9


1 . 4 . . . 2 . 6
. 2 . . . . . 4 .
5 . 6 . . . 3 . 7
. . . 2 . 3 . . .
. . . . 1 . . . .
. . . 4 . 5 . . .
8 . 3 . . . 9 . 2
. 5 . . . . . 8 .
9 . 2 . . . 6 . 4


Serg
Serg
2017 Supporter
 
Posts: 513
Joined: 01 June 2010
Location: Russia

Re: Valid puzzles for Fractal Pattern

Postby dobrichev » Sun Apr 03, 2011 10:52 am

Hi,

This approach has something in common to my attempts to exploit band completions.

Enumerating 5-clue band completions we found there are 3483430 possibilities covering all 416 bands (the total of 54+5 column in the referenced post).
Exploiting the Fractal Pattern's property that the middle band crosses middle stack with exactly 5 clues located entirely in the crossing box 5, we can enumerate the possible bands that could be completed with these 5 clues. In other words we can filter the 3483430, removing all completions that have clues in more than one band, different than 2+2+1 column and row distribution, and finally the same min-lex pattern.
After filtering, 1265 valid band completions remain. Below is the distribution by band.
Hidden Text: Show
Band nCompletions
1 0
2 0
3 0
4 0
5 0
6 0
7 0
8 0
9 0
10 0
11 0
12 0
13 0
14 0
15 0
16 0
17 0
18 0
19 0
20 0
21 0
22 0
23 0
24 0
25 0
26 0
27 0
28 0
29 0
30 0
31 0
32 0
33 0
34 2
35 0
36 0
37 3
38 0
39 0
40 2
41 0
42 0
43 1
44 0
45 0
46 2
47 0
48 0
49 2
50 0
51 0
52 2
53 0
54 0
55 3
56 0
57 0
58 2
59 0
60 1
61 0
62 0
63 2
64 0
65 4
66 1
67 0
68 4
69 0
70 4
71 1
72 0
73 3
74 0
75 4
76 2
77 0
78 3
79 2
80 3
81 0
82 1
83 0
84 0
85 3
86 0
87 2
88 0
89 4
90 0
91 1
92 0
93 0
94 0
95 0
96 2
97 0
98 0
99 2
100 0
101 0
102 0
103 2
104 0
105 0
106 0
107 2
108 0
109 0
110 2
111 1
112 2
113 0
114 2
115 0
116 0
117 2
118 2
119 0
120 4
121 2
122 0
123 2
124 0
125 4
126 0
127 1
128 4
129 4
130 4
131 2
132 3
133 0
134 3
135 2
136 0
137 0
138 0
139 0
140 0
141 3
142 8
143 8
144 1
145 8
146 7
147 6
148 0
149 4
150 9
151 3
152 0
153 4
154 8
155 8
156 3
157 4
158 5
159 7
160 0
161 0
162 8
163 4
164 3
165 6
166 4
167 0
168 0
169 7
170 8
171 0
172 4
173 7
174 3
175 0
176 3
177 4
178 4
179 7
180 6
181 3
182 4
183 0
184 0
185 5
186 2
187 0
188 0
189 2
190 4
191 2
192 0
193 1
194 8
195 4
196 0
197 0
198 2
199 8
200 0
201 8
202 2
203 2
204 2
205 5
206 3
207 9
208 4
209 4
210 5
211 7
212 6
213 0
214 2
215 3
216 8
217 0
218 0
219 0
220 0
221 0
222 0
223 0
224 0
225 0
226 0
227 0
228 0
229 0
230 0
231 0
232 0
233 0
234 0
235 0
236 0
237 0
238 0
239 0
240 0
241 0
242 1
243 2
244 4
245 0
246 3
247 0
248 3
249 1
250 1
251 2
252 0
253 0
254 0
255 4
256 0
257 4
258 1
259 0
260 0
261 4
262 3
263 5
264 3
265 7
266 4
267 6
268 4
269 1
270 8
271 2
272 2
273 4
274 2
275 0
276 4
277 4
278 6
279 8
280 4
281 8
282 2
283 3
284 4
285 8
286 2
287 0
288 0
289 0
290 2
291 2
292 1
293 2
294 0
295 2
296 3
297 5
298 0
299 2
300 4
301 6
302 0
303 6
304 4
305 0
306 0
307 0
308 8
309 0
310 6
311 5
312 6
313 4
314 2
315 8
316 8
317 5
318 7
319 7
320 2
321 7
322 3
323 3
324 2
325 4
326 0
327 2
328 7
329 8
330 9
331 3
332 2
333 4
334 11
335 2
336 4
337 3
338 6
339 3
340 9
341 5
342 6
343 8
344 6
345 8
346 0
347 3
348 18
349 15
350 6
351 15
352 16
353 11
354 12
355 10
356 9
357 9
358 4
359 0
360 8
361 12
362 5
363 8
364 13
365 4
366 12
367 3
368 8
369 12
370 6
371 10
372 1
373 7
374 4
375 6
376 12
377 8
378 10
379 6
380 6
381 14
382 15
383 8
384 7
385 10
386 8
387 9
388 10
389 15
390 7
391 6
392 6
393 4
394 10
395 2
396 15
397 2
398 4
399 6
400 6
401 10
402 3
403 1
404 0
405 5
406 1
407 6
408 6
409 3
410 2
411 2
412 0
413 0
414 0
415 0
416 0
Total= 1265

Next task is to cross the bands having valid completions. For simplicity, like blue, I am placing the original box5 at box1.
Stacks are formed by bands after
a) transpose and move to leftmost (convert band to stack), 1 alternative
b) permute boxes, moving each box to the top (3 alternatives, composition of boxes 4,7 doesn't matter)
c) permute rows in box1 (6 alternatives)
d) permute three columns (6 alternatives)
with total 3*6*6=108 stack permutations.

The loops are:
Code: Select all
for each band having valid 5-clue completion {
  for each stack having valid 5-clue completion and index >= band {
    for each of three band box permutation {
      if there is no any valid band completion with clues in box1 for this permutation skip this permutation
      for each 108 stack permutations {
        relabel stack matching the values in the crossing box1
        form a subgrid with boxes 1,2,3,4,7 fixed (band, current band permutation, stack, current stack permutation)
        solve the subgrid up to first solution (all subgrids passed this test)
        for each permuted band completion having clues in box1 and (completion index >= band completion for stack==band) {
          form a puzzle with band clues in box1 and subgrid's solution in boxes 5,6,8,9
          check whether the puzzle has any solution (else there is uncovered UA located entirely in boxes 1,2,3,4,7)
          for each permuted stack completion where all 5 clues match the permuted band clues {
            process all completions of the subgrid with boxes 1,2,3,4,7 fixed
          }
        }
      }
    }
  }
}


I stopped at "process grid" = count grid. 27276660 candidate grids are found in this way for about 4 minutes.
Later each grid should be checked for valid puzzles with the rest of the givens in the Fractal Pattern (original boxes 1,3,7,9 mapped to boxes 5,6,8,9), along with their valid non-isomorphic permutations.

There are possible bugs in my code and my head. I am far not sure the results are correct, but the approach should be right in general.

Cheers,
MD
dobrichev
2016 Supporter
 
Posts: 1316
Joined: 24 May 2010

Re: Valid puzzles for Fractal Pattern

Postby Serg » Tue Apr 05, 2011 11:29 am

Hi, dobrichev!
I should know much more details of your method to answer something definite about it. Both methods look like rather similar.

Serg
Serg
2017 Supporter
 
Posts: 513
Joined: 01 June 2010
Location: Russia

Re: Valid puzzles for Fractal Pattern

Postby dobrichev » Tue Apr 05, 2011 5:29 pm

Hi,

I modified a more general code for generating puzzles by crossing bands.
The idea is to start from "valid band completions". A valid band completion is a subgrid with givens located in one band and known band completion (one of 416 bands). It is not necessary completion to be minimal (i.e. it can contain redundant givens), but the completion guarantees that all unavoidable sets located entirely within the band are covered.
Extending to 9x9 grid, we can compose it band by band.
In order to narrow the search space, a band is crossed to a stack so the crossing box have the same givens.
More givens in the crossing box are narrowing the search space. An empty crossing box doesn't help at all.

Let cross bands A and B, transposing B to become a stack.
Location of the crossing box doesn't matter (it generates isomorphic grids and puzzles) so we can choose the top left box.
There are 3 choices to select the crossing box from band A.
The row and column transformations of band A doesn't matter.
Relabeling can be done by fixing Box1 to contain 1..9 or, as I did, to leave A in its canonical form and relabel B.
The permutations of rows of the stack B in boxes 4 and 7 doesn't matter.
The rest 108 permutations are described in the above post.
Crossing A to B is isomorphic to crossing B to A, so B >= A additionally truncates the search space.
The next task is to loop over the A and B completions a and b.
When B == A then crossing completion a to completion b is isomorphic to crossing b to a, so at completion level b >= a also works.
Predefined completions a and b are transformed in the same way as A and B respectively.
b not matching a in the crossing box1 are skipped.

At this point we have a subgrid with:
- fixed Band1 and Stack1 cell values;
- fixed givens in Band1 and Stack1.
Unsolved part is to generate valid puzzles which solution grids have the same Band1 and Stack1, givens in Band1 and Stack1 fixed, and more givens in boxes 5,6,8,9 in still unknown positions and with still unknown values.
We can verify that the task is solvable by adding clues in all 36 questionable positions, selecting the values from any valid solution of the puzzle P1 formed by all known 45 cell values in Band1 and Box1. If P1 has no solution, then A and B are incompatible in their respective permutations. Later form another puzzle P2 by emptying in the P1's solution all cells in Band1 and Box1 except the fixed givens. If P2 has multiple solutions, then there are uncovered UA sets located entirely in Band1 and Stack1, which can't be covered by any combination of givens in boxes 5,6,8,9.

At this point all solutions of the puzzle P1 are grid candidates for puzzles.
More complex morphs are skipped by brute force. After A and B are fixed (but not their permutations), I start keeping the identity part of each "successful" grid candidates in cache and skip next occurrences of the grid candidates with the same identity. The identity I am using is the minlex representation of the puzzle P1 with givens (sets a and b) removed. I am not ready to prove whether this is sufficient and never gives false positives, but hope it is.

Up to here it was the generic algorithm.

Now to Fractal Pattern specifics.

All band completions not isomorphic to
Code: Select all
101 000 000
010 000 000
101 000 000
as described in the above post, are filtered out.

From the 3 possible band A box permutations, only this with candidates a located in Box1 is used.

The positions of the givens within boxes 5,6,8,9 are independent of the rest of the subgrid, and have only 81 non-isomorphic permutations.
Using this shape as a basis
Code: Select all
xxx ... ...
xxx ... ...
xxx ... ...

... *.* *.*
... .*. .*.
... *.* *.*

... *.* *.*
... .*. .*.
... *.* *.*

the permutations are product of the following independent exchanges:
null, r4<>r5, r5<>r6 (3 choices)
null, r7<>r8, r8<>r9 (3 choices)
null, c4<>c5, c5<>c6 (3 choices)
null, c7<>c8, c8<>c9 (3 choices)
= 3*3*3*3 = 81
These 81 predefined clue position templates are tested against each solution grid.

After fixing a bug, the grid candidates expanded to 49 350 388, and the solver is called 49350388 * 81 = 3 997 381 428 times.

In attempt to understand blue's caching, I tried (w/o actual solving) grid identity as Band1 and Stack1 populated, without removal of the givens in Box1. It resulted in 49 333 619 grids, slightly less than the other identity.

The pass took 13h 30' on my slow machine, confirming the published 7 puzzles.
Without actual solving over the 81 templates, the execution time is less than 4 minutes, including 40 seconds for band completions generation.
The only optimization in the solver is, knowing one of the solutions, to guess to the known solution until it found it, which speeds up the process in this case for about 15%. No small UA sets are generated. Will test whether for 81 puzzles per grid UA testing helps.

MD
dobrichev
2016 Supporter
 
Posts: 1316
Joined: 24 May 2010

Re: Valid puzzles for Fractal Pattern

Postby Serg » Wed Apr 06, 2011 9:12 pm

Hi, dobrichev!
dobrichev wrote:Enumerating 5-clue band completions we found there are 3483430 possibilities covering all 416 bands (the total of 54+5 column in the referenced post).
Exploiting the Fractal Pattern's property that the middle band crosses middle stack with exactly 5 clues located entirely in the crossing box 5, we can enumerate the possible bands that could be completed with these 5 clues. In other words we can filter the 3483430, removing all completions that have clues in more than one band, different than 2+2+1 column and row distribution, and finally the same min-lex pattern.
After filtering, 1265 valid band completions remain.

Would you clarify some details of finding "n-clue band completitions" (please, define more strictly- what is "band completition")? Let's take a band from 416-bands list (for example, the first band). In what way you find all UAs and choose cells to hit all UAs of the band considered (and what variants of hitting cells set do you take into account)? It would be nice to see an example of a band from 416-bands list processing.

Serg
Serg
2017 Supporter
 
Posts: 513
Joined: 01 June 2010
Location: Russia

testing against U4 before solving helps

Postby dobrichev » Wed Apr 06, 2011 10:24 pm

For the case of Fractal Pattern puzzle enumeration, where a batch of 81 puzzles with 25 givens from the same solution grid is tested for uniqueness, using testing again grid's small unavoidable sets increases performance.
The best results are obtained by using only U4 (unavoidable rectangles) where the gain is ~47%. In this case there is no benefit from fast guessing to the known solution. It slightly decreases speed (~ 1%).
The code for U4 generation is posted there.
I also tried with all 2-digit UA generation, and 3-digit 6-cell UA. All combinations of these UA types gave performance gain between 30% and 47%.
The overhead for worst cases is 29% for UA generation + 7% for puzzle scanning for UA before calling the solver.
For the sample of 321508 grids, w/o UA optimization the solver is called 81 times per grid = 26 042 148 times. With optimization the calls are reduced to 13 162 006, or roughly they are halved. For the whole enumeration expected calls are ~1.5 billion.

Cheers,
MD
dobrichev
2016 Supporter
 
Posts: 1316
Joined: 24 May 2010

Re: Valid puzzles for Fractal Pattern

Postby dobrichev » Wed Apr 06, 2011 11:57 pm

Serg wrote:Hi, dobrichev!
Would you clarify some details of finding "n-clue band completitions" (please, define more strictly- what is "band completition")? Let's take a band from 416-bands list (for example, the first band). In what way you find all UAs and choose cells to hit all UAs of the band considered (and what variants of hitting cells set do you take into account)? It would be nice to see an example of a band from 416-bands list processing.


Hi Serg,
n-clue band completions are a kind of extension of your Investigation of one-band-free patterns, but with no limitation clues to be located in only one box of the questionable unpopulated band.
"Band completion" is a clue combination located entirely in one band, which with addition to the clues outside of this band could generate valid puzzles.
Valid puzzles are those with unique solution.
"n-clue band completion" is band completion consisting of n clues, without requirement for minimality.

Finding the band completions is based on exhaustive search within all possible n clue combinations. The algorithm is based on UA sets and is described in GridChecker, an exhaustive puzzle enumerator. It was several months of work, based on previous work by other people on Checker. All published versions are here.
Below is a copy of one post from the other forum, where it is described how GridChecker works.
Hidden Text: Show
How the GridChecker works

Step 1
Collect a list of Unavoidable Sets (UA).


It is possible to work with an external list (loaded from file), or with generated by the program list.

How the program generates UA sets.
1.1. Get UA sets containing up to 5 digits.
1.1.1. Create a puzzle with all occurences of digits {1,2,3,4,5} removed.
1.1.2. Solve the puzzle, storing all possible solutions.
The number of solutions is between 0.3M for more symmetric grids up to 8M for less symmetric.
Grids with more than 10M solutions may exist, but currently 10M is the hardcoded limit.
1.1.3. Compare each solution to the original grid, obtaining one non-minimal UA set per solution.
Actually only the removed digits are compared.
1.1.3.1. Compare the UA found to all previously found UA from the same puzzle.
1.1.3.1.1. If the new UA is a superset of an existing UA, ignore it and continue with next solution.
1.1.3.1.2. If the new UA is a subset of some of the existing ones, remove the respective supresets.
1.1.3.2. Add the new UA to the list of UA for this puzzle.
1.1.4. Add the local list of UA sets found from this puzzle to the global list of UA for the grid.
1.1.5. Repeat step 1.1.1 for all combinations of digits ({1,2,3,4,6}...{5,6,7,8,9}).
Now we have a list of all UA of size up to 11. (UA of size 12 can consist of 6 digits).

1.2. Get UA sets containing cells from up to 5 boxes.
1.2.1. Create a puzzle with all cells from boxes {1,2,3,4,5} removed.
1.2.2. Do the same as with digits removed in step 1.1.

In this way a list of 60K - 700K UA is formed. More symmetrical grids trend to less number of UA.
EDIT: From version 1.4 on the UA are generated by removing 4 (instead of 5) digits at a time, then several thousands times 54 random cells are emptied. This is faster and gives less amount of UA, but more UA of size 12 to 17.

Step 2
Prepare the grid for puzzle enumeration.


Since the enumeration is done by checking all the possible permutations of the given number of clues in the grid, we need to represent the grid in a form which allows as larger as possible areas to be skipped during the enumeration.

2.1. Obtain a list of all possible combinations of mutally disjoint UA sets having maximal number of sets. Inverting the property "disjoint" with "joint" it becomes the Maximal Cliques List, which term is used in the old Checker program and has gained popularity.

2.2. From the Maximal Cliques, choose one having minimal product of the sizes of UA sets.
Note: It is not proven whether this is the optimal choice.

2.3. Rate the UA within the chosen clique, and rate cells within each of the UA in the clique.
2.3.1. Rate UA by its size. Smaller UA have larger rate.
2.3.2. Rate UA having the same size by counting the number of mutally disjoined sets (DJ).
A list of level one DJ is created, which contain all UA having no cell in common to the examined UA.
Then each UA from level one list is compared for common cells to all others in the same list, resulting in level two DJ list.
Then each UA from level one is compared to level two list, resulting in level 3 list.
Level one list is compared to last level list until no DJ UA are found.
A list with the number of distinct DJ sets for the levels is formed and is stored in reverse order - the higher levels are at the top.
The UA with highest level non-empty list is rated first.
For UA with equal non-empty highest level, the one with most entries in the list (larger list size) is rated first.
For UA with still equal rating, the one with most entries in the next list is rated first, and so on.
For UA with still equal rating, the one with DJ sets from level one list, additionally rated by their size is chosen.

2.4. Rate the cells within each UA.
Create a list of UA sets disjoint to all higher rated UA within the clique and all the cells within the current UA except the current cell. Rate each UA within the list by its size (1/size**2), sum the ratings.

2.5. Rate the grid cells cells not included in the slected clique. Use same technique as for cells within UA.

2.6. Remap the grid.
2.6.1. Place the UA sets from the clique by their rating, the cells within UA and these outside the clique by their cell rating. Smaller UA are occuping the first cells, non-clique members occupy the last cells. Keep the mapping table, and create an inverse mapping table.
2.6.2. Remap all the UA sets in the same way.

2.7. Order the UA sets descending by their first cell (after remapping), then ascending by size.

2.8. Filter out largest UA. Choose the size treshold so that at most 1500 UA remain. Leave all the UA of size below the treshold. From the rest UA, erase the rightmost ones so that the final list contain up to 2000 UA sets.

2.9. Calculate tresholds for the number of clues so that at least N clues must be placed in the lower X cells in order at least one clue to hit an UA from the clique.

2.10. Prepare arrays of UA - one with their bitmap, and one with their lower position.


Step 3
Enumerate all puzzles of size N.


Assume a puzzle is a 81-bit binary number with 1 on clue positions and 0 elsewhere.
Assume the less significant bit is at right.
The goal is to check any permutation of N-clues puzzle for uniqueness of its solution.

The enumeration is done by initially placing all clues at right (minimal positions), then moving clues at left until all become in leftmost position.

Basic (naive) approach example for 5 givens:
Code: Select all
Possible positions for the leftmost clue
.............................................................................0000
The rightmost 5 - 1 = 4 cells are reserved for the rest (less significant) clues.

Initial position of the leftmost clue
00000000000000000000000000000000000000000000000000000000000000000000000000001xxxx
Final position of the leftmost clue
1xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
The positions marked with "x" are available for the rest of the clues.

Start of enumeration
000000000000000000000000000000000000000000000000000000000000000000000000000011111
000000000000000000000000000000000000000000000000000000000000000000000000000101111
000000000000000000000000000000000000000000000000000000000000000000000000000110111
...
111101000000000000000000000000000000000000000000000000000000000000000000000000000
111110000000000000000000000000000000000000000000000000000000000000000000000000000
End of enumeration


Since we know that in addition any permutation which leaves at least one unhit UA is invalid, we can skip some areas of the permutation space.

We can divide the process into steps. The implemented approach is:
3.1. Determine a valid position range for the first unplaced clue.
3.1.1. Determine maximal (leftmost) position.
3.1.1.1. Left treshold by previuos clue is the position next to the previous clue, 81 for the first clue.
3.1.1.2. Left treshold by clique is the position guaranted there are sufficient clues to hit the UA to the right.
The smaller of the tresholds is used to fix the upper limit of the range.
3.1.2. Determine minimal (rightmost) position.
3.1.2.1. Right treshold by next clues. There should be a room for the less significant clues.
3.1.2.2. Right treshold by first unhit UA set. Since UA are ordered by their less significant cell, there is no chance the first UA to be hit from the rest of the clues.
The largest of the tresholds is used to determine the lower limit of the range.
3.1.3. If the range is empty (i.e. lower limit exceeds upper limit), then backtrack.

Here is an example for determining the range for the third clue of total 5.
Code: Select all
UA sets in the chosen Maximal Clique
0000000000000000000000000000000000000000000000000000000000000000000< U6 ><U4><U4>

Ordered list of the UA not hit
000001000100010001000001000001000000000000000000000000000000000000000000001000000
000100100010001000000000100010001000000000000000000000000000000000000000000100000
...

Positions of the first two clues
000000000000000000100000000100000000000000000000000000000000000000000000000000000

Steps in determining the valid range
000000000000000000100000000100000000000000000000000000000000000000000000000000000 #more significant clues
0000000000000000000000000000xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx #range 1
0000000000000000000000000000000000000000000000000000000000000000000< U6 ><U4><U4> #clique UA
0000000000000000000000000000000000000000000000000000000000000000000xxxxxxxxxxxxxx #range 2
000000000000000000000000000000000000000000000000000000000000000000000000000000011 #room for the rest 2 clues
0000000000000000000000000000000000000000000000000000000000000000000xxxxxxxxxxxx00 #range 3
000001000100010001000001000001000000000000000000000000000000000000000000001000000 #topmost UA
0000000000000000000000000000000000000000000000000000000000000000000xxxxxxxx000000 #range 4


3.2. For each position in the range:
3.2.1. Place the clue and remove the UA sets hit.
3.2.2. If all UA are hit, permute the rest clues (if any) in all possible ways and check the puzzles for uniqueness.
3.2.3. If it is last clue, backtrack.
3.2.4. Store the context for backtracking.
3.2.5. Call recursively for the first of the rest clues.

3.3. If it is the first clue, then done, else backtrack.


Some tricks

When determining the Maximal Clique, only UA of size up to 11 are processed. The rest cells in each Maximal Clique are checked for UA and if found, it is added to the UA and the process is repeated.

When determining the rating of UA in the clique, UA of size up to 8 are used. This simplification sometimes results in better (faster for enumeration) arrangement.

UA sets are represented as 128-bit bitmaps with 81 bits used. They are processed with SIMD instructions.

After the list of the unhit UA sets diminished to 768 sets, a swithing to bitmap mode is done. For each clue position a list of 6 128-bit values is marking the UA sets which are hit by this clue (81 hitting masks). Another 768-bit list is updated during the positioning of each clue (set mask). First zero bit in this list corresponds to the first unhit UA.

The solver knows the original grid, and when guessing, it does it in the "right" way, tracing extremely fast the path to the first solution, then finding the closer second solution if any.

MD

All UA sets located in a band is easy to collect by collecting the solution differences of a puzzle formed by a valid completion of this band, and with all cells in the band cleared. The difference between each 2 solutions is a (not necessarily minimal) UA set. Non-minimal contain smaller UA subsets, which are differences between other two solutions. After removal of non-minimals, only minimal UA remain.
The number of solutions and UA sets for each band are listed in columns 2 and 3 in the table in Bands and low-clue puzzles.

For band completion enumeration I am using an extension coded into GridChecker. I am fixing the 54 clues for the rest of the grid as "givens", and producing the UA only for that band, knowing that all others are hit by the rest 54 clues.
If you can compile the source of GridChecker, I will publish (or send you) the latest version with these extensions. It is easy to trace the logic.

Example in next post. Still don't know how detailed it will be.

Cheers,
MD
dobrichev
2016 Supporter
 
Posts: 1316
Joined: 24 May 2010

Example

Postby dobrichev » Thu Apr 07, 2011 2:32 am

Consider band 261. It participates in 6 of the puzzles for Fractal Pattern.

Code: Select all
123 456 789
457 189 623
689 732 514 #band 261

Compose a puzzle having at top band 261.

Code: Select all
123 456 789
457 189 623
689 732 514

... ... ...
... ... ...
... ... ...

... ... ...
... ... ...
... ... ... #puzzle with band 261 at top

Compose a valid solution grid having at top band 261 by solving the above puzzle.

Code: Select all
123 456 789
457 189 623
689 732 514

214 365 897
365 897 142
798 214 356

532 641 978
841 973 265
976 528 431 #valid grid with band 261 at top

Compose a puzzle from the above grid by removal of all givens in top band

Code: Select all
... ... ...
... ... ...
... ... ...

214 365 897
365 897 142
798 214 356

532 641 978
841 973 265
976 528 431 #puzzle grid with band 261 emptied

The above puzzle has 156 solutions, and one of them has band 261 at top

Here is the puzzle with some of the solutions

Code: Select all
...........................214365897365897142798214356532641978841973265976528431 #puzzle
123456789457189623689732514214365897365897142798214356532641978841973265976528431 #band 261
123456789459782613687139524214365897365897142798214356532641978841973265976528431 #band a
123456789687139524459782613214365897365897142798214356532641978841973265976528431 #band b
123456789689732514457189623214365897365897142798214356532641978841973265976528431 #band c
 ...

Now compare first 27 cells of the rest 155 solutions to band 261 (first listed solution).

Code: Select all
123456789457189623689732514...................................................... #band 261
123456789459782613687139524...................................................... #band a
...........xx.x.x...xx.x.x....................................................... #unav a
123456789687139524459782613...................................................... #band b
.........xx..x.x.xxx..x.x.x...................................................... #unav b
123456789689732514457189623...................................................... #band c
.........xxxxxxxxxxxxxxxxxx...................................................... #unav c
 ...


As we see, unav c has unav b as a subset, therefore it is non-minimal and must be ignored.
Note: Minimality of the UA used is not required, but non-minimal UA don't contribute.

After filtering out the non-minimal UA, from initial 155 UA only the following 19 remain.
Permutable cells are marked with digits, the rest are from band 261.

Code: Select all
1..4.....4..1....................................................................   4
.2..5..8..5..8..2................................................................   6
12...6.8..........68...2.1.......................................................   8
..3..67.9..7..96.3...............................................................   8
...........71.9.2...97.2.1.......................................................   8  #unav a
..345.7.9...........973.5.4......................................................   10
...4.67.9..7..96....97....4......................................................   10
.........45..8.6.368..3.5.4......................................................   10 #unav b
..3.5.7..4.7...6.36...3.5.4......................................................   11
.23....89....89.23.89.32.........................................................   12
.23.567...57.896...89.32.........................................................   14
...4.67.9.5..896.3.8.73.5.4......................................................   14
.23.567..457.8.6.368..32..4......................................................   16
1..456789....89.236..732514......................................................   18
.23....894571..6236897..514......................................................   18
12.4.6.89.571.962.6897..514......................................................   19
1.34567.9..71.9.236..732514......................................................   19
1.345.789457.8.6.36897..514......................................................   20
1..45.78.4.7.896236.9732514......................................................   20

A "band completion of band 261" is every clue combination that simultaneously hits all these 19 UA.

There are no 2-clue combinations that covered all UA because these 3 UA are mutually disjoint and require at least 3 clues, one for each UA.

Code: Select all
1..4.....4..1....................................................................   4
.2..5..8..5..8..2................................................................   6
..3..67.9..7..96.3...............................................................   8

Without going to details, there are no 3-clue combinations too, but there are 388 4-clue combinations.
Below are first 3 and last 3 of them, when ordered alphabetically.

Code: Select all
....5.......1..6.......2...
....5.......1..6...8.......
....5.......1.9....8.......
 ...
12.........7..............4
12.........7............5..
12.........7..........3....

Each of these 4-clue combination is cappable to compose a valid puzzle without any additional givens in this band, and they are "band completions".

Each of these 4-clue completions produces 23 non-minimal 5-clue completions by adding an extra clue at each of 23 free positions.
Additionally, there could be 5-clue completions not formed as supersets of any of the 4-clue completion.

Four of the 5-clue completions are related to Fractal Pattern. Here is one of them.

Code: Select all
.....6......18.......73....

in 2-d form

Code: Select all
... ..6 ...
... 18. ...
... 73. ...

swap rows 1,2

Code: Select all
... 18. ...
... ..6 ...
... 73. ...

swap columns 5,6

Code: Select all
... 1.8 ...
... .6. ...
... 7.3 ...

and place it in band 2 to compose Fractal.

This pattern by itself is not valuable, but we additionally know all "non-givens" within the band, which will form the "target grid".

Hope this makes the things more clear.

Some parts of the example are made manually and could have typos.

Don't hesitate to ask for other details if necessary.

Cheers,
MD
dobrichev
2016 Supporter
 
Posts: 1316
Joined: 24 May 2010

Re: Valid puzzles for Fractal Pattern

Postby Serg » Thu Apr 07, 2011 11:41 am

Hi, dobrichev!
Thank you for detailed description of your method. It is now clear to me. I think your method is based on the same idea as blue's method (as far as I understand it) - decompose the whole pattern by simpler parts, filter out variants with unvaidable sets formed by non-clue cells for each part and finally construct the pattern from previosly analyzed parts. Saying in other words, the main idea is to avoid unavoidable sets as possible during variants analyzing.

I am impressed by your way of finding possible band completitions. It is so difficult! (But maybe not so difficult personally for you because it is based on GridChecker and other tools/results that were previously developed/investigated by yourself.)

Thanks for interesting ideas!

Serg
Serg
2017 Supporter
 
Posts: 513
Joined: 01 June 2010
Location: Russia

Re: Valid puzzles for Fractal Pattern

Postby JeJ » Mon Apr 11, 2011 2:49 am

I don't have anything to contribute to this topic, but I just wanted to thank the people who have posted those fractal patterns, they look very nice in a Sudoku program.
JeJ
 
Posts: 76
Joined: 06 January 2011

Re: Valid puzzles for Fractal Pattern

Postby Serg » Thu Apr 21, 2011 3:43 pm

Hi, people!
I've found some intersting properties of Fractal Pattern's valid puzzles. 4 puzzles (totally there exist 7 puzzles) have UA sets of order 4 formed entirely by puzzles' filled cells. These puzzles are posted below (puzzles are posted left, UA sets are posted right).
Code: Select all
2 . 3 . . . 4 . 6       2 . 3 . . . . . .     # puzzle 1
. 1 . . . . . 2 .       . . . . . . . . .
5 . 7 . . . 8 . 3       . . . . . . . . .
. . . 2 . 3 . . .       . . . . . . . . .
. . . . 1 . . . .       . . . . . . . . .
. . . 4 . 5 . . .       . . . . . . . . .
3 . 2 . . . 6 . 8       3 . 2 . . . . . .
. 6 . . . . . 4 .       . . . . . . . . .
8 . 1 . . . 5 . 9       . . . . . . . . .


2 . 3 . . . 4 . 6       2 . 3 . . . . . .     # puzzle 2
. 1 . . . . . 2 .       . . . . . . . . .
5 . 7 . . . 8 . 3       . . . . . . . . .
. . . 2 . 3 . . .       . . . . . . . . .
. . . . 1 . . . .       . . . . . . . . .
. . . 4 . 5 . . .       . . . . . . . . .
3 . 2 . . . 6 . 8       3 . 2 . . . . . .
. 6 . . . . . 4 .       . . . . . . . . .
8 . 1 . . . 9 . 5       . . . . . . . . .


2 . 3 . . . 4 . 6       2 . 3 . . . . . .     # puzzle 3
. 1 . . . . . 2 .       . . . . . . . . .
7 . 5 . . . 8 . 3       . . . . . . . . .
. . . 2 . 3 . . .       . . . . . . . . .
. . . . 1 . . . .       . . . . . . . . .
. . . 4 . 5 . . .       . . . . . . . . .
1 . 8 . . . 5 . 9       . . . . . . . . .
. 6 . . . . . 4 .       . . . . . . . . .
3 . 2 . . . 6 . 8       3 . 2 . . . . . .


2 . 3 . . . 4 . 6       2 . 3 . . . . . .     # puzzle 4
. 1 . . . . . 2 .       . . . . . . . . .
7 . 5 . . . 8 . 3       . . . . . . . . .
. . . 2 . 3 . . .       . . . . . . . . .
. . . . 1 . . . .       . . . . . . . . .
. . . 4 . 5 . . .       . . . . . . . . .
1 . 8 . . . 9 . 5       . . . . . . . . .
. 6 . . . . . 4 .       . . . . . . . . .
3 . 2 . . . 6 . 8       3 . 2 . . . . . .

This property implies we can produce another valid puzzle from original puzzle by permuting UA set digits. So, we can produce valid puzzle ("puzzle 1a") from "puzzle 1", being non-isomorphic to original "puzzle 1".
Code: Select all
3 . 2 . . . 4 . 6       3 . 2 . . . . . .     # puzzle 1a
. 1 . . . . . 2 .       . . . . . . . . .
5 . 7 . . . 8 . 3       . . . . . . . . .
. . . 2 . 3 . . .       . . . . . . . . .
. . . . 1 . . . .       . . . . . . . . .
. . . 4 . 5 . . .       . . . . . . . . .
2 . 3 . . . 6 . 8       2 . 3 . . . . . .
. 6 . . . . . 4 .       . . . . . . . . .
8 . 1 . . . 5 . 9       . . . . . . . . .

It turns out that "puzzle 1a" is isomorphic to "puzzle 3", and vice versa, "puzzle 3a" is isomorphic to "puzzle 1". So, by UA set permutation we can produce "puzzle 3" from "puzzle 1" and vice versa. In the same way we can produce "puzzle 4" from "puzzle 2" and vice versa.

It is interesting - have known 17-clues puzzles (39-clues minimal puzzles, etc.) UA sets among their clues? If any, can we use this property to produce other valid puzzles of appropriate type?

Serg
Serg
2017 Supporter
 
Posts: 513
Joined: 01 June 2010
Location: Russia

Re: Valid puzzles for Fractal Pattern

Postby ronk » Thu Apr 21, 2011 4:36 pm

Serg wrote:It is interesting - have known 17-clues puzzles (39-clues minimal puzzles, etc.) UA sets among their clues? If any, can we use this property to produce other valid puzzles of appropriate type?

I presume you mean "UA sets" which are fully populated with clues. That's definitely an interesting property for the fractal, but I'd be surprised if the property even exists in a 17-puzzle.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: Valid puzzles for Fractal Pattern

Postby dobrichev » Thu Apr 21, 2011 5:21 pm

Good observation, ronk.

Known 17's were searched for "twins". Here I counted 96 twins in the Gordon's collection. Now I can't remember what exactly I counted, since there were cases where puzzles A and B are twins, B and C are twins, but A and C are not. So 96 is probably not the pair count but the number of puzzles which have 1 or more twins.
dobrichev
2016 Supporter
 
Posts: 1316
Joined: 24 May 2010

Re: Valid puzzles for Fractal Pattern

Postby Serg » Fri Apr 22, 2011 8:16 am

Hi, ronk, dobrichev!
Thank you for your replies. dobrichev, thank you for your link. Your results are very interesting for me. I've searched twin puzzles in exactly the same way as you.

dobrichev wrote:Now I can't remember what exactly I counted, since there were cases where puzzles A and B are twins, B and C are twins, but A and C are not. So 96 is probably not the pair count but the number of puzzles which have 1 or more twins.

Sounds somewhat strange... Puzzles A, B, C in your example all have the same completition, aren't they? If so, they all are twins (maybe "multiplies"?).

Serg

[Edited: link to wrongly published new horizontally symmetric 18-clue puzzles was deleted]
Last edited by Serg on Fri Apr 22, 2011 11:24 am, edited 1 time in total.
Serg
2017 Supporter
 
Posts: 513
Joined: 01 June 2010
Location: Russia

Next

Return to General