The New Sudoku Players' Forum

[Afmob]

Not yet. I'm just wondering that you only needed 5 CPU hours to analyze all puzzles.

Right now, I've gone through N1,N7 and N19 and together they have 994,068,192 ED puzzles. I'll post more when the whole computation is finished.

Edit: I've checked all 22 patterns and none of them had a uniquely solvable puzzle but with the huge number of essentially different (ED) puzzles, Serg hasn't possibly checked every ED puzzle but used some different method to reduce the search space.

Pattern || Automorphisms || ED Puzzles:

Code: Select all

N01 || 192 ||   290,907,708
N02 ||  96 ||   698,144,880
N03 ||  48 || 1,394,121,216
N04 ||  24 || 3,345,890,496
N05 ||  48 || 1,672,430,076
N06 ||  24 || 4,013,753,328
N07 ||  96 ||   580,654,080
N08 ||  24 || 2,786,918,400
N09 ||  48 || 1,393,493,760
N10 ||  12 || 6,688,604,160
N11 ||  24 || 3,344,412,672
N12 ||  12 || 8,026,407,936
N13 ||  96 ||   653,194,800
N14 ||  48 || 1,567,684,800
N15 ||  24 || 3,135,283,200
N16 ||  12 || 7,524,679,680
N17 ||  24 || 3,762,365,760
N18 ||  12 || 9,029,719,296
N19 || 576 ||   122,506,404
N20 ||  96 ||   881,850,816
N21 ||  48 || 2,116,398,960
N22 ||  72 || 1,693,178,802


[Afmob]

Serg, could you please explain your algorithm? The number of essentially puzzle is far too large (> 64,7 billion) for checking all ED puzzles of each pattern in just 5 CPU hours.

[Serg]

Hi, Afmob!

Serg, could you please explain your algorithm? The number of essentially puzzle is far too large (> 64,7 billion) for checking all ED puzzles of each pattern in just 5 CPU hours.

The general idea of my method is borrowed from blue's exhaustive search for Fractal Pattern done in May, 2010 (many thanks to blue!). He published his method's description at setbb.com/sudoku forum (see thread Search for maximal pattern, containing both diagonals). blue treated his method as very special, being suited for specific patterns only. But I treat now his method of exhaustive seach as universal and very efficient. I successfully used it several times for exhaustive search exploring different patterns. It works well! Certainly I added some techniques to this method to make it more universal and efficient.

Assume we are doing exhaustive search for valid puzzles exploring given pattern. A possible approach to this search is to check out all essentially different solution grids and select those grids that produce puzzles having unique solution for given pattern. It is not necessary to loop over all 5e9 e-d solution grids and check all isomorphs of given patterns for each solution grid. We can decompose overall search, looping over possible configuirations of alone bands, for example, and considering all combinations of these bands. At the first glance this approach requires the same volume of work as looping over all e-d solution grids, but, but, but... The main idea of the method discussed is decomposition of the grid to several parts, decomposition of the pattern to the same parts, store parts fillings variants (subset of solutions grids) having no unhit UA sets (all UA sets must be hit by this parts clues). At this stage many parts configurations having unhit UA sets are filtered out. So, when we'll combine that parts we'll forced to consider substaintially less variants comparing with looping over all possible solution grids.

For example, let's consider exhaustive search for valid puzzles for map

Code: Select all

1 1 1
1 1 1
9 9 9


First, we should search all valid configurations of the top band B123. It can have 2 possible e-d patterns only (configurations with 2 empty rows were rejected):

Code: Select all

        A1                         A2
+-----+-----+-----+        +-----+-----+-----+
|x . .|x . .|. . .|        |x . .|. . .|. . .|
|. . .|. . .|x . .|        |. . .|x . .|. . .|
|. . .|. . .|. . .|        |. . .|. . .|x . .|
+-----+-----+-----+        +-----+-----+-----+


I checked 653184 configurations for A1 pattern and found 163312 non-isomorphic configurations (I accounted for not all possible automorhisms). 310 configurations only have no unhit UA sets. So, I stored these 310 variants of band's filling for further usage.

I checked 653184 configurations for A2 pattern and found 55228 non-isomorphic configurations (I accounted for not all possible automorhisms). 168 configurations only have no unhit UA sets. So, I stored these 168 variants of band's filling for further usage.

Next, I found all valid configurations of the left (sub)stack B1+B4. It can have 2 possible e-d patterns:

Code: Select all

        C1                   C2
+-----+-----+        +-----+-----+
|x . .|x . .|        |x . .|. . .|
|. . .|. . .|        |. . .|x . .|
|. . .|. . .|        |. . .|. . .|
+-----+-----+        +-----+-----+


I checked 6048 configurations for C1 pattern and found 1516 non-isomorphic configurations. 888 configurations only have no unhit UA sets.

I checked 6048 configurations for C2 pattern and found 1582 non-isomorphic configurations. 946 configurations only have no unhit UA sets.

Next, I checked out all valid configurations of the combination: top band B123 plus left (sub)stack B1+B4. It can have 6 possible e-d patterns:

Code: Select all

        D1                         D2                         D3                         D4
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|x . .|x . .|. . .|        |x . .|x . .|. . .|        |x . .|. . .|. . .|        |x . .|. . .|. . .|
|. . .|. . .|x . .|        |. . .|. . .|x . .|        |. . .|x . .|x . .|        |. . .|x . .|x . .|
|. . .|. . .|. . .|        |. . .|. . .|. . .|        |. . .|. . .|. . .|        |. . .|. . .|. . .|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|x . .|                    |. x .|                    |x . .|                    |. x .|
|. . .|                    |. . .|                    |. . .|                    |. . .|
|. . .|                    |. . .|                    |. . .|                    |. . .|
+-----+                    +-----+                    +-----+                    +-----+

        D5                         D6
+-----+-----+-----+        +-----+-----+-----+
|x . .|. . .|. . .|        |x . .|. . .|. . .|
|. . .|x . .|. . .|        |. . .|x . .|. . .|
|. . .|. . .|x . .|        |. . .|. . .|x . .|
+-----+-----+-----+        +-----+-----+-----+
|x . .|                    |. x .|
|. . .|                    |. . .|
|. . .|                    |. . .|
+-----+                    +-----+


At this stage I got 153364 variants for D1 pattern, 350788 variants for D2 pattern, 49848 variants for D3 pattern, 113896 variants for D4 pattern, 112610 variants for D5 pattern, 241210 variants for D6 pattern. Because I used valid variants only of band B123 and substack B1+B4, I avoided checking out huge amount of invalid combinations of band and substack. This is central idea of the method. We can also search for all valid variants of band and substack "from scratch", filling boxes B1-B4 by all possible digits combinations. But we would forced to check out much more variants in that case in comparison with combining "pre-cleaned" (from unhit UA sets) band and substack. So, using "pre-cleaned" band and substack allows us to check out only configurations having unhit UA sets spanning all 4 boxes or boxes B1, B2 and B4, but we don't expect see UA sets spanning 2 boxes only or boxes B1-B3.

At this stage I use a trick speeding up unhit UA check several times. I call this trick as "UA caching".
Suppose we found unhit UA set for some combination of band B123 and substack B1+B4. If we will check a combination of the same band and another substack we can test only cells of the box B4 beloning to previously found UA set to determine - do that cells contain UA set digits?
For example, assume we found this unhit UA set (U8):

Code: Select all

+-----+-----+-----+
|1 . .|. 7 .|5 . .|
|. 5 .|. 1 .|7 . .|
|. . .|. . .|. . .|
+-----+-----+-----+
|. . .|
|5 1 .|
|. . .|
+-----+


This implies that during checking out combinataion of the same band and another substack we can simply check cells r5c1 and r5c2 - do r5c1 contains "5" and r5c2 contains "1"? If so - the combination definitely has unhit UA set. So, we should keep "UA cache", containing some patterns of the box B4 cells, during checking out combinations of band and substack having the given band. This trick speeds up the search 2-5 times (or more, I don't remember precise ratio).

Next, we should combine 4-boxes comfiguration (B1+B2+B3+B4) and band B456. It turns out that there are no valid 6-boxes configurations having 1 clue in each box.

Some words about durability of the search stages described above.
1. Finding all valid bands took me 3 minutes of CPU time.
2. Finding all valid 2-boxes subbands took me 1 second of CPU time.
3. Finding all valid B1+B2+B3+B4 configurations took me 6 minutes of CPU time.
4. Finding all valid B1+B2+B3+B4+B5+B6 configurations took me 16804 seconds (4.7 hours) of CPU time.

Serg

[Edited: I deleted wrong statement "If I would use intermediate stage "Finding all valid B1+B2+B3+B4+B5 configurations", I would take about 15 minutes per all stages because there are 20 valid B1+B2+B3+B4+B5 one-clue-box configurations only". Really it is optimal to combine full band (B258) with B1+B2+B3+B4 configuration, as it was described in this post.]

[Afmob]

Serg, thanks for your thorough answer and confirming that you din't actually check all ed puzzles. You said that you didn't use all possible automorphisms to get the configurations/completions for the first band. Did you take into account that for N1 you have 8 possible automorphisms for the first band but for N4 only 2 automorphisms (since columns 5 and 6 (8 and 9) are not identical)?

[eleven]

Hi Serg,

i did not have time to read all carefully, but maybe you can answer a quick question, which will help me to understand.

Code: Select all

        A1                         A2
+-----+-----+-----+        +-----+-----+-----+
|x . .|x . .|. . .|        |x . .|. . .|. . .|
|. . .|. . .|x . .|        |. . .|x . .|. . .|
|. . .|. . .|. . .|        |. . .|. . .|x . .|
+-----+-----+-----+        +-----+-----+-----+


I checked 653184 configurations for A1 pattern and found 163312 non-isomorphic configurations (I accounted for not all possible automorhisms). 310 configurations only have no unhit UA sets. So, I stored these 310 variants of band's filling for further usage.

A1 is the pattern i had in the other thread too. As you can see, i kept 4 times more variants. The reason is, that i did not use 2 column automorphisms, because the rest of the pattern does not have them (there: switching columns 12 and 89). Now i think, if you do use them, you would have more pattern combinations to consider, e.g. this one additional to D4.

Code: Select all

+-----+-----+-----+
|x . .|. . .|. . .|
|. . .|x . .|x . .|
|. . .|. . .|. . .|
+-----+-----+-----+
|. . x|             
|. . .|             
|. . .|             
+-----+ 

This concerns all 4 automorphisms for this task. You did not mention, how you handled this problem.

[eleven]

<rubbish>

[Serg]

Hi, Afmob!

Serg, thanks for your thorough answer and confirming that you din't actually check all ed puzzles. You said that you didn't use all possible automorphisms to get the configurations/completions for the first band. Did you take into account that for N1 you have 8 possible automorphisms for the first band but for N4 only 2 automorphisms (since columns 5 and 6 (8 and 9) are not identical)?

Yes, I didn't check all e-d puzzles. (I misunderstood your question about it, sorry.) But I am sure I did exhaustive search.

That automorphisms analysis is weak point of my search method. I spent most of time to this analysis during search program coding and cross-checking results. During each grid/puzzle subsets combining some automorphisms can disappear, but others can appear. I must carefully account for these changes, and this point complicates code. This is why I avoided accounting for automorphisms (partitially) at earlier stages. Each time we account for automorphisms we "compress" stored variants. But it is quite possible that we will be forced to "decompress" these variants producing additional (formerly isomorphic) variants for analisys at the next stages.

To solve this "automorphisms mutating" problem I had to analyse (for automorphisms) final pattern first, then going back to beginning (simpler parts combining).

Yes, I took into account that for pattern N4 band B258 "destroys" swappings of columns c5/c6 and c8/c9. So, in this case I had to consider 3 additional variants of the band B123 swapping c5/c6 and c8/c9 columns ("decompression").

Serg

[Serg]

Hi, eleven!

Hi Serg,

i did not have time to read all carefully, but maybe you can answer a quick question, which will help me to understand.

Code: Select all

        A1                         A2
+-----+-----+-----+        +-----+-----+-----+
|x . .|x . .|. . .|        |x . .|. . .|. . .|
|. . .|. . .|x . .|        |. . .|x . .|. . .|
|. . .|. . .|. . .|        |. . .|. . .|x . .|
+-----+-----+-----+        +-----+-----+-----+


I checked 653184 configurations for A1 pattern and found 163312 non-isomorphic configurations (I accounted for not all possible automorhisms). 310 configurations only have no unhit UA sets. So, I stored these 310 variants of band's filling for further usage.

A1 is the pattern i had in the other thread too. As you can see, i kept 4 times more variants. The reason is, that i did not use 2 column automorphisms, because the rest of the pattern does not have them (there: switching columns 12 and 89). Now i think, if you do use them, you would have more pattern combinations to consider, e.g. this one additional to D4.

Code: Select all

+-----+-----+-----+
|x . .|. . .|. . .|
|. . .|x . .|x . .|
|. . .|. . .|. . .|
+-----+-----+-----+
|. . x|             
|. . .|             
|. . .|             
+-----+ 

This concerns all 4 automorphisms for this task. You did not mention, how you handled this problem.

You are right, some automorphisms are "distroyed" at the later search stages, so we should not account for such automorphisms at all (as you did it) or produce additional variants at the later stages to account for automorphisms "disappearing". (I think I wrote answer to your question in my previous post addressed to Afmob.)

I have a dream to automatise automorphisms analysis for my method. Then it will be possible to code universal search tool not requiring any manual pattern ajustment.

Serg

[Serg]

<withdrawn>

[Serg]

Hi, colleagues!
I forgot to say about the most complicated (to my mind) case of automorphisms "interactions" while combining 2 pieces of grid.

Let's consider pattern N1:

Code: Select all

        N1
+-----+-----+-----+
|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|
+-----+-----+-----+


When we are combining 4-boxes solution grid's fragment having pattern (boxes B1, B2, B3, B4)

Code: Select all

        D1
+-----+-----+-----+
|x . .|x . .|. . .|
|. . .|. . .|x . .|
|. . .|. . .|. . .|
+-----+-----+-----+
|x . .|
|. . .|
|. . .|
+-----+


with 3-boxes solution grid's fragment having pattern (boxes B4, B5, B6)

Code: Select all

        A1
+-----+-----+-----+
|x . .|x . .|. . .|
|. . .|. . .|x . .|
|. . .|. . .|. . .|
+-----+-----+-----+


we can see that both patterns have automorhism "swapping columns c8/c9". Hence it is sufficient to store one of two isomorphic images of these fragments. Say, we can claim that r1c8 < r1c9 for all considered variants of both fragments fillings. The automorphism considered isn't "destroyed" by appearing the clue in columns c8/c9 during combining fragments. But we can see that combined fragment

Code: Select all

       E1
+-----+-----+-----+
|x . .|x . .|. . .|
|. . .|. . .|x . .|
|. . .|. . .|. . .|
+-----+-----+-----+
|x . .|x . .|. . .|
|. . .|. . .|x . .|
|. . .|. . .|. . .|
+-----+-----+-----+


has 2 isomorphic fillings' variants (I consider now automorhism "swapping columns c8/c9" only) - variant "r1c8 < r1c9" and variant "r1c8 > r1c9". To account for all minicolumns mc8/mc9 (B3, B6 boxes) combinations, we must treat one of these automorphisms as "destroyed". Say, we can consider the band B456 as not having automorhism "swapping columns c8/c9" before combining it with 4-boxes (B1-B4) fragment. In this case only we will be able to get 2 possible configurations of E1 fragments (variant "r1c8 < r1c9 and r4c8 < r4c9" and variant "r1c8 < r1c9 and r4c8 > r4c9"). One could say about 2 automorphisms merging or about destroying one of the automorphism by another.

I post the simplest variant of automorhisms "interaction", but I was forced to account more complicated variants of automorhisms "interaction".

Serg

[eleven]

Hi, eleven!
Maybe I misunderstood you...

No, you didn't, it was just rubbish - i was already crazy from switching between patterns and bands and complements and solutions ...

[eleven]

Serg,

your last example is not one, where i see a problem. Here you have the same pattern/automorphisms in bands 1 and 2.

But again, how did you handle this pattern?

Code: Select all

    +-----+-----+-----+
    |x . .|. . .|. . .|
    |. . .|x . .|x . .|
    |. . .|. . .|. . .|
    +-----+-----+-----+
    |. . x|             
    |. . .|             
    |. . .|             
    +-----+ 

If you dont use the automorphisms for band 1, you would have 8 times more completions. Switching columns 2 and 3 here plus renumbering can bring you to 2 different of the 8 completions - but only one is in your list.

[Serg]

Hi, eleven!

Serg,

your last example is not one, where i see a problem. Here you have the same pattern/automorphisms in bands 1 and 2.

But again, how did you handle this pattern?

Code: Select all

    +-----+-----+-----+
    |x . .|. . .|. . .|
    |. . .|x . .|x . .|
    |. . .|. . .|. . .|
    +-----+-----+-----+
    |. . x|             
    |. . .|             
    |. . .|             
    +-----+ 

If you dont use the automorphisms for band 1, you would have 8 times more completions. Switching columns 2 and 3 here plus renumbering can bring you to 2 different of the 8 completions - but only one is in your list.

Concerning the band pattern

Code: Select all

        A1
+-----+-----+-----+
|x . .|x . .|. . .|
|. . .|. . .|x . .|
|. . .|. . .|. . .|
+-----+-----+-----+


If we permit columns c5/c6 swapping and c8/c9 swapping only, and relabel B1 box to ordered form

Code: Select all

1 2 3
4 5 6
7 8 9


we'll get 653184 variants of the band filling.

Let's consider now isomorphic transformations:
1. Swapping boxes B1/B2 (and B1 box relabelling).
2. Swapping columns c2/c3 (and B1 box relabelling).

If we check out those 653184 variants of the band filling for non-isomorhic form, we'll get 163312 non-isomorphic variants (slightly more than 653184/4=163296 because of bands' automorphisms). 163002 variants have unhit UA sets, so we need to store 310 variants of the band's filling for further use.

So, you can see at this point that I used all possible automorphisms for band A1 (including "swapping columns c2/c3").

Now let's consider all possible combinations of the band A1 and two-boxes subband

Code: Select all

        C1                   C2
+-----+-----+        +-----+-----+
|x . .|x . .|        |x . .|. . .|
|. . .|. . .|        |. . .|x . .|
|. . .|. . .|        |. . .|. . .|
+-----+-----+        +-----+-----+


We should consider those combinations only:

Code: Select all

        D1                         D2                         D3                         D4
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|x . .|x . .|. . .|        |x . .|x . .|. . .|        |x . .|. . .|. . .|        |x . .|. . .|. . .|
|. . .|. . .|x . .|        |. . .|. . .|x . .|        |. . .|x . .|x . .|        |. . .|x . .|x . .|
|. . .|. . .|. . .|        |. . .|. . .|. . .|        |. . .|. . .|. . .|        |. . .|. . .|. . .|
+-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+        +-----+-----+-----+
|x . .|                    |. x .|                    |x . .|                    |. x .|
|. . .|                    |. . .|                    |. . .|                    |. . .|
|. . .|                    |. . .|                    |. . .|                    |. . .|
+-----+                    +-----+                    +-----+                    +-----+


Because pattern

Code: Select all

+-----+-----+-----+
|x . .|. . .|. . .|
|. . .|x . .|x . .|
|. . .|. . .|. . .|
+-----+-----+-----+
|. . x|
|. . .|
|. . .|
+-----+


for example, can be morphed to D4 pattern.

If we consider pattern

Code: Select all

        D4
+-----+-----+-----+
|x . .|. . .|. . .|
|. . .|x . .|x . .|
|. . .|. . .|. . .|
+-----+-----+-----+
|. x .|
|. . .|
|. . .|
+-----+


we can see that clue r4c2 breaks the pattern's automorphism "Swapping columns c2/c3", so we must consider 620 band B123 variants (additional variants are produced by minicolumns c2/c3 swapping). But at this stage automorphism "Swapping boxes B1/B2" isn't destroyed (we should consider "Swapping boxes B2/B3" automorphism for pattern D4), so we must increase bands' variants only twice.

To get filling variants for band pattern

Code: Select all

        A3
+-----+-----+-----+
|x . .|. . .|. . .|
|. . .|x . .|x . .|
|. . .|. . .|. . .|
+-----+-----+-----+


we should swap boxes B1/B3, swap rows r1/r2 and relabel B1 box each of 310 variants of the A1 band's fillings.

I feel I still miss something in your question...

Serg

[Edited: I corrected description of A3 band's fillings production in the tail of the post.]

[eleven]

...we can see that clue r4c2 breaks the pattern's automorphism "Swapping columns c2/c3", so we must consider 620 band B123 variants (additional variants are produced by minicolumns c2/c3 swapping)...

Serg,

sorry, i did not want to be nit-picking, its just that you did not mention, how much additional band 1 variants you checked for each of the six 4-box patterns D1-D6.
You only wrote about 310/168 variants for A1/A2, but for D1-D6 you have to consider 620/1240/310/620 and 672/1344 variants for the first band.

[coloin]

Hi Serg, finally ther penny dropped as to how you are doing this.
I have looked at a few patterns with just

Code: Select all

111
191
999

and of course any puzzles generated will have one of your 310 bands in band 1......

at present you are/have analysed the 22 different ways to have

Code: Select all

111
111
999

probably all the possible

Code: Select all

111
191
999

have puzzles ?

Maybe it would be possible to generate all the possible

Code: Select all

111
1-1

B12346 combinations which are solveable with 5 [one in each box] clues - are there really that many ?

maybe there are

Code: Select all

+---+---+---+
|4..|...|...|
|...|..3|.6.|
|...|...|...|
+---+---+---+
|...|329|...|
|.7.|145|..2|
|...|687|...|
+---+---+---+
|123|456|987|
|847|912|635|
|956|738|124|
+---+---+---+

If there are not to much which case we could easily resolve the next level

Code: Select all

111
121
999

case for example

edit

Code: Select all

102
190
999

do exist

Code: Select all

+---+---+---+
|7..|...|...|
|...|...|.23|
|...|...|...|
+---+---+---+
|...|714|...|
|.3.|628|...|
|...|539|...|
+---+---+---+
|123|456|789|
|547|982|631|
|986|173|542|
+---+---+---+

C