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

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

Postby ronk » Sun Apr 15, 2007 1:54 pm

ravel wrote:After this inflation of gsfr 99990+ puzzles i think, we should hold a list with all known minimal (gsf) canonicalized puzzles.

Because of puny CPU power, I haven't been able to participate in this exciting thread, so my opinion carries little weight I'm sure, but I must object to puzzle "distribution" only in canonical form.

That a puzzle has been canonicalized is a very BIG clue. That said, I realize that correctly guessing that a very difficult puzzle has been canonicalized may not be of much help to a manual solver.

However, if the puzzles must to be normalized to one form, my vote is for the "digit-ordered normalization" that JPF (and others, I think) use, e.g., ...
JPF wrote:
Code: Select all
 1 . . | . . . | . . 2
 . . 3 | 4 . . | . 5 .
 . 6 . | . . . | 7 . .
-------+-------+-------
 . . . | 8 5 . | . 9 .
 . . . | 3 . 6 | . . .
 . . 8 | . 9 . | . . .
-------+-------+-------
 . 2 . | . . . | 1 . .
 7 . . | . . . | . . 6
 . . 9 | . 8 . | . 3 .

... where in a top-to-bottom scan of the rows, non-repeating digits appear in order.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby ravel » Sun Apr 15, 2007 3:59 pm

Of course i dont mind, which kind of normalization should be used and i agree, that "digit-ordered normalization" shows the puzzle in nicer form. But the main purpose for such a list is, that people, who find hard puzzles, quickly can check, if it already has been found by others.
So at least a fast public program for that normalization must be available.
ravel
 
Posts: 998
Joined: 21 February 2006

Postby m_b_metcalf » Sun Apr 15, 2007 4:49 pm

ronk wrote:Because of puny CPU power, I haven't been able to participate in this exciting thread, so my opinion carries little weight I'm sure, but I must object to puzzle "distribution" only in canonical form.


It's not only CPU power, but also luck that sometimes counts. The first 11.4 was produced by fiddling around with a puzzle produced by JPF. From that point it cost probably less than a minute or two.

Regards,

Mike Metcalf
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 9210
Joined: 15 May 2006
Location: Berlin

Postby AW » Sun Apr 15, 2007 5:08 pm

gsf wrote:I'll write up the ideas behind the nested propositions and recalibration and post later this weekend


Looking forward to it! I'm very curious as to how you chose to treat "nested propositions", and how it relates to layers of swords and jellies.

ravel wrote:Mauricio's non minimal puzzle (62 non isomorphic minimals):
600002059520040010003500200300194500010658030005273001004005100030020045750400008


This puzzle is very interesting. The very hard puzzles found in this thread (and the hardest thread) have a small number of givens (21 or less). They lock up very early on, with approximately 200-250 undecided candidates. Mauricio's puzzle locks up with a very small number of remaining candidates : 128 (148 without substitutions), and scores 2 swords in the end. Seems to me this is of particular interest when trying to identify just what is the minimal requirement for a puzzle to be very hard. It shows that, even with a complete box in the givens and a high average of givens per house, you can still be nasty!

JPF wrote:100000002003400050060000700000850090000306000008090000020000100700000006009080030 JPF 04/14/B4


This puzzle is yet another jelly from JPF. 13 swords and 1 jelly.

Perhaps someone could start a new thread in which we could discuss, specifically, "the ratings game". And maybe come to a temporary agreement as to how the hardest grids should be classified? I gather from current discussions that the systems have major drawbacks: for some it's not always quite certain what is being rated, for some it takes too long to get a number, for some ratings differ for isomorphic puzzles. There is little motivation to produce a serious rating program when there's no consensus on how puzzles shoule be rated!
AW
 
Posts: 27
Joined: 31 January 2007

Postby gsf » Sun Apr 15, 2007 6:08 pm

ronk wrote:
ravel wrote:After this inflation of gsfr 99990+ puzzles i think, we should hold a list with all known minimal (gsf) canonicalized puzzles.

Because of puny CPU power, I haven't been able to participate in this exciting thread, so my opinion carries little weight I'm sure, but I must object to puzzle "distribution" only in canonical form.

right, the original form should be preserved
and canonicalization used mainly as a key to weed out equivalent puzzles
there's really no need to list the canonical form as long as posted lists have been cleared of dups offline
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby tarek » Sun Apr 15, 2007 6:20 pm

Just to add to the difficulty argument which would be hopefully re-addressed in the new thread.....

The idea of a line chart has always been a good indicator for dispalying the change of a variable over a period of time or steps....

The 1st one that I saw was a step vs. difficulty line chart by foxglove here & in the programmers forum.

This can provide the a visual indicator for the general masses... this could be be used in association with "the area under the line" to show the overall difficulty.
tarek
User avatar
tarek
 
Posts: 2699
Joined: 05 January 2006

Postby ravel » Sun Apr 15, 2007 7:11 pm

gsf wrote:there's really no need to list the canonical form as long as posted lists have been cleared of dups offline
Hm, to do that you have to normalize them. At the beginning of the year we only knew a few such hard puzzles, but in the last 2 weeks i saw more than 50 new ones. So i suspect, that we have thousands at the end of the year, a list that you cannot post here. And you would not look at them one by one, so the presentation is not that important.

I would like them to be preserved for several reasons.
- the rating problem: even for my own program i get totally different top lists with different parameters, though all are arguable in some way. They would be a good material to develop other rating systems or to identify properties of very hard puzzles.
- the authorship: it could become very cumbersome next year to check, if a puzzle already has been published.
ravel
 
Posts: 998
Joined: 21 February 2006

Postby gsf » Sun Apr 15, 2007 7:52 pm

ravel wrote:
gsf wrote:there's really no need to list the canonical form as long as posted lists have been cleared of dups offline
Hm, to do that you have to normalize them.

that's what I meant
offline maintain the list as a (<key>,<value>) pair where <key> is the canonical form of the puzzle
and <value> is the original puzzle and other puzzle related info like ratings, label, author, date
sort/uniq on the <key> offline and only post the <value>s
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby JPF » Sun Apr 15, 2007 8:41 pm

ravel wrote:
JPF wrote:There is still the connexion with ravel's thread...
The thread is frozen. I added a link to your ER top list at the top page. Since only these "old" 11+ puzzles are not in your list, you might want to add them:
Code: Select all
Ocean's New Year's present for RW
dml 1/07
Mauricio's non minimal puzzle (62 non isomorphic minimals):


Thanks, I updated the list with the new posted puzzles.

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

Postby coloin » Mon Apr 16, 2007 1:01 pm

So many things to comment on.......
I feel chuffed to be partly responsible for producing these hard puzzles - I hadnt really appreciated the degree of the increase in complexity compared with our previous "hardest"puzzles from 3 months ago.

The development of different approaches to rating programs is fascinating - and I can only admire !

I have re-read RW's post and cant help perhaps commenting on the way it encompasses the solving techniques to enable us potentially develop puzzles which do not have the solving feature and hence are progresssivly difficult. We are closer to understanding how to make hard puzzles.

I will perhaps leave the "unavoidable" set idea for now - although Im convinced that the intersection of these extra large unavoidable sets associated with individual clues contributes to the effect of [correct or incorrect] proposition clues - im not sure how though ! It is possible to pick clues from unavoidables which give a puzzle with a hidden single. I cant envisage applying RWs theory yet !

I was going to leave it there............................................

Until I followed a hunch and "chanced" on these ones

All hard
All from the same grid
All uniquely sharing the same large unavoidable set of 53 clues.....

Code: Select all
1035 ,  1..3....2.9.4...5...6...7...5.9.3.......7.......8...4.7.....6...3...9.8...2.....1 - 10.8
 705 ,  1...8...2.9.4...5...6...7...5.9.3.......7.......8...4.7.....6...3...9.8...2.....1
 845 ,  1.......2.9.4...5...6...7..45.9.3.......7.......8...4.7.....6...3...9.8...2.....1
 654 ,  1.......2.9.4...5...6...7...5.923.......7.......8...4.7.....6...3...9.8...2.....1
 861 ,  1.......2.9.4...5...6...7...5.9.38......7.......8...4.7.....6...3...9.8...2.....1 -  9.4
1532 ,  1.......2.9.4...5...6...7...5.9.3.......74......8...4.7.....6...3...9.8...2.....1 - 11.3 tarek 04/08/2
1228 ,  1.......2.9.4...5...6...7...5.9.3.......7...5...8...4.7.....6...3...9.8...2.....1 - 10.9
1892 ,  1.......2.9.4...5...6...7...5.9.3.......7.......85..4.7.....6...3...9.8...2.....1 - Easter Monster
 584 ,  1.......2.9.4...5...6...7...5.9.3.......7.......8..24.7.....6...3...9.8...2.....1 -  9.2
 980 ,  1.......2.9.4...5...6...7...5.9.3.......7.......8...4.7..5..6...3...9.8...2.....1 - 10.5
 772 ,  1.......2.9.4...5...6...7...5.9.3.......7.......8...4.7...4.6...3...9.8...2.....1
 877 ,  1.......2.9.4...5...6...7...5.9.3.......7.......8...4.7....86...3...9.8...2.....1
1091 ,  1.......2.9.4...5...6...7...5.9.3.......7.......8...4.7.....6...3...9.8...2.3...1 - 10.6

The 10.9 is a new pattern !
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


Also these ones, originating puzzle first
[Edit - this looks to be a repeat of above !]
Code: Select all
1512 ,  1......89.....91.2......4....76......3..4....9....2..5..4.7....5....8.1..6.3..... - 11.3 tarek 4/08/2
1859 ,  1......89.....9..2......45...76......3..4....9....2..5..4.7....5....8.1..6.3..... - 11.4 [Easter Monster]
1195 ,  1......89.....9..2......4....76......3..4....9....2..5..4.7....5....8.1..6.3..5.. - 10.9 -04/16/1b
1076 ,  1......89.....9..2......4....76......3..4.8..9....2..5..4.7....5....8.1..6.3..... - 10.8 -04/16/3

And
Code: Select all
1522 ,  1.......2..34...5..6....7......3..4....8.6.....954.....2....1..7.......6..5.9..8. - 11.3 JPF 04/10
1149 ,  1.......2..34...5..6....7......3..4......6..9..954.....2....1..7.......6..5.9..8. - 10.9 -04/16/4
Last edited by coloin on Tue Apr 17, 2007 6:38 pm, edited 1 time in total.
coloin
 
Posts: 1733
Joined: 05 May 2005

Postby coloin » Tue Apr 17, 2007 9:06 pm

I note ravel has updated his list........

Interestingly the puzzles that I had on my waiting list despite no SE >11 there are some hard puzzles as rated by his method.

I am most grateful, I had almost assumed they were not special and I also presumed that JPF had searched these bases.

However for clarity These are the two runs I did

1.......2.9.4...5...6...7...5.......................4...2...6...3...9.8.7.......1 - 676286 sol.
1.......2.9.4...5...6...7...5.......................4...7...6...3...9.8.2.......1 - 691248 sol.
6.......2.9.4...5...1...7...5.......................4...2...6...3...9.8.7.......1 - 708196 sol.
6.......2.9.4...5...1...7...5.......................4...7...6...3...9.8.2.......1 - 682164 sol.

1.......2.9.4...5...6...7...5.......................4.7.....6...3...9.8...2.....1 - 678104 sol. [ Easter monster & coloin-04/13-1601]
1.......7.9.4...5...6...2...5.......................4.7.....6...3...9.8...2.....1 - 696188 sol.
6.......2.9.4...5...1...7...5.......................4.2.....6...3...9.8...7.....1 - 688096 sol.
6.......2.9.4...5...1...7...5.......................4.7.....6...3...9.8...2.....1 - 685046 sol.

Worringly the suexrat values and SE ratings are fairly low on some of these puzzles - worringly in that there are many puzzles which have been irretrievably discarded !

ravel - I think Tarek ULTRA0209 is the only syymetrical puzzle in your top list !

C
coloin
 
Posts: 1733
Joined: 05 May 2005

Postby JPF » Tue Apr 17, 2007 10:07 pm

coloin wrote:I note ravel has updated his list........

Yes, I noticed that too.
Thanks ravel, again.

But I'm more than puzzled.
Where are we now ?

We know how to easily produce very hard puzzles with SE>10.7 ; thanks notably to m_b_metcalf and to it's strange SE=11.4 "sub-puzzle" coming from our patterns competition.

Apparently, these puzzles are also highly rated by other rating systems (ravel's, gsfr, suexrat)... but... more or less, not always...
and not with the same league table !

Sudoku Explainer is a nice one because it's public and it provides some solution up to a level of difficulty,
but practically impossible to use for puzzles with SE = 10.7+
(I have now a list of more than 100 of such puzzles and I see no reason not to be able to produce at least 15 more every day).

Like ravel, gsf, AW and others I agree that it's time to think about what we are really looking for in term of rating.
A public program (or at least a common methodology) should be set up accordingly to evaluate quickly these very hard puzzles and to find what we are looking for in them.

If not, we will accumulate thousand of puzzles.
and so what ?

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

Postby tarek » Wed Apr 18, 2007 8:10 am

coloin wrote:ravel - I think Tarek ULTRA0209 is the only syymetrical puzzle in your top list !

Thanx for bringing this to my attention coloin.... The thing is, with all my puzzles, there is an attempt to get closer towards symmetry...In this thread I've neglected the ones which are already symmetrical....

However with a minor tweak (columns 4 & 6) the 180 symmetry should turn into 180 & double diagonal symmetries......

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

ULTRA0209B
 8 . . | . . . | . . 5 
 . 6 . | 3 . . | . 1 . 
 . . 7 | . . . | 4 . . 
-------+-------+------
 . 9 . | 1 2 . | . . . 
 . . . | 9 . 4 | . . . 
 . . . | . 3 6 | . 9 . 
-------+-------+------
 . . 4 | . . . | 7 . . 
 . 3 . | . . 1 | . 6 . 
 5 . . | . . . | . . 8

& similar operations to these 3
Code: Select all
tarek ULTRA0024B
1.......4.2...6.9...5...8......98.7....372....3.65......8...5...6.9...2.4.......1
 1 . . | . . . | . . 4 
 . 2 . | . . 6 | . 9 . 
 . . 5 | . . . | 8 . . 
-------+-------+------ 
 . . . | . 9 8 | . 7 .   
 . . . | 3 7 2 | . . .
 . 3 . | 6 5 . | . . . 
-------+-------+------
 . . 8 | . . . | 5 . . 
 . 6 . | 9 . . | . 2 . 
 4 . . | . . . | . . 1 

tarek ULTRA0026B
9.......1.3...4.7...6...2......72.8....853....5.46......2...6...4.7...3.1.......9
 9 . . | . . . | . . 1 
 . 3 . | . . 4 | . 7 . 
 . . 6 | . . . | 2 . . 
-------+-------+------
 . . . | . 7 2 | . 8 . 
 . . . | 8 5 3 | . . . 
 . 5 . | 4 6 . | . . . 
-------+-------+------
 . . 2 | . . . | 6 . . 
 . 4 . | 7 . . | . 3 . 
 1 . . | . . . | . . 9 

tarek ULTRA0208B
1.......9.4.8...3...2...6...7.43.......2.7.......58.7...6...2...8...3.4.9.......1
 1 . . | . . . | . . 9 
 . 4 . | 8 . . | . 3 . 
 . . 2 | . . . | 6 . . 
-------+-------+------
 . 7 . | 4 3 . | . . . 
 . . . | 2 . 7 | . . . 
 . . . | . 5 8 | . 7 . 
-------+-------+------
 . . 6 | . . . | 2 . . 
 . 8 . | . . 3 | . 4 . 
 9 . . | . . . | . . 1

tarek
Last edited by tarek on Wed Apr 18, 2007 10:11 am, edited 1 time in total.
User avatar
tarek
 
Posts: 2699
Joined: 05 January 2006

Postby coloin » Wed Apr 18, 2007 10:15 am

Indeed JPF I agree we have to look at our motivation now.

I think the reason we searched for these puzzles was because we could.......

We were following a long running thread to come up with harder and harder puzzles - until we now have reached the point where we have so many puzzles and no definitive all encompassing rating system.

I think the "Easter Monster" has ticked most of the boxes.......Except perhaps we havnt had a Carcul vv "Easter Monster" showdown yet !

C
coloin
 
Posts: 1733
Joined: 05 May 2005

Postby tarek » Wed Apr 18, 2007 2:33 pm

This is a line chart of "Move vs. ER" of this puzzle until the singles tail:
Code: Select all
..2...6...7.1...8.4.......3.5..9..7....71.........2...3.......4.8..7..5...6...2..

Image

IMO, this method would describe the puzzle's difficulty more accurately than just a simple "Hardest step"

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

PreviousNext

Return to General