The New Sudoku Players' Forum

[eleven]

Is there a chance that the distance between patterns can help us find puzzles?

Maybe, i did not try it that way.
I had looked at the distances last year with gsf's program (yes, it also can show the transformations, but i dont know the commands), and i think, all puzzles had a hamming distance less equal 12 to another one - but of course not in normal form.

It will be hard in any case to find a new pattern. Since i already had done the simple neighbourhood searches, it might be better to do, what i believe mauricio and olimpia did: Take a new pattern and try to find a valid puzzle in it.

[Serg]

Hi!
Now I implemented olimpia's idea.

Talking about re-arranging shapes, I've wondered if any of the 17 clue puzzles can be re-arranged to be nearly symmetric (on a vertical axis), so that it is only one clue away from complete symmetry. Then an 18th clue can be added, making an 18 clue non-minimal symmetric sudoku. I suspect this doesn't exist, but if anyone has the programming skills to check, it might be interesting to find out. Also, I'm not sure if checking for "near-symmetry" would significantly increase the task compared to a simpler "symmetry" check.

I've checked out 49151 puzzles from Gordon Royle's 17-clue puzzles list. It turns out that there are no "almost symmetric" (horizontal or vertical) 17-clue puzzles. I.e. there are no 17-clue puzzles which can be transformed to 18-clue symmetric puzzles by adding 1 clue only.

To cross-check this result I tested for minimality all 18-clue symmetric puzzles, published by eleven (385 puzzles). If there would be non-minimal 18-clue symmetric puzzles, we would then get new 17-clue puzzles or otherwise we have to admin an error in "almost symmetric" 17-clue puzzles search. But it turns out all 385 18-clue symmetric puzzles are minimal.

Serg

[eleven]

Hi Serg,

in the other thread

3. Exhaustive search for symmetric 18-clue valid puzzles.

I also wondered, if its feasible to make an exhaustive search over all 18 clue patterns with "reflective" symmetry. The answer is yes, but not for me.

To get an idea, what effort that would need, I calculated a list of possible patterns in "symmetric pattern minlex" form, i.e. the patterns have the reflectice symmetry and the pattern string is minimal. I did not include patterns, which have 2 empty rows in a band or 2 empty columns in a stack (about 40%). The list has almost 300000 patterns, you can download it here. Note, that i did not bother to eliminate 429 equivalents (those, where the mirrored puzzle can be transposed to the same symmetry with lower minlex - i did that with "half" puzzles and only used band and row swapping and column swapping for the first stack).

Now some thousands of the patterns can be eliminated too, because they have invalid bands (e.g. with 2 empty boxes and less than 4 clues in the third) or 4 invalid empty boxes. But i doubt, that the list can be reduced to less than 200000 with invalid subpatterns.

So i would have to do an exhaustive search for 200K symmetric 18 clues. From a single test i know, that it took more than an hour - and the puzzle had an additional symmetry. Thus with this program i guess, that on average i would need 5 hours on a single core on my PC.

To do it in say 6 months i would need a program, which is about 40 times faster and 6 cores. Possible, but no way for me.

[Serg]

Hi, eleven!

I also wondered, if its feasible to make an exhaustive search over all 18 clue patterns with "reflective" symmetry. The answer is yes, but not for me.

To get an idea, what effort that would need, I calculated a list of possible patterns in "symmetric pattern minlex" form, i.e. the patterns have the reflectice symmetry and the pattern string is minimal. I did not include patterns, which have 2 empty rows in a band or 2 empty columns in a stack (about 40%). The list has almost 300000 patterns, you can download it here. Note, that i did not bother to eliminate 429 equivalents (those, where the mirrored puzzle can be transposed to the same symmetry with lower minlex - i did that with "half" puzzles and only used band and row swapping and column swapping for the first stack).

Please, clarify - did you calculate sample patterns batch only or all possible patterns (I suspect the first is true)?

Now some thousands of the patterns can be eliminated too, because they have invalid bands (e.g. with 2 empty boxes and less than 4 clues in the third) or 4 invalid empty boxes. But i doubt, that the list can be reduced to less than 200000 with invalid subpatterns.

I think elimination potential of this techique is higher. I succeded in approx. 6 times seach space reduction for 17-clue valid puzzles after appling my "composition rules" (see the thread How to prove non-existance of 8-clue valid puzzles?). I used such rules:

Code: Select all

Valid puzzles composition rules
-------------------------------

Rule 1.  Map of any valid puzzle must be isomorphic to one of these maps:

Type 1   Type 2   Type 3   Type 4   Type 5   Type 6   Type 7

X X X    X X 0    X 0 0    X X 0    X X 0    X 0 0    X 0 0
X X X    X X X    X X X    X X X    X 0 X    0 X X    0 X X
X X X    X X X    X X X    0 X X    0 X X    X X X    0 X X

Rule 2.  Map posted below has no valid puzzles when A < 4

A 0 0
9 9 9
9 9 9

Rule 3.  Map posted below has no valid puzzles

1 1 1
1 9 9
1 9 9

Rule 4.  Map posted below has no valid puzzles

1 2 0
2 9 9
0 9 9

Rule 5.  Map posted below has no valid puzzles

0 1 2
1 9 9
2 9 9

Rule 6.  Map posted below has no valid puzzles

1 2 0
1 9 9
1 9 9

Rule 7.  Map posted below has no valid puzzles

2 1 0
1 9 9
0 9 9


plus 1 additional rule

Code: Select all

Rule 8.  Map posted below has no valid puzzles

1 1 1
1 1 1
9 9 9


So, I could filter out invalid puzzles by appling "composition rules", but I think we should discuss all possible patterns list first.

So i would have to do an exhaustive search for 200K symmetric 18 clues. From a single test i know, that it took more than an hour - and the puzzle had an additional symmetry. Thus with this program i guess, that on average i would need 5 hours on a single core on my PC.

To do it in say 6 months i would need a program, which is about 40 times faster and 6 cores. Possible, but no way for me.

I think we should classify all possible valid 18-clue symmetric puzzles (patterns). Such classification provide us with many small tasks instead of one "monolit" task. These small tasks (search for valid puzzles in narrow class of patterns) can be done independently by other participants and we would be able to see progress of search.

After classification we should try to reduce search space. Then we could compare possible algorithms by searching a small bunch of patterns.

Should we open new thread for 18-clue symmetric puzzles exhaustive search (and post to this thread results of the search only)?

Serg

[eleven]

Please, clarify - did you calculate sample patterns batch only or all possible patterns (I suspect the first is true)?

This list should include all possible valid patterns, if i made no mistake. It was not hard to calculate it, so it should not be a big problem for others to confirm that or find missing ones.

I think elimination potential of this techique is higher.

I only jumped through the list in puzzle form and looked for Rule1/Rule2 puzzles. I saw some areas with much of them (e.g. at the beginning), but not so much overall. I dont have any tools to find them. Maybe you already have.

I think we should classify all possible valid 18-clue symmetric puzzles (patterns). Such classification provide us with many small tasks instead of one "monolit" task. These small tasks (search for valid puzzles in narrow class of patterns) can be done independently by other participants and we would be able to see progress of search.

What do you have in mind ? Number of clues in column 5, box patterns etc. ? If so, i agree.

After classification we should try to reduce search space. Then we could compare possible algorithms by searching a small bunch of patterns.

Should we open new thread for 18-clue symmetric puzzles exhaustive search (and post to this thread results of the search only)?

Though i am interested to do more, it is not possible for me to invest more than a few hours per week for that. So from my side there will not come much input for a new thread.
In the moment i am interested in a simple idea to fasten the exhaustive search. I hope that i can test this week, if its of any worth. [Edit: Done, has no effect]

[Serg]

Hi, eleven!

Please, clarify - did you calculate sample patterns batch only or all possible patterns (I suspect the first is true)?

This list should include all possible valid patterns, if i made no mistake. It was not hard to calculate it, so it should not be a big problem for others to confirm that or find missing ones.

I tried to calculate 18-clue symmetric patterns' number too.

Though it is possible to calculate number of essentially different valid 18-clue symmetric patterns accurately, but it needs some time, so I present my calculation of estimated low bound of 18-clue symmetric patterns only. All calculations were done manually, so they can be cross-checked easily.

I consider such possible isomorphic transformations:
1. Bands permutations (6 ways).
2. Rows permutations within the upper band (6 ways).
3. Rows permutations within the middle band (6 ways).
4. Rows permutations within the lower band (6 ways).
5. Correlated (mirrored) columns permutations within left and right stacks (6 ways).

So, alone pattern has at most 6^5 = 7776 automorphisms.

To calculate the number of possible patterns we must consider 5 cases: central column (c5) may contain 0, 2, 4, 6 or 8 clues. We should calculate number of patterns for all cases and then to sum that numbers to obtain total number of possible patterns. Number of possible patterns in the left half of sudoku grid (rows r1-r9, columns c1-c4) is described by formula n!/(k!*(n-k)!), where n = 36 - number of cells in the left half of sudoku grid, k - number of clues in the left half of sudoku grid. This number must be multiplied by number of placing clues in column c5 - m!/(p!*(m-p)!), where m = 9 - number of cells in the c5 column, p - number of clues in the c5 column.

1. Column c5 contains 0 clues. k = 9, p = 0; number of patterns = 94143280.
2. Column c5 contains 2 clues. k = 8, p = 2; number of patterns = 30260340*36 = 1089372240.
3. Column c5 contains 4 clues. k = 7, p = 4; number of patterns = 8347680*126 = 1051807680.
4. Column c5 contains 6 clues. k = 6, p = 6; number of patterns = 1947792*84 = 163614528.
5. Column c5 contains 8 clues. k = 5, p = 8; number of patterns = 376992*9 = 3392928.

Total numbers of 18-clue symmetric patterns: 2,402,330,656 (accurate calculations).

Low bound of essentially different 18-clue symmetric patterns (as if each pattern would have 7776 automorphisms) - 2402330656/7776 = 308941 (approx.)

This estimation correlates with your number. Maybe I'll calculate accurate number of 18-clue symmetric patterns in some time.

Though i am interested to do more, it is not possible for me to invest more than a few hours per week for that. So from my side there will not come much input for a new thread.
In the moment i am interested in a simple idea to fasten the exhaustive search. I hope that i can test this week, if its of any worth.

So am I . I agree, it's not the time to open separate thread devoted to 18-clue symmetric patterns exhaustive search.

Serg

[Edited: I corrected an error in my calculations.]
[Edited2: I corrected an error in number of automorphisms calculations.]
[Edited3: I corrected an error in arithmetic calculation. Total numbers of 18-clue symmetric patterns is still 2,402,330,656 (as eleven wrote).]

[Afmob]

I have some spare CPU power (28 cores) and I'm currently going through your patterns to see how many I can analyze in one day. But as the number of automorphisms per pattern decreases the longer it takes to go through one pattern. In extreme cases it might take more than a day but the first patterns take less than a second. I'll give an update tomorrow.

[eleven]

Afmob,

please note that the first 36141 patterns are invalid, because in band 1 they only have 2 or 3 clues in box 2. Also many others can be eliminated from the outset, if you look at Serg's rules above.

I hoped, that Serg has tools to make these eliminations immediately, before someone burns cpu for nothing.

[eleven]

Serg,

by calculating the patterns i counted 2402330656 patterns, 1062301863 of them had 2 empty rows (cols) in a band (stack).
I dont know now, where the difference is from to your 2402331376, which is 720. At least my results should not be very wrong

[dobrichev]

Is there willing to reduce the list size as much as possible, to confirm it, then to share/debug the brute force part of the program code, and finally to split the task in pieces of reasonable size?

[Afmob]

First, we should reduce the list. We could use Serg's composition rules but as far as I know they haven't been confirmed yet, so I take them with a grain of salt.

[dobrichev]

The list is short enough so if there are incorrect composition rules the wrongly eliminated patterns could be reconsidered later.

I have no puzzle generation code which automatically takes into consideration the pattern automorphisms. Due to the required symmetry, each pattern has at least 2 automorphisms and this almost halves the search space. Each additional symmetry (cycle) halves the rest of the space. Am I correct?

If nobody has reliable tool that can exploit the additional symmetries, we can start processing the patterns that have no additional symmetries, i.e. the computationally hardest ones.

[Afmob]

I have those tools and probably others, too. But still some patterns will take at least a day to be fully analyzed.

[eleven]

I have no puzzle generation code which automatically takes into consideration the pattern automorphisms. Due to the required symmetry, each pattern has at least 2 automorphisms and this almost halves the search space. Each additional symmetry (cycle) halves the rest of the space. Am I correct?

With 2 automorphisms each puzzle has 3 equivalents with the same pattern.
Since for this pattern no digit symmetry is possible, they are all different and the search space can be reduced to a fourth.

However it takes some time to determine, which of the 4 you take as representative, e.g. the one with some minlex order (and the more automorhisms you have, the longer it takes).
But, as champagne demonstrated in the pattern games strategies, many puzzles can be excluded early with only a part of the numbers generated.

[eleven]

I have those tools and probably others, too. But still some patterns will take at least a day to be fully analyzed.

Can you post a hard one, please ? When i have time, i want to try it.