Rating rules / Puzzles. Ordering the rules

Advanced methods and approaches for solving Sudoku puzzles

Postby gsf » Sun May 18, 2008 11:44 am

I just posted q2-taxonomy.dat with schema
Code: Select all
#!sudoku -c5,Q2,Q1,ER,XR,puzzle,label,Qtime,ERtime,Qstats,stats

sorted by Q2, high to low

let me know of hard puzzles that should be added

I also reposted my solver with a tweak to the Q2 rating for easier puzzles that had previously produced a q2 rating of 0
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby ronk » Sun May 18, 2008 12:04 pm

gsf, thanks for publishing the q2-taxonomy.

gsf wrote:let me know of hard puzzles that should be added

What is/are the current difficulty rating(s) required for addition:?:

Similar to gfroyle's "submission service" for 17s, have you considered one for difficult puzzles:?:

If you do establish one, batch submission would be desirable.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby tarek » Sun May 18, 2008 12:37 pm

ronk wrote:Similar to gfroyle's "submission service" for 17s, have you considered one for difficult puzzles:?:

If you do establish one, batch submission would be desirable.

That is an excellent suggestion:D:idea:

gsf,
Thanks for the effort you've put into this .... I just opened the file as a spreadsheet & sorted them according to (Q1-Q2) .....

There is a huge number of puzzles that have fallen from grace, that must be due to the added locked candidates.

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

Postby champagne » Sun May 18, 2008 1:50 pm

gsf wrote:
let me know of hard puzzles that should be added


I made a quick check with my own list of "hardest".

It seems that the hardest coming from ocean and dml are not here, but may be my pattern is not the standard of your file.

(or may-be there is other reasons not to have them).

No surprise, the last from coloin are missing as well, but this is normal
champagne
2017 Supporter
 
Posts: 5680
Joined: 02 August 2007
Location: France Brittany

Postby gsf » Sun May 18, 2008 4:36 pm

ronk wrote:gsf, thanks for publishing the q2-taxonomy.

gsf wrote:let me know of hard puzzles that should be added

What is/are the current difficulty rating(s) required for addition:?:

for a taxonomy I'm looking for a range of ratings from highest to lowest
more inclined to acces dup ratings for the highest ones since that might expand our understaniding of hardest
Similar to gfroyle's "submission service" for 17s, have you considered one for difficult puzzles:?:
If you do establish one, batch submission would be desirable.

good idea
will ruminate on that
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby denis_berthier » Mon May 19, 2008 7:33 am

tarek wrote:There is a huge number of puzzles that have fallen from grace, that must be due to the added locked candidates.

Strangely enough, there's also a lot of puzzles with Q2 > Q1.

gsf, does the Q2 rating use another scale than the Q1?

Anyway, here are the correlation results for this new list (8152 puzzles).

1) For the whole list
Q2 vs Q1 : 0.41
At first sight, I was very surprised that the correlation is so weak. On second thoughts, I remembered that:
- 46% of the minimal puzzles can be solved with Singles
- 77,7% can be solved with Singles + elementary interactions
One can therefore understand that adding elementary interactions to prune the search tree can change it so drastically for all the puzzles.

2) For the sublist of the (4849) puzzles for which the ER is computed:

Q2 vs Q1 : 0.67 (I have no explanation why the correlation is higher for this sublist - maybe, gsf could explain it based on the reasons why he didn't compute the ER for the other puzzles and which kind of new bias this introduced)

Q1 vs ER : 0.41
Q2 vs ER : 0.40

log(Q2) vs ER : 0.67
log(Q1) vs ER : 0.72

which shows that Q2 behaves globally as Q1 wrt ER.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby coloin » Mon May 19, 2008 1:21 pm

Firstly, in response to tarek I only started searching for new hardest - my computor was inactive and I had a little idea - which once running wouldnt be stopped ! The -q2 is another rating program which will enhance the pick up rate - I am at the mercy of the output of all these programs. The attempts at correlation have to be aplauded.

Previously new puzzles were made rather quickly with a {-1+1} method. A more directed search with a {-2+2] can be implemeted, which much longer, but 25 21-puzzles gives around 300k new puzzles. I started from a single puzzle and gradually found harder and harder puzzles. After about 7 rounds of creaming off the hardest 50 puzzles each time out popped GN.

The top 50 puzzles each time will be extremely biased - I only chose the SP [Si vous plait:) ] because it was the first puzzle to have a higher sxt, and it didnt have an inserted single as in BM.

Im loathe to complicate matters to post a ream of probably useless puzzles, although I will post one which has 5 single clues and then has a massive apparent difficulty, we might learn from this puzzle.

I am also loathe to post random morphic versions of puzzles. My version of GN shows the puzzle in all its flawed symmetry. I wonder if it is worth suggesting a furthur canonicalizing pattern.

The minlex patterns with an ordered row1 or box1 are difficult to obscure from someone trying to solve or look for patterns. I have no doubt Steve K would not have found his SK loop if the puzzle had not been presented with a symmetrical morph.

Finally, I'm perhaps thinking that a search for a "hardest puzzle" might be directed at puzzles with more than 21 clues - possibly. There are perhaps 100 times more puzzles to chose from, the reason we havn't found them is because of this fact ! There are certainly hard puzzles around with 22+ clues.

C
coloin
 
Posts: 1637
Joined: 05 May 2005

Postby gsf » Mon May 19, 2008 3:50 pm

denis_berthier wrote:
tarek wrote:There is a huge number of puzzles that have fallen from grace, that must be due to the added locked candidates.

Strangely enough, there's also a lot of puzzles with Q2 > Q1.

gsf, does the Q2 rating use another scale than the Q1?

a different scale
Anyway, here are the correlation results for this new list (8152 puzzles).

1) For the whole list
Q2 vs Q1 : 0.41
At first sight, I was very surprised that the correlation is so weak. On second thoughts, I remembered that:
- 46% of the minimal puzzles can be solved with Singles
- 77,7% can be solved with Singles + elementary interactions
One can therefore understand that adding elementary interactions to prune the search tree can change it so drastically for all the puzzles.

that's it
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

SER rating

Postby denis_berthier » Sun Aug 24, 2008 1:35 am


Is anyone aware of any change in the definition of the SER rating?

I've always read that the SER of EasterMonster was 11.4 - but I had never tried to compute it.

As I was computing the SER of several puzzles, I found 11.5 for SilverPlate - more than EM. I therefore checked EM - and I got 11.6 !!!

I'm using version 12.0.0 of SE with command line:
java -cp SudokuExplainer.jar diuf.sudoku.test.serate --format=%r 1.......2.9.4...5...6...7...5.9.3.......7.......85..4.7.....6...3...9.8...2.....1
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: SER rating

Postby tarek » Sun Aug 24, 2008 2:31 am

denis_berthier wrote:
Is anyone aware of any change in the definition of the SER rating?
The change occured when SE was updated from version 1.2 (SE12) to version 1.2.1 (SE121).

Nicolas Juillera describing the changes in his program wrote:Changed ratings for nested chains. Nesting level has now more impact on rating.
(Basically, this only adds 0.2 to the rating of the rare Sudokus with at least a "xxx Forcing Chain (+Multiple Forcing Chain)" and 0.4 to those with "xxx Forcing Chain (+Dynamic Forcing Chain)".)
This effictively changed EM rating from 11.4 to 11.6, it also changed GN rating from 11.5 to 11.9

Serate 1.2.1.2 (the one which you are using) is a modified SE121 for use in the Patterns game, it still has the exact capabilities of SE121 & therefore the same changes to rating.

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

Re: SER rating

Postby denis_berthier » Sun Aug 24, 2008 2:44 am

tarek,

thanks for your answer.

Then I must add:

all the results I've reported in this thread are based on the new SE rating.

As the range of puzzles used in these results were below SER 9, I don't think that changes anything.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby coloin » Tue Aug 26, 2008 9:40 am

I dont know how much credance anyone gives to SE ratings [?>8.0] these days.There are more and more examples of false high ratings.

An upgrade would be a difficult project.

Solving methods - such as using double [or triple!] proposition clues - which strmcker does are to be respected.

I note the arguements within "Eureka" have stopped !...........has it suddenly dawned on them that it is alright to make assumptions ?

I have always simplisticly viewed all techniques as assumptive.

for example..... the logic behind a hidden single - if I put a 3 in here - the grid will be invalid therefore it cant be a 3 ................is no different from an XY-wing or a long chain for that matter. The only difference is that it is easier to visualize a hidden single than a multiple dynamic forcing chain - whatever that is !

C
coloin
 
Posts: 1637
Joined: 05 May 2005

Postby denis_berthier » Tue Aug 26, 2008 10:00 am

coloin wrote:I dont know how much credance anyone gives to SE ratings [?>8.0] these days.There are more and more examples of false high ratings.
An upgrade would be a difficult project.

"Dynamic" chains (more or less equivalent to T&E) introduce a logical discontinuity which is hidden by SER.

We need ratings.
There doesn't seem to be any universal rating. A rating can only be based on a specific set of resolution rules. The set used in SE may be a little outdated.
As there must be different ratings, we need methods for comparing them.
It is impossible to compare different ratings on a puzzle by puzzle basis.
The comparison can only be statistical.
Unfortunately for high ratings, they correspond to very rare puzzles and we reach the limits of elementary statistics.


coloin wrote:I note the arguements within "Eureka" have stopped !...........has it suddenly dawned on them that it is alright to make assumptions ?
I have always simplisticly viewed all techniques as assumptive.

I've always thought we need not waste our time with undefined words such as "assumptive". Just leave this to professional word fighters.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby tarek » Tue Aug 26, 2008 11:33 am

I also doubt Rating based on Sudoku Explainer for the most difficult puzzles.

I would favour a rating based on a defined backdoor set & size ... That is a personal opinion obviously....

Only 2 puzzles to date have managed to have a backdoor size 2 for the large set of techniques in gsf's solver arsenal ... these 2 happen to be in top tier of difficult puzzles.

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

Postby champagne » Tue Aug 26, 2008 2:19 pm

Coloin Wrote

I don’t know how much credence anyone gives to SE ratings [?>8.0] these days. There are more and more examples of false high ratings.



I fully agree. Just to give one more example,

Code: Select all
012000304400010000000004002004000560000070000083000200800700000000040009906000480_277H

This is one of the recent puzzles proposed by JPF on a French forum in the range 9 to 9.5 SE rating.

This puzzle is solved (among other possibilities) in once with a very simple net clearing 9r6c8

Code: Select all
 []3r5c8 - 4r5c8 = 4r6c8 - 9r6c8 
 []3r7c8 – 2r7c8 = 2r8c8 – 2r8c12 = 2r9c2 – 7r9c2 = 7r9c9 – 7r46c9 = 7r6c8 - 9r6c8   
 []3r8c8 – 3r8c12 = 3c9c2 – 7r9c2 ….


I have doubts that this worth’s a rating over 9.

On top of it, nothing has been done to account the fact that any puzzle having the SK loop is “relatively” easy to solve. For me, by far, SP and GN are the hardest known puzzles.

Hand players show that they are more and more skill finding these very short solutions.
I am on the way to do with my solver part of what they can achieve, but what they are doing is very impressive.

Summertime is behind us, I should be soon in a position to do a summary of my research showing again a poor correlation with the SE rating


Champagne
champagne
2017 Supporter
 
Posts: 5680
Joined: 02 August 2007
Location: France Brittany

PreviousNext

Return to Advanced solving techniques