The New Sudoku Players' Forum

[pollock_mania]

Hi folks,

Before I begin, I'm not plugging commercial software nor do I have my site set up with ads for revenue. This is just to get the word out there about a convenient, no-download solver that also works offline, and to potentially solicit code contributions from the open-source community.

So my solver is 100% javascript, with the CSS+HTML+Javascript inside a single HTML file so that you can save it and use the solver offline. Being 100% Javascript, it's also open-source and licensed under the GPL.

There's also a quantitative instance "hardness" ranker, which is based on the following logic:
1. If an instance is solvable purely with logic, it's difficulty is 0.
2. For the portion of the board that CANNOT be solved by logic, the difficulty is the log of the expected search tree size.

This gives an exponential scale for ranking Sudoku instances from the perspective of computer solvability.

I'd like to encourage you all to check it out, distribute the code (under GPL terms of course) and as always, I am more than open to suggested enhancements or code contributions.

http://compbio.cs.uic.edu/~mayank/fapanosss.html

Thanks,
-Mayank

[tarek]

Welcome Mayank,

1. What is the logic used by your solver for solving puzzles logically ?
2. AI Escargo is definitely NOT the hardest sudoku puzzle
3. have you tried the following as a test case?

Code: Select all

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

tarek

[EDIT: Reposted the original form of the puzzle]

[pollock_mania]

Hi Tarek,

Thanks for that instance! From a computational point of view, it doesn't seem harder than Al Escargot. My quantiative ranking of Silver Plate is 96.01, which is less than Al Escargot's 96.92 (remember, it's an exponential scale). This seems to be confirmed by the fact that the solver finds a solution in about 45 seconds, which sits where you'd expect it for an instance of that difficulty.

As for the techniques used to solve by logic, it's plain and simple constraint satisfaction with iterative propagation, i.e. fill in what can be filled in, update the constraints, repeat as necessary. After no "logic-only" squares remain, it starts on the search tree.

I've taken the liberty of putting up Silver Plate as a test case -- please let me know if I should change the citation.

Thanks,

-Mayank

[tarek]

I've taken the liberty of putting up Silver Plate as a test case -- please let me know if I should change the citation.

I'm sure that coloin would be delighted to know that it is there.....

As for hardest puzzles .... There has been an ongoing debate about which puzzle is the hardest .....

The hardest Sudoku thread on this forum.
The Algrithmics of sudoku topic in wikipedia lists the most difficult puzzles up to March 2008 according to several rating programs used by the users of this forum.

I'm not sure how your SEARCH TREE works, several rating algorithms use singles as their backbone (q1,SX9,SXT) .... This one rates highly in all of the 3 (again by coloin)

Code: Select all

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

Good luck,

tarek

[Edit: Reposted the original form of the puzzle

[coloin]

Not being able to program a proverbial "sausage" I welcome a new solver rater program.

I have always thought that the time for a computor to "guess" or "frontrack a solution was a good index of complexity.

But the problem with rating is the subjective nature of the whole issue - as you probably know.

For the portion of the board that CANNOT be solved by logic

I am of the opinion that all puzzles can be solved by "logic"

Have you thought about solving methods which envolve proposition pairs and beyond ?

Locating which "correct/incorrect proposition pair" is the best at "crushing" the puzzle is one which intuitive solvers are better at than computors.

Number of proposition pairs in a hard 21 clue puzzle ~ [60*3]*[59*3} / 2 ~ 15000 pairs

Ususally a bivalue cell or bi-local pair of cells in a box is favoured.

Hard puzzles tend to have fewer of these, and it is difficult to see the constraint induced by the incorrect clues [long chain]

I suppose this is equivalent to a "search tree" in many ways.

But what if you strike lucky and chose a correct clue early on - has this been factored ? IOW is there consistancy over a series of isomorphic versions of the same puzzle.

tarek - you are quoting minlex isomorphs of puplished puzzles - this is going to confuse somebody sometime - and will distort things if the computor or solver decides that r1c1 is a 1 !

PS despite this Platinum Blonde rates at 99.89 on my pc

C

[tarek]

tarek - you are quoting minlex isomorphs of puplished puzzles - this is going to confuse somebody sometime - and will distort things if the computor or solver decides that r1c1 is a 1 !

I copied & pasted them directly from the hardest puzzles thread ..... If you would kindly post or send me the original form, I would then edit my previous posts ....

tarek

[coloin]

No worries
Here are both versions of a fairly hard list list !

Code: Select all

Cloudy Bay      #1.........2.4...6...3...5.1.4..86.......49.8....2.....5.7...3...6.9...4.........7
Bronze Medalian #1.......7.2.4...6...3...5...9..82.......9..8....6..4....5...1...6.8...2.7....3...
Silver Plate    #1.......7.2.4...6...3...5...9..4........62.4....9..8....5.....3.6.2...8.7....1...
Platinum Blonde #.......12........3..23..4....18....5.6..7.8.......9.....85.....9...4.5..47...6...
Tungston Rod    #........7.2.4...6.1.....5...9...2.4....8..6..6..9.......5..3....3..8..2.7....4..1
Golden Nugget   #.......39.....1..5..3.5.8....8.9...6.7...2...1..4.......9.8..5..2....6..4..7.....
dukdiamond1     #1.......2.2.....6...34..5.....8.5.....8.3.9.....9.4.....5..34...7.....1.6.......7
dukdiamond2     #1.......2.2.....6...34..5.....8.5.....8.3.9.....9.4.....53..4...6......77......1.
weekender2      #..1.....7.2..4..6.3.....5...9.4.6.......92.4.......8....7..3....6..2..8.5.......1
weekender1      #........91......35..9.3.8....3.5...67....2......4.......6.8..9..2.7..6..4.....1.. 


Rating          -q2                                  sx9        sxt         SE121                 
Cloudy Bay      # 45364 FNBP C21.m/M2.4.8200         #3924      #2363       #                     
Bronze Medalian # 98041 FNBP C21.m/M2.8.5740         #3298      #2052       #                     
Silver Plate    # 98036 FNBP C21.m/M2.1.314928       #3316      #2164       #                     
Platinum Blonde # 99551 FNBP C21.m/M3.389.1366       #5059      #2095       #                     
Tungston Rod    # 99307 FNBP C21.m/M3.310.1714       #2950      #1510       #                     
Golden Nugget   # 99220 FNBP C21.m/M2.1.164025       #3639      #2175       #11.9                 
dukdiamond1     # 97726 FNBP C21.m/S2.p/M3.535.993   #4181      #1988       #                     
dukdiamond2     # 97767 FNBP C21.m/M2.3.30618        #3415      #2151       #                     
weekender2      # 98798 FNBP C21.m/M2.1.170586       #2274      #1557       #                     
weekender1      # 98824 FNBP C21.m/M3.108.4920       #3806      #2178       # 

Canonical versions for reference

Cloudy Bay      #020050000007100006090003000006700800030002000900005000000000407004600010000000608#
Bronze Medalian #100400080000009200000030005000000900070800040006020003004700060710000000800005000#
Silver Plate    #100006000050700003009020000040500300000090050000000074070800040600000800002001000#
Platinum Blonde #003050009400100000080007000030005008000030920000000060005060002700004000810000000#
Tungston Rod    #020000700006080100700003004000060000300005010008200000005000090000500040900001300#
Golden Nugget   #020000700400080030009100000000005003000000064600030800005900000800040007010002000#
dukdiamond1     #020400009000080030000003100000005800009200004000010050062000000074000000900600007#
dukdiamond2     #000000780007100006000000150200030000030004000008500600006800500040090000900002000#
weekender2      #000006080000100200090070004000008600300040005005200000030000000740000010900030007#
weekender1      #020006700006000000708010000040500030010090000600004200004007800000000090000030005#

Any chance of a paste function for this rater program ?

C

[Pat]

As for the techniques used to solve by logic, it's plain and simple constraint satisfaction with iterative propagation, i.e. fill in what can be filled in, update the constraints, repeat as necessary. After no "logic-only" squares remain, it starts on the search tree.

and when you say "constraint satisfaction",
exactly which constraints do you mean?

looking at your "Hard" test-case -- which you describe as "Mostly logic, some brute force" --

Code: Select all

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



-- after "hidden singles",
it needs just one "naked single" (r4c4)

may i infer that your only logic is "hidden singles" ??

[coloin]

The Instance difficulty is not consistant with equivalent versions of the same puzzle.

Try both versions of SP

This explains the false positive rating of the El Etana puzzle perhaps.

But an average figure for a larger number of puzzle versions might be more significant. This is what sxt/sx9 does.

C

[pollock_mania]

I am of the opinion that all puzzles can be solved by "logic"

I would agree, but in my context, I meant "logic" as not involving guessing of any kind.

Have you thought about solving methods which envolve proposition pairs and beyond ?

This is a very interesting idea. The way I have it right now effectively means that cells with the lowest number of possibilities are tried first. I also tried a randomized order, but as one might imagine it didn't turn out very well.

I suppose this is equivalent to a "search tree" in many ways.

Yes, I think it's almost completely equivalent.

But what if you strike lucky and chose a correct clue early on - has this been factored ? IOW is there consistancy over a series of isomorphic versions of the same puzzle.

This should be factored into the tree, and isomorphs of the same puzzle should rank identically and take the same amount of time to solve (theoretically).

PS despite this Platinum Blonde rates at 99.89 on my pc

Now that IS impressive.

Thanks for your post (and the later one), it gives me some ideas -- namely an iterative combination of guessing and naked 1s might be more efficient for the "tricky" puzzles, although I don't know how well Javascript will handle the memory management for such a program. Worth a try though.

and when you say "constraint satisfaction",
exactly which constraints do you mean? may i infer that your only logic is "hidden singles" ??

Absolutely correct, although this is the first time I've heard the term "naked singles".

The Instance difficulty is not consistant with equivalent versions of the same puzzle.

This is troubling. My guess is that it might be an implementation issue, but in theory it should be easy to calculate the rating: (1) after naked singles, calculate all consistent possibilities for each cell, (2) the size of the search tree is the product of the number of possibilities for each cell. Instead, sum the logarithms. (3) This should hold consistent for isomorphs of the same puzzle.

[coloin]

It doesnt.

try it on the two versions of Silver Plate

C