I don't really know much about Sudokus but I made a sudoku (not the result of any thought, I basically removed numbers from a full grid as long as it had only 1 solution) and it came out with this weird puzzle:
. . .|. 7 .|9 4 .
. . .|. 9 .|. . 5
3 . .|. . 5|. 7 .
-----+-----+-----
. . 7|4 . .|1 . .
4 6 3|. . .|. . .
. . .|. . 7|. 8 .
-----+-----+-----
8 . .|. . .|. . .
7 . .|. . .|. 2 8
. 5 .|2 6 .|. . .
I went to the Sudoku Explainer and it rated it 9.3, whereas the Toughest Known Puzzle with the Sudoku Susser was a 9.5. However, this Sudoku gets 27984 with SudoCue and the Toughest Known Puzzle was only 17000 or so. Is it common for these things to be so different?
Very hard sudoku for Sudocue
16 posts
• Page 1 of 2 • 1, 2
Very hard sudoku for Sudocue
by sirdave » Wed Apr 09, 2008 6:16 pm
- sirdave
- 2010 Supporter
- Posts: 36
- Joined: 04 January 2006
by sirdave » Wed Apr 09, 2008 8:40 pm
I made about 100 others using a computer program with the same method, but only 2 surpassed 9 SE and only about 5 required tabling on the Sudoku Susser (I didn't put them into SudoCue). So I suppose I was very very lucky? I just found a thread where someone made millions and got none over 9.2 SE.
- sirdave
- 2010 Supporter
- Posts: 36
- Joined: 04 January 2006
by tarek » Wed Apr 09, 2008 9:53 pm
This is interesting SirDavid....
One of the most successful methods in generating the hardest of puzzle was to follow this template:
Where all but the centre box were pre-set clues, you then go through all possible combination clues to fill the centre box & minimize from there.
Now, would it be possible to super-impose some templates on pre-set solution grids leaving let's say 2 boxes full (one of them being the centre box the other probably a corner box) then minimize. then change the grid with a new one with the same templates again & minimize....
the templates would follow these isomorphs of corner boxes
I can see maybe 4^5 templates
just an idea
tarek
One of the most successful methods in generating the hardest of puzzle was to follow this template:
- Code: Select all
O . . | . . . | . . O
. O . | O . . | . O .
. . O | . . . | O . .
-------+-------+-------
. . . | O O O | . . .
. O . | O O O | . O .
. . . | O O O | . . .
-------+-------+-------
. . O | . . . | O . .
. O . | . . O | . O .
O . . | . . . | . . O
Where all but the centre box were pre-set clues, you then go through all possible combination clues to fill the centre box & minimize from there.
Now, would it be possible to super-impose some templates on pre-set solution grids leaving let's say 2 boxes full (one of them being the centre box the other probably a corner box) then minimize. then change the grid with a new one with the same templates again & minimize....
the templates would follow these isomorphs of corner boxes
I can see maybe 4^5 templates
- Code: Select all
O . . |
. O . |
. . O |
-------+
. O . |
O . . |
. . O |
-------+
. . O |
O . . |
. O . |
-------+
. O . |
. . O |
O . . |
-------+
O . . |
. . O |
. O . |
-------+
just an idea
tarek
-
tarek - Posts: 3762
- Joined: 05 January 2006
by coloin » Thu Apr 10, 2008 1:01 am
I think I tried the double box method - without result.
With respect to the pattern where all corner boxes have 3 clues in the disjoint pattern. :
The row-swapping of the corner boxes has the result of moving around the solitary clues in their box.
As I found it you can always swap 3 of the corner boxes to the diagonal cross pattern which leaves one corner box with 6 options.
Moving the solitary clues around increase the number of grid solutions solutions for the 16-template. This resulted in less puzzles.
I dont suppose we can enumerate all the 16-templates ? [And I dont mean "all" !]
Upper limit = 6 * 9^4 / [6^2 ] = 1093.5
6 corner patterns, 9 places for the solitary clues [^4], 6 central band row swaps [^2]
With a few more refective symmetries this is getting near 4^5
C
With respect to the pattern where all corner boxes have 3 clues in the disjoint pattern. :
The row-swapping of the corner boxes has the result of moving around the solitary clues in their box.
As I found it you can always swap 3 of the corner boxes to the diagonal cross pattern which leaves one corner box with 6 options.
Moving the solitary clues around increase the number of grid solutions solutions for the 16-template. This resulted in less puzzles.
I dont suppose we can enumerate all the 16-templates ? [And I dont mean "all" !]
Upper limit = 6 * 9^4 / [6^2 ] = 1093.5
6 corner patterns, 9 places for the solitary clues [^4], 6 central band row swaps [^2]
With a few more refective symmetries this is getting near 4^5
C
- coloin
- Posts: 2385
- Joined: 05 May 2005
- Location: Devon
by sirdave » Thu Apr 10, 2008 1:35 am
Wow, that is a very interesting method. It looks like it would work since it makes all those puzzles with few clues in the same 2 regions, though maybe I'm wrong about the reason. It's above my coding skills to make something like this work though, I used a beginner's version of basic and it takes about 2 minutes to generate a puzzle even via my very simple method.
I was wrong about 2 over 9.0 SE, it seems to be 2 over 8.0. I just thought I'd post this 8.9 out of a sample of 150 or so that I have now as well as that 9.3, and maybe I'll generate more overnight:
. . .|7 . .|. 3 .
. . .|4 6 .|8 . 7
. . .|. . 2|. . .
-----+-----+-----
. 1 .|. . 3|. . 5
. 4 .|. . .|. 1 .
. . .|8 . 9|3 . .
-----+-----+-----
. 5 3|. 8 .|. 2 .
1 . .|. . .|. . 6
7 . .|. 2 .|4 . .
P.S. Is there any way to get SE to read a series of puzzles and rate them if they are in the following format:
(sudoku in format like " 23 91 4 12 8 2 5 8 5 7 9 91 345 5 7 3 6 8 34 " without quotation marks)(carriage return)(another sudoku) etc.? This would make it a lot easier, as it is I copy-paste into the Susser and manually input those that require tabling into the SE but this takes a while. Thanks!
EDIT: It messed up the spaces in the example above, but you get the idea, and there's no need to post it- solving heuristics were just
4 x Comprehensive Forcing Chains
2 x Simple Forcing Chains
1 x Simple Forcing Loops
1 x XY-Wing
2 x Intersection Removal
1 x Simple Hidden Sets
2 x Simple Naked Sets
13 x Pinned Squares
with no tabling or Nishio. I was trying to show one of the mediocre puzzles generated by this method, I get some like this a lot with just pins and a few that need tabling.
I was wrong about 2 over 9.0 SE, it seems to be 2 over 8.0. I just thought I'd post this 8.9 out of a sample of 150 or so that I have now as well as that 9.3, and maybe I'll generate more overnight:
. . .|7 . .|. 3 .
. . .|4 6 .|8 . 7
. . .|. . 2|. . .
-----+-----+-----
. 1 .|. . 3|. . 5
. 4 .|. . .|. 1 .
. . .|8 . 9|3 . .
-----+-----+-----
. 5 3|. 8 .|. 2 .
1 . .|. . .|. . 6
7 . .|. 2 .|4 . .
P.S. Is there any way to get SE to read a series of puzzles and rate them if they are in the following format:
(sudoku in format like " 23 91 4 12 8 2 5 8 5 7 9 91 345 5 7 3 6 8 34 " without quotation marks)(carriage return)(another sudoku) etc.? This would make it a lot easier, as it is I copy-paste into the Susser and manually input those that require tabling into the SE but this takes a while. Thanks!
EDIT: It messed up the spaces in the example above, but you get the idea, and there's no need to post it- solving heuristics were just
4 x Comprehensive Forcing Chains
2 x Simple Forcing Chains
1 x Simple Forcing Loops
1 x XY-Wing
2 x Intersection Removal
1 x Simple Hidden Sets
2 x Simple Naked Sets
13 x Pinned Squares
with no tabling or Nishio. I was trying to show one of the mediocre puzzles generated by this method, I get some like this a lot with just pins and a few that need tabling.
- sirdave
- 2010 Supporter
- Posts: 36
- Joined: 04 January 2006
by RW » Thu Apr 10, 2008 4:09 am
SirDavid wrote:P.S. Is there any way to get SE to read a series of puzzles and rate them
Nicolas Juillerat wrote:Included my old testing routines in the .jar file. There is now an
unsupported way of analysing many Sudokus at once:
java -cp SudokuExplainer.jar diuf.sudoku.test.Tester sudoku.txt result.txt
where "sudoku.txt" is a file with Sudokus, one line of 81 digits per puzzle;
and "result.txt" is the file in which analysis results are saved.
Btw. What Tarek forgot to mention was that in the given sixteen clue template (all but box 5) the same digit should not appear twice in any stack or band. Puzzles generated in this way in general have ER>9.0, I've seen none below ER 8 and I believe it's impossible to create a puzzle like this wih ER<7.
RW
- RW
- 2010 Supporter
- Posts: 1010
- Joined: 16 March 2006
by tarek » Thu Apr 10, 2008 12:30 pm
Thanx RW,
Coloin,
I guess you have already tried this
What is the range of multiple-solutions for this 15 clue template that would generate a high number of valid minimal puzzles in the (21-22 clue range) ?
Do you think that we exhausted all 16-clue templates in the previous search ?
Would it be worth looking for templates (16 or 15) that satisfy all criteria & solution-counts. from randomly generated solution grids?
something like this:
1. generate a solution grid
2. superimpose template (pre-defined or cycle through 4^5 patterns discussed above)
3. check for elligibility (digits in stack or band)
4. check for solution count range
5. output templates.
tarek
Coloin,
I guess you have already tried this
- Code: Select all
X . . | . . . | . . X
. X . | X . . | . X .
. . X | . . . | X . .
-------+-------+-------
. X . | O O O | O O O
. . . | O O O | O O O
. . . | O O O | O O O
-------+-------+-------
. . X | . . . | X . .
. X . | . . X | . X .
X . . | . . . | . . X
What is the range of multiple-solutions for this 15 clue template that would generate a high number of valid minimal puzzles in the (21-22 clue range) ?
Do you think that we exhausted all 16-clue templates in the previous search ?
Would it be worth looking for templates (16 or 15) that satisfy all criteria & solution-counts. from randomly generated solution grids?
something like this:
1. generate a solution grid
2. superimpose template (pre-defined or cycle through 4^5 patterns discussed above)
3. check for elligibility (digits in stack or band)
4. check for solution count range
5. output templates.
tarek
-
tarek - Posts: 3762
- Joined: 05 January 2006
by sirdave » Thu Apr 10, 2008 12:53 pm
Thanks for that, I don't know what that extraction of different puzzle lines means but most likely my dad does (he knows Java).
Oh here's a 9.0 that requires tables 4 on the sudoku susser
. 6 .|. 3 .|. . 8
. . 7|. . .|5 . .
. . 2|. . .|. 4 9
-----+-----+-----
. . 6|. 5 .|. . .
7 . .|4 . .|. . .
. 9 .|8 . 1|. 3 .
-----+-----+-----
. 7 .|9 . .|. . .
. . .|. . 2|. 1 .
8 . .|1 . .|. 9 4
an 8.5 that requires 3 nishios and a table
. . .|3 . .|9 . .
9 2 .|. . .|. . 5
7 . .|. 5 .|. 1 .
-----+-----+-----
. 5 .|. 4 .|. . 1
1 . 2|6 . .|8 5 .
. . 8|. . .|. . .
-----+-----+-----
. . 6|. . .|. . 7
. . .|. 6 7|1 3 .
5 . .|. . .|. . 2
I'm pretty sure I made both of these manually using this method, but I'm not sure (it was a while ago).
I know these 3 were by my method and among those same 150:
8.3
8 . .|3 . 1|. . .
. 4 .|. . 7|. 3 .
. . .|6 5 .|. . .
-----+-----+-----
. . 7|1 . .|2 . .
. . .|. 6 5|. . 9
. . .|. . .|. 7 6
-----+-----+-----
. . .|. 7 .|9 2 .
. 6 .|. . .|3 . .
1 . 2|. . .|. 8 .
and 8.3
9 7 .|. . 1|. 6 .
. . .|. 5 .|7 . .
6 . .|. . .|. . 2
-----+-----+-----
. . .|4 . .|. 7 6
. . .|. . .|8 . .
. . 6|. . 8|2 4 3
-----+-----+-----
. . 1|. . 3|. 8 7
. . .|. . 9|3 . .
5 . 4|. . 6|. . .
and 8.5
. 4 .|. . .|. 3 1
. . 8|. 3 .|. . .
. 1 .|5 . .|8 9 .
-----+-----+-----
. 5 .|. . .|. . .
1 . .|3 . 2|. . .
. . .|. 7 .|9 . .
-----+-----+-----
2 9 1|. . 3|. . 6
. 6 .|. 2 .|. . .
. . 4|. 8 .|1 . 9
EDIT: Oh tarek posted while I was making this post lucky I checked
Oh here's a 9.0 that requires tables 4 on the sudoku susser
. 6 .|. 3 .|. . 8
. . 7|. . .|5 . .
. . 2|. . .|. 4 9
-----+-----+-----
. . 6|. 5 .|. . .
7 . .|4 . .|. . .
. 9 .|8 . 1|. 3 .
-----+-----+-----
. 7 .|9 . .|. . .
. . .|. . 2|. 1 .
8 . .|1 . .|. 9 4
an 8.5 that requires 3 nishios and a table
. . .|3 . .|9 . .
9 2 .|. . .|. . 5
7 . .|. 5 .|. 1 .
-----+-----+-----
. 5 .|. 4 .|. . 1
1 . 2|6 . .|8 5 .
. . 8|. . .|. . .
-----+-----+-----
. . 6|. . .|. . 7
. . .|. 6 7|1 3 .
5 . .|. . .|. . 2
I'm pretty sure I made both of these manually using this method, but I'm not sure (it was a while ago).
I know these 3 were by my method and among those same 150:
8.3
8 . .|3 . 1|. . .
. 4 .|. . 7|. 3 .
. . .|6 5 .|. . .
-----+-----+-----
. . 7|1 . .|2 . .
. . .|. 6 5|. . 9
. . .|. . .|. 7 6
-----+-----+-----
. . .|. 7 .|9 2 .
. 6 .|. . .|3 . .
1 . 2|. . .|. 8 .
and 8.3
9 7 .|. . 1|. 6 .
. . .|. 5 .|7 . .
6 . .|. . .|. . 2
-----+-----+-----
. . .|4 . .|. 7 6
. . .|. . .|8 . .
. . 6|. . 8|2 4 3
-----+-----+-----
. . 1|. . 3|. 8 7
. . .|. . 9|3 . .
5 . 4|. . 6|. . .
and 8.5
. 4 .|. . .|. 3 1
. . 8|. 3 .|. . .
. 1 .|5 . .|8 9 .
-----+-----+-----
. 5 .|. . .|. . .
1 . .|3 . 2|. . .
. . .|. 7 .|9 . .
-----+-----+-----
2 9 1|. . 3|. . 6
. 6 .|. 2 .|. . .
. . 4|. 8 .|1 . 9
EDIT: Oh tarek posted while I was making this post lucky I checked
- sirdave
- 2010 Supporter
- Posts: 36
- Joined: 04 January 2006
by coloin » Thu Apr 10, 2008 8:18 pm
It was a while ago so I dont recall really what I tried !
I think the 16 clue template has to have less than <100000 grid solutions for it to get enough puzzles in the central box with 4 or 5 [or 6 - many puzzles]
Need to look at the 15 clue templates from our puzzles to get the 15 clue counts.
There is a puzzle from the Easter Monster [puzzle and same solution grid] which shifts one clue from the central box to a "solitary clue" box.
However we start to generate templates, I get a feeling that the way tarek and i did a {-1+1} on our existing puzzles [at least thats what I did] we maybe have found many of the puzzles, but never all of course.
It might be worth revisting the templates, I do have a version of gsfs solver which can canonicalise these
C
I think the 16 clue template has to have less than <100000 grid solutions for it to get enough puzzles in the central box with 4 or 5 [or 6 - many puzzles]
Need to look at the 15 clue templates from our puzzles to get the 15 clue counts.
There is a puzzle from the Easter Monster [puzzle and same solution grid] which shifts one clue from the central box to a "solitary clue" box.
- Code: Select all
+---+---+---+
|1..|...|..2|
|.9.|4..|.5.|
|..6|...|7..|
+---+---+---+
|.5.|9.3|...|
|...|.7.|..5|
|...|8..|.4.|
+---+---+---+
|7..|...|6..|
|.3.|..9|.8.|
|..2|...|..1|
+---+---+---+ 10.9 Coloin-04/16/1a 22683056 sol.
However we start to generate templates, I get a feeling that the way tarek and i did a {-1+1} on our existing puzzles [at least thats what I did] we maybe have found many of the puzzles, but never all of course.
It might be worth revisting the templates, I do have a version of gsfs solver which can canonicalise these
C
- coloin
- Posts: 2385
- Joined: 05 May 2005
- Location: Devon
by tarek » Thu Apr 10, 2008 10:47 pm
coloin wrote:However we start to generate templates, I get a feeling that the way tarek and i did a {-1+1} on our existing puzzles [at least thats what I did] we maybe have found many of the puzzles, but never all of course.
Thanx for the numbers. I wasn't doing it in a systematic way (finding templates)..... The way that 17-clue puzzles have increased dramatically suggests that we are probably missing some pockets in the templates & "hardest puzles", therefore collecting these templates sounded like a good idea. The way that you put it, makes me think twice before attempting this again however
(the previous search was indeed, extensive)Maybe we should just keep this thought until a new "hardest" comes out, that would provide the spark IMO.
That is good, whay didn't I think of this.coloin wrote:I do have a version of gsfs solver which can canonicalise these
-
tarek - Posts: 3762
- Joined: 05 January 2006
by coloin » Fri Apr 11, 2008 12:24 am
Yes the search was extensive {-1+1} x10 or so, maybe more
Yes the key to the templates was to have less than 1000000 grid solutions, at the same time there was no induced clues. It is the induced clues which normally bring this down. And the lack of induced clues is a feature in all the [n-1] sub-puzzles in the extreme puzzles we found.
For example, this template didnt work
I cant remember why the templates had such a low solution count.
Im also happy to leave this untill GN gets overtaken, I cant see who would do it though !
C
Yes the key to the templates was to have less than 1000000 grid solutions, at the same time there was no induced clues. It is the induced clues which normally bring this down. And the lack of induced clues is a feature in all the [n-1] sub-puzzles in the extreme puzzles we found.
For example, this template didnt work
- Code: Select all
+---+---+---+
|1..|...|..6|
|.2.|7..|.5.|
|..3|...|4..|
+---+---+---+
|.7.|...|...|
|...|...|...|
|...|...|.8.|
+---+---+---+
|..6|...|1..|
|.5.|..8|..3|
|4..|...|.2.|
+---+---+---+ because this 16 clues template has 6298650 sol.
I cant remember why the templates had such a low solution count.
- Code: Select all
+---+---+---+
|1..|...|..9|
|.2.|.4.|.7.|
|..3|...|5..|
+---+---+---+
|...|..5|...|
|.4.|...|.8.|
|...|.32|...|
+---+---+---+
|..5|...|3..|
|.8.|.7.|.2.|
|9..|...|..1|
+---+---+---+ SE 9.2, the template has a surprizing 108864 sol. only
Im also happy to leave this untill GN gets overtaken, I cant see who would do it though !
C
- coloin
- Posts: 2385
- Joined: 05 May 2005
- Location: Devon
by sirdave » Fri Apr 11, 2008 4:52 pm
Boy, that is a long thread! I changed my generator and now about half of the puzzles are over 7 SE. I made it so it eliminates the following positions last
1...1...1
.1.....1.
..1...1..
...1.1...
1...1...1
...1.1...
..1...1..
.1.....1.
1...1...1
and it now comes up with many more 7.0+ puzzles, and many more diagonals. I will try to get my dad to convert the program into C if possible, or maybe someone else could use the idea if they wanted to, or maybe even it's already been tried, but I will keep plugging along at my puzzle every few minutes and see what happens. Thanks for referencing that thread, I had seen it before poking around here but didn't pay much attention as I just thought it was a collection of sudokus, not a discussion of methods.
1...1...1
.1.....1.
..1...1..
...1.1...
1...1...1
...1.1...
..1...1..
.1.....1.
1...1...1
and it now comes up with many more 7.0+ puzzles, and many more diagonals. I will try to get my dad to convert the program into C if possible, or maybe someone else could use the idea if they wanted to, or maybe even it's already been tried, but I will keep plugging along at my puzzle every few minutes and see what happens. Thanks for referencing that thread, I had seen it before poking around here but didn't pay much attention as I just thought it was a collection of sudokus, not a discussion of methods.
- sirdave
- 2010 Supporter
- Posts: 36
- Joined: 04 January 2006
by RW » Fri Apr 11, 2008 6:19 pm
I assume you found that pattern quite in the beginning of the hardest thread. Methods for finding hard puzzles have been refined a lot since then. The method tarek described above, which is the best known method, was actually invented in this thread. Also a long thread, but the basics of the method is described by coloin in the first two pages. Also, on the second page gsf describes how you can use his program to find these puzzles.
RW
RW
- RW
- 2010 Supporter
- Posts: 1010
- Joined: 16 March 2006
16 posts
• Page 1 of 2 • 1, 2
