The New Sudoku Players' Forum

[dobrichev]

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.

[tdillon]

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.

[m_b_metcalf]

... 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

[tdillon]

Hi Mike,

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

[dobrichev]

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]

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?

[m_b_metcalf]

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

[tdillon]

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.

[dobrichev]

No magic here.

Likely you switch to backtracking really as a last resort

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.

[tarek]

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

[tdillon]

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



[creint]

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

[tdillon]

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]

To me this is a sign that even 86s can exist. Unless the collection of the 88s+ already took tens thousands of cpu hours.

With an idle machine begging for employment in the past few weeks I've set it loose looking for more low-clue pencilmark sudoku.

Starting from the previous collection of 25k 87's after about 20k core-hours I now have around 7 million distinct 87's spread across ~300 solution grids.

Further, I've finally come across a cluster of 86-clue puzzles! Here are the counts I have so far and grids they are associated with:

Code: Select all

   2946 123456789456789132789231546231865974675194328894372651347618295518927463962543817
   2766 123456789456789132789231546278693451395174268641825973532948617817562394964317825
   2471 123456789456789123789132564295843617318267495647915238571698342862374951934521876
    346 123456789456789132789231546265347918378195624941862375517924863634518297892673451


And here is an example:

Code: Select all

123456789.2345678...3456...123456..912345.7.9123456.89123456.89123456789123456.89.234..78..2345678...34.678.123456789123456789123456.89123456789.234.678..2345678..2345678...345678..23456789123456..91234567.9123456.8912345678912.4.67891234567891234567891234567891.34.6..91234.6...1234.678.1234.6.8.12345678912.4.....12345678.1.3456789..34567891.34567891234567891234567891234567891234567891234567891234567891.3456789..345678.1.345678912345678912345678912345678912.456789123456789123456789123456789.234567891234567891234567.9123456789123456.89123456789123456789123456789123456789.2.456789..3456789123456789.23456789123456789123456789123456789.23456789123456789.234567891.3456789123456789123456789123456.891234567891234.678.123456789


Can there be 85's? ...

[m_b_metcalf]

And here is an example:

Well done, Tom. Solved with pairs and pointing:

Hidden Text: Show

Code: Select all

  1  2  4  3  5  6  8  7  9
  3  5  6  7  8  9  1  2  4
  7  8  9  4  1  2  5  6  3
  2  1  3  6  7  8  9  4  5
  6  9  7  5  4  1  3  8  2
  5  4  8  2  9  3  6  1  7
  8  3  2  9  6  4  7  5  1
  4  6  5  1  3  7  2  9  8
  9  7  1  8  2  5  4  3  6

Mike