The New Sudoku Players' Forum

[denis_berthier]

Here is something that I don't understand:
I first gave gsf's program eleven's example pattern : ...XXX..X...X....XXX......XXX...X.......X.......X...XXX......XXX....X...X..XXX... and it generated 100 puzzles in less than 10s (on my old MacBookPro 2012).
Then I gave it Mike's pattern: X.XX.XX.X.X..X..X.X.XX.XX.XX.XX.XX.X.X..X..X.X.XX.XX.XX.XX.XX.X.X..X..X.X.XX.XX.X and it has now been running for 40 mins without generating anything.

[m_b_metcalf]

Here is something that I don't understand:
I first gave gsf's program eleven's example pattern : ...XXX..X...X....XXX......XXX...X.......X.......X...XXX......XXX....X...X..XXX... and it generated 100 puzzles in less than 10s (on my old MacBookPro 2012).
Then I gave it Mike's pattern: X.XX.XX.X.X..X..X.X.XX.XX.XX.XX.XX.X.X..X..X.X.XX.XX.XX.XX.XX.X.X..X..X.X.XX.XX.X and it has now been running for 40 mins without generating anything.

I was intrigued by this. I have several generators. Some of them have built-in checks for minimality or for a minimal level of difficulty, but that wasn't the root cause of why some found puzzles galore and others none at all. It turns out that if you generate a solution grid and impose the pattern then you can generate puzzles very fast. If, on the other hand, you try to build a puzzle from scratch you will find that it will in most cases have zero solutions (is invalid).

I don't know how gsf's program works, but if it has built-in checks for some property it may never produce anything for this pattern.

HTH

Mike

[1to9only]

Then I gave it Mike's pattern: X.XX.XX.X.X..X..X.X.XX.XX.XX.XX.XX.X.X..X..X.X.XX.XX.XX.XX.XX.X.X..X..X.X.XX.XX.X and it has now been running for 40 mins without generating anything.

I think it's just slow finding unique and minimal puzzles for this pattern.

I ran this (generates non-unique and non-minimal puzzles, output is to screen):

Code: Select all

gsf.exe -n100 -gt <pattern.txt


This generated 10 non-unique and non-minimal puzzles in about 8 minutes on an old quad-core cpu:

Code: Select all

7.95.48.1.5..6..4.3.89.75.24.62.19.3.3..7..1.9.76.84.58.17.53.6.9..8..5.5.31.62.4 #     2 F C45/S8.f
9.31.24.7.1..9..6.2.54.63.11.27.59.6.5..3..2.3.76.85.46.98.41.3.4..6..7.7.85.96.2 #     2 F C45/S8.f
3.82.16.5.4..8..3.7.56.94.19.71.83.4.1..9..2.2.34.51.68.97.42.3.3..5..1.1.29.35.8 #     2 F C45/S8.f
4.23.87.6.8..6..3.3.57.28.46.81.59.3.3..8..7.1.94.76.85.38.94.1.4..5..9.9.62.35.7 #     3 F C45/S8.f
4.83.17.5.6..5..9.2.58.61.35.76.98.1.1..4..3.3.91.84.69.27.36.4.3..6..8.6.45.23.9 #     2 F C45/S8.f
2.41.95.3.6..8..7.8.37.54.11.85.39.6.5..4..1.6.29.87.54.56.28.7.8..9..5.7.98.16.4 #     2 F C45/S8.f
9.28.71.6.6..4..2.1.42.68.56.71.45.2.1..6..7.5.37.86.97.85.32.4.5..7..8.3.64.97.1 #     2 F C45/S8.f
6.95.24.8.5..3..9.7.46.93.59.61.85.7.2..5..8.8.57.36.25.39.12.4.9..6..7.2.83.79.1 #     2 F C45/S8.f
2.34.51.8.4..1..3.8.17.94.61.96.78.3.6..2..4.4.85.36.26.49.23.5.3..8..9.9.73.42.1 #     2 F C45/S8.f
7.41.28.5.9..7..3.1.53.69.29.32.45.7.2..5..9.8.17.92.63.98.56.4.1..6..8.6.89.71.3 #     2 F C45/S8.f


[denis_berthier]

Mike, I think you're right: the problem is with (at least) one of the conditions of uniqueness or minimality for this pattern.

1to9only, I could reproduce your result, where those two conditions are not imposed.

I also tried with the pattern complementary to Mike's (exchange X's and .'s) and the (non-) result is as with the original pattern (in both cases, i.e. with or without the 2 conditions).

I tried to change the -euniq'()*(1==minimal)' condition in order to impose only uniqueness. Almost haphazardly, I wrote -euniq'()' . It seems to work, as I get puzzles.

Finally, it seems that the problem is with minimality, i.e. either there are very few minimals for this pattern or, as Mike said, there is something in the code.

[m_b_metcalf]

Finally, it seems that the problem is with minimality, i.e. either there are very few minimals for this pattern or, as Mike said, there is something in the code.

Denis, The highest number of clues for a minimal puzzle is known to be 40 (I think). Since this pattern has 45 clues it will never be minimal. As I've already found, about 7 out of ten puzzles have a unique solution. I just generated 1000 such puzzles (in 0.7 s). Are you interested in having them sent by e-mail?

Regards,

Mike

[denis_berthier]

Finally, it seems that the problem is with minimality, i.e. either there are very few minimals for this pattern or, as Mike said, there is something in the code.

Denis, The highest number of clues for a minimal puzzle is known to be 40 (I think). Since this pattern has 45 clues it will never be minimal.

Yes! I don't remember the exact number, but it's in this range.

I was coming to the same conclusion via another route. On checking the puzzles generated for eleven's pattern, I observed that for all of them, there is always a clue present in the cells of the given pattern. It means that gsf's program doesn't really try to find all the possible minimal puzzles that have no clue at other places than those of the given pattern (which is how I expected it to work). And the absence of result when we ask for minimals means that the clues in the pattern are always redundant.

As I've already found, about 7 out of ten puzzles have a unique solution. I just generated 1000 such puzzles (in 0.7 s). Are you interested in having them sent by e-mail?

Yes, thanks (the unique ones, I mean)
What was most interesting was to understand what happened with this pattern.
But maybe I could have a look at their complexity and see if they behave as those generated by yzfswf.

Your generator seems to be very fast. When I try to get 10 unique puzzles with gsf's, it take 1.5 minute.

[m_b_metcalf]

Your generator seems to be very fast. When I try to get 10 unique puzzles with gsf's, it take 1.5 minute.

I've sent you 1000 puzzles by PM. The program simply uses pre-computed grids and checks that the superimposed pattern gives a unique solution.

Regards,

Mike

[m_b_metcalf]

Your generator seems to be very fast. When I try to get 10 unique puzzles with gsf's, it take 1.5 minute.

Here are 13 generated from scratch, that took ~2 minutes.

Hidden Text: Show

Code: Select all

108907402040050010205401803306709501090040020402608907507104209010090070609305104                   
104608305060030040207104609302806704070010050408507906509201403040080060603705801                   
107203908080040010204109607301904205090010060408506109503607804040050090609408501                   
105907804040020090209401605301709206020060040406205903504608702090050060608302409                   
109306805060020070207105609302604701050030080406801902504907308090010060608203507                   
107506802080030010205401906308205709060040020402907603504103208070020050603804107                   
105908306060030070207605809301807902020050030409302108504706203080090010603501704                   
109706304050030010203809506302501609010040030408903107501402703020090060604108205                   
109206703030080060208307509301809604050070020402503901507108406010030090603702805                   
109702406060090070207503108306804907010070080408905203503609701090030040604107809                   
107308502030020010206109703309506801050080060408201309504602107010090020602804905                   
103506809070090060206708105309201704050080020408907601507309206030060010602405308                   
108502906040030010209601408301208709070060080402107603507903804020010090603405107                   


[denis_berthier]

Your generator seems to be very fast. When I try to get 10 unique puzzles with gsf's, it take 1.5 minute.

I've sent you 1000 puzzles by PM. The program simply uses pre-computed grids and checks that the superimposed pattern gives a unique solution.

Thanks
All the SERs are 1.2

[denis_berthier]

Now that it works on my Mac, I've been playing with gsf's program.
First of all, note that I have NO experience in puzzle generation (except the controlled-bias puzzles resulting from an old collaborative work); so, what I'm saying below may be obvious to those who have some.

I tried various patterns (with the uniqueness and minimality options on) and the results are very surprising to me. Of course, I expected a large difference between different puzzles. But what I didn't expect is the large differences between the templates for the hardest puzzles. And, here, by hardest, I mean the hardest of the hardest, the top 3 hardest, i.e. the only 3 known puzzles in B7B

..X....X..X....X.XX...........X.X..X.X.XX....X....X....X.X....X..X....X.....X.X.X ; eleven#3 ; B7B ; 11.9
.X...XX..X...X......X.......X.....X.X.X....X..X.X....X....X..X....X.X..X...X..X.X ; eleven#22 ; B7B ; 11.9
X.......X.X.X...X...X...X...X.X.........X.......X.X.X...X...X...X...X.X.X.......X ; Metcalf ; B7B ; 11.8
For reference, I also tried EasterMonster (it is rated SER 11.9 but it is only in B6B)

While gsf's program generates 100 puzzles in a few minutes for the first two patterns and (in more time) for EasterMonster, it doesn't produce anything after several hours for the 3rd pattern.
Does this inspire any comments ?

[m_b_metcalf]

But what I didn't expect is the large differences between the templates for the hardest puzzles. And, here, by hardest, I mean the hardest of the hardest, the top 3 hardest, i.e. the only 3 known puzzles in B7B

..X....X..X....X.XX...........X.X..X.X.XX....X....X....X.X....X..X....X.....X.X.X ; eleven#3 ; B7B ; 11.9
.X...XX..X...X......X.......X.....X.X.X....X..X.X....X....X..X....X.X..X...X..X.X ; eleven#22 ; B7B ; 11.9
X.......X.X.X...X...X...X...X.X.........X.......X.X.X...X...X...X...X.X.X.......X ; Metcalf ; B7B ; 11.8
For reference, I also tried EasterMonster (it is rated SER 11.9 but it is only in B6B)

While gsf's program generates 100 puzzles in a few minutes for the first two patterns and (in more time) for EasterMonster, it doesn't produce anything after several hours for the 3rd pattern.
Does this inspire any comments ?

Denis, This pattern has form. It's a pattern that was first noted near the bottom of the first page of 'Patterns Game 1.0' in the Interactive games forum. At the time, it required a fix to SE to get it rated (at 11.4 on that older version). Its discovery was serendipitous in that it resulted from a chance deletion of a clue from a pattern provided by jpf. An isomorph of the pattern was used in Patterns Game 169. You'll see, on p. 12 of the Results, how few entries there were.

HTH

Mike

[Edit: it took one of my programs about 30 minutes to find the following (although they're probably isomorphs of one another):

Code: Select all

1.......2.3.4...5...6...7...5.8.........1.......9.3.4...7...6...9...5.3.2.......1
1.......2.3.4...5...6...7...5.8.........6.......9.3.4...7...6...9...5.3.2.......1
1.......2.3.4...5...6...7...5.8.........1.......9.3.4...7...6...8...5.3.2.......1
1.......2.3.4...5...6...7...5.8.........6.......9.3.4...7...6...8...5.3.2.......1 all ED=10.7/10.7/3.4


]

[1to9only]

X.......X.X.X...X...X...X...X.X.........X.......X.X.X...X...X...X...X.X.X.......X ; Metcalf ; B7B ; 11.8

gsf is painfully slow working on this pattern, it took about 1 hour (old quad-core cpu) to produce this (unique and minimal) puzzle:

Code: Select all

7.......2.1.3...9...6...5...3.9.........2.......4.7.1...5...7...8...9.3.2.......6 # 95327 FNBTHWXYKOG C20.m/S2.a/M1.34.1


SE rates this ED=9.3/9.3/3.4.

[denis_berthier]

X.......X.X.X...X...X...X...X.X.........X.......X.X.X...X...X...X...X.X.X.......X ; Metcalf ; B7B ; 11.8
For reference, I also tried EasterMonster (it is rated SER 11.9 but it is only in B6B)
While gsf's program generates 100 puzzles in a few minutes for the first two patterns and (in more time) for EasterMonster, it doesn't produce anything after several hours for the 3rd pattern.

Denis, This pattern has form. It's a pattern that was first noted near the bottom of the first page of 'Patterns Game 1.0' in the Interactive games forum. At the time, it required a fix to SE to get it rated (at 11.4 on that older version). Its discovery was serendipitous in that it resulted from a chance deletion of a clue from a pattern provided by jpf. An isomorph of the pattern was used in Patterns Game 169. You'll see, on p. 12 of the Results, how few entries there were.

Hi Mike, Thanks for the history. I had no idea.
Speaking of history, I see, Feb. 2007. Twas near the time of my first encounter with Sudoku. I had no idea yet about the existence of Sudoku forums.
Anyway, I find this puzzle very interesting. It has very few minimals compared to the other hard ones.

[denis_berthier]

gsf is painfully slow working on this pattern, it took about 1 hour (old quad-core cpu) to produce this (unique and minimal) puzzle:

Code: Select all

7.......2.1.3...9...6...5...3.9.........2.......4.7.1...5...7...8...9.3.2.......6 # 95327 FNBTHWXYKOG C20.m/S2.a/M1.34.1

SE rates this ED=9.3/9.3/3.4.

My MacBookPro was busy with other things so I ran it on an old MacPro 2012. I should have waited full night.

[m_b_metcalf]

Anyway, I find this puzzle very interesting. It has very few minimals compared to the other hard ones.

You might be interested in a pattern that was used in both games 1 and 39 in 'Patterns Game 1.0' (pages 1 and 99), again devised by jpf.

Code: Select all

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

It yields only five known valid ratings:

Code: Select all

000100000234500010600000278000000050000060000080000000851000002090004635000009000 # 5 1.2 JPF
000100000234500010600000237000000040000080000010000000485000009070001864000007000 # 2 1.5 TTHsieh
000100000234500060500000738000000020000090000040000000715000006060005189000002000 # 3 1.7 JPF
000600000574100030200000185000000040000050000010000000639000002080009576000004000 # 1 2.0 JPF
000100000234500060700000893000000030000040000050000000463000007090005412000009000 # 4 4.2 TTHsieh

Regards,

Mike
[Edited 'puzzles' to 'ratings'.]