How regular is to generate sudoku with difficulty 9+ SE?

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

Postby StrmCkr » Sat May 26, 2007 10:36 pm

Code: Select all
 Advanced Tie Interceptor
*-----------*
 |..1|...|2..|
 |.3.|...|.4.|
 |5..|.3.|..6|
 |---+---+---|
 |...|1.7|...|
 |.4.|...|.8.|
 |...|9.2|...|
 |---+---+---|
 |3..|...|..8|
 |.6.|.5.|.3.|
 |..2|...|7..|
 *-----------*
man this puzzle so looks like a tie interceptor
from star wars.
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 840
Joined: 05 September 2006

Postby gsf » Tue May 29, 2007 3:13 pm

Ocean wrote:Here is a puzzle that seems to have singles backdoor size 3 (M3). Maybe the 'easiest' such puzzle so far?
Code: Select all
 *-----------*
 |..1|...|2..|
 |.3.|...|.4.|
 |5..|.3.|..6|
 |---+---+---|
 |...|1.7|...|
 |.4.|...|.8.|
 |...|9.2|...|
 |---+---+---|
 |3..|...|..8|
 |.6.|.5.|.3.|
 |..2|...|7..|
 *-----------*

this is a neat puzzle
simple singles propositions solve it (no nesting required)
only degree 2 and 3 candidates are needed
there's so few propositions that its q1 rating is 1732
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby ravel » Wed May 30, 2007 7:41 am

Amazing puzzle, Ocean. I never thought, that backdoor size is a good criterion for hardness, but i did not expect such an "easy" M3 puzzle (far away of all hardest lists).
ravel
 
Posts: 998
Joined: 21 February 2006

Postby gsf » Wed May 30, 2007 8:24 am

ravel wrote:Amazing puzzle, Ocean. I never thought, that backdoor size is a good criterion for hardness, but i did not expect such an "easy" M3 puzzle (far away of all hardest lists).

here's one from gordon's 22M 18 catalog
just a bit easier (6 proposition steps instead of 9) q1 rating 1278, singles backdoor size 3
Code: Select all
3.....2.....54.......6.....1.2..3..........648.........9.7...5.......1.8.5..6....

I'm checking the other 22M now (min q1 rating 6, max 8596)
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby gsf » Wed May 30, 2007 4:24 pm

found three M3 with q1 rating < 1000
Code: Select all
...5....13.8......4....3......61....9.....8......5.....6.7...2..1....3........49. #   795 FNP C18.m/M3.991.536
....2.58..4.3......1..........6...715.....2.....4.....2...59.........3.67........ #   922 FNP C18.m/M3.1432.371
.8..9....3......6....3...4.....1...5..2...9....7...8..65....1.....2.7........4... #   943 FNP C18.m/M3.1132.469

searching 10 <= q1 <= 99 now (12M 18 clue puzzles)
[edit: search done, only the M3's already posted for godon's 22M 18's]
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby Ocean » Thu May 31, 2007 8:22 pm

gsf wrote:this is a neat puzzle. simple singles propositions solve it (no nesting required). only degree 2 and 3 candidates are needed. there's so few propositions that its q1 rating is 1732
Thanks for the detailed analysis.
ravel wrote:Amazing puzzle, Ocean. I never thought, that backdoor size is a good criterion for hardness, but i did not expect such an "easy" M3 puzzle (far away of all hardest lists).
I was also surprised. Was experimenting with (or fooled by) the hypothesis "an M3 puzzle is probably extremely hard", which would give a relatively efficient screening tool. Anyway, it was fun to find one of them.

gsf wrote:here's one from gordon's 22M 18 catalog
just a bit easier (6 proposition steps instead of 9) q1 rating 1278, singles backdoor size 3
Code: Select all
3.....2.....54.......6.....1.2..3..........648.........9.7...5.......1.8.5..6....

...
found three M3 with q1 rating < 1000
...

These are genuine examples of easy M3s!
The statement "just a bit easier" must be an understatement: That particluar 18-clues M3-puzzle can be solved with a triple plus a few doubles. Also the other three M3 18s can be solved with basic techniques such as those incorporated in Simple Sudoku. (Compared to the puzzle that I referred to as "easy": it was still rated 9.4 by Sudoku Explainer.)

So, among the 18s, roughly one puzzle per five million has singles backdoor size three. Since these puzzles were readily available, it might seem funny that the famous conjecture was not refuted earlier. But at least it shows that a collection of this size is handy when searcing for extreme cases.
Ocean
 
Posts: 442
Joined: 29 August 2005

Postby gsf » Thu May 31, 2007 8:36 pm

Ocean wrote:Since these puzzles were readily available, it might seem funny that the famous conjecture was not refuted earlier. But at least it shows that a collection of this size is handy when searcing for extreme cases.

yes, that was lack of diligence on my part
no excuse ignoring a big supply of puzzles
but you're right that the conjecture that "conjecture breakers should be hard" got in the way
so did the abundance of neat threads on this forum
its hard to keep track of what threads go with what puzzle catalog

[edit: I just remebered this -- I had coded early versions of my solver to the conjecture (yes, not a good idea)
and had some limits in the backdoor code that would have hindered the M3 search anyway
I fixed the code when Ruud posted some clueless (pencilmark only) grids, some of which were M4's]

I found these trying to compile a catalog of Q1 ratings from 1 through 99999
in a day or so (when SE finishes rating the 4K or so puzzles already gathered) I'll post the catalog url

I'm hoping there will be some correlation between lower Q1 ratings and the standard techniques
that solve puzzles with those lower ratings
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby AW » Thu Jun 28, 2007 1:47 am

coloin wrote:Thanks AW
Code: Select all
SER,puzzle,tag
114,6.......2.9.4...5...1...7...5..84.......2.......3.5.4.2.....6...3...9.8...7.....1,coloin-04/13-1600
114,1.......2.9.4...5...6...7...5.3.4.......6........58.4...2...6...3...9.8.7.......1,coloin-04/13-1414
113,1.......2.9.4...5...6...7...5.3.4......96.........8.4...2...6...3...9.8.7.......1,coloin-04/13-1426
114,200000006050080010004000900070301000000820000000705030009000400080010050600000002,ultra0203

These grids had a high ER [and took gsf >7 hours to get the ER !] what do you make of them ?

C


Well. That was not easy. Solver now manages to solve coloin-04/13-1600, coloin-04/13-1414, coloin-04/13-1426. Sadly, doing this in reasonable time required many experiments and many failiures. The end result is interesting, but doesn't quite fit with the previous version. Still trying to understand what it all means.

Those three puzzles are really odd.:)
AW
 
Posts: 27
Joined: 31 January 2007

Postby Eioru » Tue Aug 21, 2007 4:58 pm

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


First one can't be produced because it is symmetry and 17 clues.
So I think the second and third one will be possible to 11.0+.
Now, I'm trying the third one, 25 clues, but really difficult.
Eioru
 
Posts: 182
Joined: 16 August 2006

Postby JPF » Tue Aug 21, 2007 5:32 pm

Pattern 3 :

I guess you are not looking for minimal puzzles:)

I don't see a great deal of difficulty to find a puzzle with this pattern.
Here's a minimal 20 clues with a sub-pattern :

Code: Select all
 . . 1 | . . . | . 2 .
 3 . . | . . 4 | . . .
 . . . | 5 . . | . . 6
-------+-------+-------
 . 5 . | 2 . 7 | 4 . .
 . . . | . . . | . . .
 . . 7 | 8 . 3 | . 1 .
-------+-------+-------
 5 . . | . . 1 | . . .
 . . . | 9 . . | . . 2
 . 6 . | . . . | 5 . .


which is a sub-pattern of Pattern 2 too.

I probably missed something.

JPF
JPF
2017 Supporter
 
Posts: 3754
Joined: 06 December 2005
Location: Paris, France

Postby coloin » Wed Aug 22, 2007 12:34 am

Yes I agree that they are easy to generate......but maybe we can do a similar thing as before !

This [different] pattern [with 19 clues ] was searched by nick70 here
here is his first puzzle
Code: Select all
+---+---+---+
|1..|.5.|...|
|...|1..|.3.|
|..7|...|6..|
+---+---+---+
|.5.|..8|...|
|9..|.2.|..1|
|...|3..|.6.|
+---+---+---+
|..6|...|8..|
|.3.|..7|...|
|...|.9.|..5|
+---+---+---+ SE 1.2


taking away the clues from the central box gives this subpuzzle
Code: Select all
1...5.......1...3...7...6...5.......9.......1.......6...6...8...3...7.......9...5 #58792 sol.
reduced because these clues are infered
1.3.5......91..53.5.7...61..5.......9......51.......6..96...8...35..7196....9...5


taking a 'difficult' puzzle from nick70s list
Code: Select all
+---+---+---+
|1..|.5.|...|
|...|1..|.6.|
|..9|...|3..|
+---+---+---+
|.6.|..3|...|
|4..|.2.|..5|
|...|7..|.2.|
+---+---+---+
|..7|...|8..|
|.3.|..2|...|
|...|.4.|..1|
+---+---+---+ SE 9.0 [with 16 clues NO clues are infered]


I came up with these ones using the techniques described earlier in the thread
Code: Select all
+---+---+---+
|1..|.2.|...|
|...|3..|.4.|
|..5|...|6..|
+---+---+---+
|.3.|...|...|
|2..|7.1|..8|
|...|.48|.9.|
+---+---+---+
|..6|...|2..|
|.7.|..9|...|
|...|.8.|..1|
+---+---+---+ SE 9.2
and
Code: Select all
+---+---+---+
|1..|.2.|...|
|...|3..|.4.|
|..5|...|6..|
+---+---+---+
|.3.|258|...|
|2..|.1.|..8|
|...|.6.|.9.|
+---+---+---+
|..6|...|5..|
|.4.|..9|...|
|...|.8.|..1|
+---+---+---+  SE 9.1
and
Code: Select all
+---+---+---+
|1..|.2.|...|
|...|3..|.4.|
|..5|...|6..|
+---+---+---+
|.3.|4.6|...|
|2..|.7.|..8|
|...|.1.|.9.|
+---+---+---+
|..6|...|5..|
|.7.|..9|...|
|...|.8.|..1|
+---+---+---+  SE 9.0


A long way off from 11.0.....but maybe this is what Eioru means and there is certainly scope for better.
C
coloin
 
Posts: 1733
Joined: 05 May 2005

Postby AW » Thu Aug 23, 2007 3:35 am

Hey! I thought I observed something interesting about the Easter Monster puzzle. I don't know if it has been pointed out before. As I recall, it's has a singles back-door size 3, right?

Well, it also seems to have a... erm... singles front-door size 2. For lack of a better term. Placing any one of the remaining candidates never leads to a contradiction, using singles only.

Has anyone discussed this previously?
AW
 
Posts: 27
Joined: 31 January 2007

Postby gsf » Thu Aug 23, 2007 5:27 am

AW wrote:Hey! I thought I observed something interesting about the Easter Monster puzzle. I don't know if it has been pointed out before. As I recall, it's has a singles back-door size 3, right?

Well, it also seems to have a... erm... singles front-door size 2. For lack of a better term. Placing any one of the remaining candidates never leads to a contradiction, using singles only.

Has anyone discussed this previously?

that's exactly the observation illuminated by the -q1 rating option in my solver
using singles, no singleton candidate assignment leads to a contradiction
pairwise candidate assignments lead to 8 contradictions, but those don't help the singles only solution
it requires singles+locked-candidates, and it takes 18 pairwise propositions to get 18
contradcitions before singles+locked-candidates solves the puzzle
its a great puzzle
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby tarek » Fri Sep 07, 2007 8:08 pm

I wasn't sure where to post these puzzles. These are new puzzles that require 3 singles magic cells to break.
Code: Select all
...6........9.3.7..3..78...4.......5..6...1...8...7.3...1.....45.....6...9..2..8.
..2.7....5....3....8.4...6..6.8....9..7.5....3....2......1..546.4....8.1.......9.
....4..7..9....3.....3..9.42....7....4.8....9..1.5.....8.4..6....5..1...7...2....
..1..8...2...9.5...6.4.....9.....3.7.......6.....7..253...2...9..46......8...1...
5.......7.1.4...9...3...8...2.64.........1......9.2.6.8....45...9...6.1...7.....3

tarek
User avatar
tarek
 
Posts: 2699
Joined: 05 January 2006

Postby gsf » Fri Sep 07, 2007 8:29 pm

tarek wrote:I wasn't sure where to post these puzzles. These are new puzzles that require 3 singles magic cells to break.
Code: Select all
...6........9.3.7..3..78...4.......5..6...1...8...7.3...1.....45.....6...9..2..8.
..2.7....5....3....8.4...6..6.8....9..7.5....3....2......1..546.4....8.1.......9.
....4..7..9....3.....3..9.42....7....4.8....9..1.5.....8.4..6....5..1...7...2....
..1..8...2...9.5...6.4.....9.....3.7.......6.....7..253...2...9..46......8...1...
5.......7.1.4...9...3...8...2.64.........1......9.2.6.8....45...9...6.1...7.....3

tarek

nice
there's 22 now, 12 by you
I added them to q1-taxonomy.dat
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

PreviousNext

Return to General