Pencilmark Sudoku

Programs which generate, solve, and analyze Sudoku puzzles

Re: Pencilmark Sudoku

Postby dobrichev » Sat Jan 11, 2020 8:26 am

I don't think an aquarium fish released into ocean it will grow sufficiently.

Vanilla hardest puzzles have two orthogonal properties
- they are hard to solve;
- they are special cases of pencilmark-only puzzles.

IMO the second constraint is harder and therefore it is easier to search for hardest pencilmark puzzles from scratch rather from vanilla ones.

Also I think the SE rating isn't adequate for pencilmark puzzles.
At the low difficulties it should rate Naked Singles as zero as it does for direct pencilmarks eliminations.
At the nested guesses level the logarithmic rescaling of the chain lengths is OK, but iterating over large variety of special guesses seems inappropriate even for human solvers.
dobrichev
2016 Supporter
 
Posts: 1779
Joined: 24 May 2010

Re: Pencilmark Sudoku

Postby tdillon » Mon Jan 13, 2020 11:01 am

dobrichev wrote:IMO the second constraint is harder and therefore it is easier to search for hardest pencilmark puzzles from scratch rather from vanilla ones.

That's my sense as well. I experimented both with trying to generate hard pencilmark puzzles starting from hard vanilla ones and with trying to generate low-clue pencilmark puzzles starting from 17-clue vanilla ones. Neither seemed as effective as starting from scratch.

BTW, I've added some newly discovered 87 clue puzzles and also some more really hard puzzles (by minisat backtracking under permutation).

For example, here's a fun one to check out:

Code: Select all
1.3.5.7.91234567891234567891234567891.3.5.78.1.3.567891.34567..123.56789123456789..345.7.9123456..9.234567891234567.9123456789..345...9123456789.2345.7.912345.7891234567891..4.6..9.2.4.6.8912.456.89123456789.23456789123456.8.12345678912.4.678.12345678912.456.89.2.456.89123456789123456789..34567.9..34567.9.23...789123456789123.5678912...6...12.456.8912.45...91234567891.3456.891234.6.89123.5678912...6789123.5.78.12345678912345678912345.78912345678.1234567891234.6789..3....89123...7891.34567..12345678912345678912345678912345678.1.345678....456...1234567891...5678.12345678912.4.6.89.2.4.6.89.2.4...891234..78912345678912345678912345678912.456789123.567891234.6789.234.678912345.789123...78.123456789..345678..23.56789123456789

Code: Select all
|hard                                  |  puzzles/sec|  usec/puzzle|   %no_guess|  guesses/puzzle|
|--------------------------------------|------------:|------------:|-----------:|---------------:|
|minisat_augmented_01                  |         0.0 |43,046,414.5 |       0.0% |   1,081,777.43 |
|fsss2_locked                          |         0.1 |16,669,979.4 |       0.0% |  13,839,251.93 |
|tdoku                                 |         0.1 | 7,575,961.4 |       0.0% |  10,334,598.34 |

Minisat hardness won't always correlate well with ER (minisat can't exploit uniqueness strategies, and it doesn't handle pigeonhole inferences well), but I think it's a safe bet that if a puzzle causes minisat to backtrack a million times then it's pretty darn hard.
Last edited by tdillon on Wed Jan 15, 2020 9:04 pm, edited 1 time in total.
tdillon
 
Posts: 42
Joined: 14 June 2019

Re: Pencilmark Sudoku

Postby m_b_metcalf » Mon Jan 13, 2020 12:06 pm

tdillon wrote: ... and also some more really hard puzzles (by minisat backtracking under permutation).

For example, here's a fun one to check out:

Code: Select all
1.3.5.7.91234567891234567891234567891.3.5.78.1.3.567891.34567..123.56789123456789..345.7.9123456..9.234567891234567.9123456789..345...9123456789.2345.7.912345.7891234567891..4.6..9.2.4.6.8912.456.89123456789.23456789123456.8.12345678912.4.678.12345678912.456.89.2.456.89123456789123456789..34567.9..34567.9.23...789123456789123.5678912...6...12.456.8912.45...91234567891.3456.891234.6.89123.5678912...6789123.5.78.12345678912345678912345.78912345678.1234567891234.6789..3....89123...7891.34567..12345678912345678912345678912345678.1.345678....456...1234567891...5678.12345678912.4.6.89.2.4.6.89.2.4...891234..78912345678912345678912345678912.456789123.567891234.6789.234.678912345.789123...78.123456789..345678..23.56789123456789




Assuming only one solution:

Code: Select all
 1 2 3 4 5 6 7 8 9
 4 5 6 7 8 9 1 2 3
 7 9 8 1 3 2 5 4 6
 2 1 5 8 9 3 6 7 4
 3 6 4 2 7 1 9 5 8
 8 7 9 5 6 4 2 3 1
 5 3 1 6 2 8 4 9 7
 6 8 2 9 4 7 3 1 5
 9 4 7 3 1 5 8 6 2

Total time .59 seconds

Does the fact that your first row is always 1, …, 9 have any effect on solution times?

Regards,

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

Re: Pencilmark Sudoku

Postby tdillon » Mon Jan 13, 2020 4:01 pm

Hi Mike,
m_b_metcalf wrote:Does the fact that your first row is always 1, …, 9 have any effect on solution times?

The benchmark program that I'm using computes average solving times over many random band/stack/row/col/digit permutations of the puzzle, so the initial minlex presentation of the puzzle does not affect its results.That said, if you evaluate the puzzle just once as given, there's a good chance the minlex order might be favorable for a specific solver if the solver's heuristics have been tuned on datasets that were minlexed. I randomize precisely to avoid this.

Also, as I mentioned above, this puzzle might not be as hard as the minisat/fsss2/tdoku numbers suggest. It could just be that the good routes to a solution involve a bunch uniqueness or pigeonhole-based inferences, even if they're not that hard.

Sounds like you have an interesting solver! I'd be happy to integrate it with my benchmark program if the source is available somewhere.

Tom
tdillon
 
Posts: 42
Joined: 14 June 2019

Re: Pencilmark Sudoku

Postby dobrichev » Mon Jan 13, 2020 4:35 pm

Hi Tom,

Congratulations for the 87s.
Were they much much difficult to find than 88s?

The posted hard puzzle is a record. It has backdoor of size 6 in singles + locked candidates. The hardest so far have BD 6 in singles (Tarek's hardest) but BD 4 in singles + locked. From my collection hardest are BD 4 in singles + locked too.

So that a brute force solver needs 6 lucky nested guesses, and much more if not so lucky.

My solver said 17 seconds. Shame for the solver and bravo to the puzzle creator ;)
dobrichev
2016 Supporter
 
Posts: 1779
Joined: 24 May 2010

Re: Pencilmark Sudoku

Postby dobrichev » Mon Jan 13, 2020 4:43 pm

Hi Mike,

Did you cracked the first solution in 0.59 seconds exploiting minlex or your solver just reported the first solution so fast?

I am curious up to what degree your solver can solve it "logically".
Is the puzzle crackable by some not very exotic technique or requires series of nested guesses on top of your techniques zoo?
dobrichev
2016 Supporter
 
Posts: 1779
Joined: 24 May 2010

Re: Pencilmark Sudoku

Postby m_b_metcalf » Mon Jan 13, 2020 5:41 pm

Tom and Mladen,
No magic here. The initial 'logic' part of my solver finds not a single elimination. My crude brute-force solver then finds the first, and only, solution quickly because the first row corresponds straightaway to its starting point. If I ask it to find anymore solutions, it goes into hyperspace. I don't think, Tom, that my program is of any interest for your test set-up (aside from the fact that it's written in Modern Fortran).

Regards, and congratulations on your record-breaker,

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

Re: Pencilmark Sudoku

Postby tdillon » Mon Jan 13, 2020 5:45 pm

dobrichev wrote:Hi Tom,
Were they much much difficult to find than 88s?

It took around 400 core-hours to find the first 87 starting from a large set of 88's and 89's. This is definitely longer than it took to find the first 88, but I didn't keep stats in a way that helps make a quantitative comparision.
tdillon
 
Posts: 42
Joined: 14 June 2019

Re: Pencilmark Sudoku

Postby dobrichev » Mon Jan 13, 2020 6:46 pm

m_b_metcalf wrote:No magic here.

Likely you switch to backtracking really as a last resort :)

tdillon wrote:It took around 400 core-hours.

To me this is a sign that even 86s can exist. Unless the collection of the 88s+ already took tens thousands of cpu hours.
dobrichev
2016 Supporter
 
Posts: 1779
Joined: 24 May 2010

Re: Pencilmark Sudoku

Postby tarek » Mon Jan 13, 2020 10:51 pm

Well done for breaking all the records Tom. I'm hopeful that this would trigger a way to crack these tough puzzles in a logical way.

Sukaku Explainer in the current form - as Mladen mentioned - is just not up to the task but it comes close!

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

Re: Pencilmark Sudoku

Postby tdillon » Mon Jan 13, 2020 11:50 pm

dobrichev wrote:The posted hard puzzle is a record. It has backdoor of size 6 in singles + locked candidates.

Of the 2537 puzzles currently in minisat_bt_100k+ quite a few are BD6 in singles + locked candidates. In singles only there are a bunch that are BD7+. Here are the distributions:

Code: Select all
 BD       S+LC        S
---       ----     ----
  4        138        8
  5       2101      839
  6        298     1638
  7+         0       52

tdillon
 
Posts: 42
Joined: 14 June 2019

Re: Pencilmark Sudoku

Postby creint » Tue Jan 14, 2020 9:26 pm

Timings using Gurobi solver for the puzzle:
1.3.5.7.91234567891234567891234567891.3.5.78.1.3.567891.34567..123.56789123456789..345.7.9123456..9.234567891234567.9123456789..345...9123456789.2345.7.912345.7891234567891..4.6..9.2.4.6.8912.456.89123456789.23456789123456.8.12345678912.4.678.12345678912.456.89.2.456.89123456789123456789..34567.9..34567.9.23...789123456789123.5678912...6...12.456.8912.45...91234567891.3456.891234.6.89123.5678912...6789123.5.78.12345678912345678912345.78912345678.1234567891234.6789..3....89123...7891.34567..12345678912345678912345678912345678.1.345678....456...1234567891...5678.12345678912.4.6.89.2.4.6.89.2.4...891234..78912345678912345678912345678912.456789123.567891234.6789.234.678912345.789123...78.123456789..345678..23.56789123456789


0.25 seconds first solution
0.9 seconds solution + single solution check
creint
 
Posts: 168
Joined: 20 January 2018

Re: Pencilmark Sudoku

Postby tdillon » Mon Jan 20, 2020 10:09 pm

creint wrote:Timings using Gurobi solver for the puzzle:
0.25 seconds first solution
0.9 seconds solution + single solution check

Berkson's paradox at work! While there's a decent positive correlation between minisat-hardness and gurobi-hardness, thanks to differences in approach and heuristics there is still considerable independent variation. As a result, if we select puzzles with the most extreme minisat-hardness they're often not among the puzzles with the most extreme gurobi-hardness.

For most of the datasets I've tested gurobi is slower than minisat, but its very differences might make it a nice addition to a blended solver hardness measure. e.g. maybe a geometric mean of minisat, gurobi, fsss2, tdoku.
tdillon
 
Posts: 42
Joined: 14 June 2019

Previous

Return to Software