m_b_metcalf wrote:I processed all of these (Tom's). Most are fairly easy.
Indeed ... I haven't looked at them from the perspective of human-centric rating, but even with the simple techniques implemented in the solvers below many of the 90 clue puzzles are solved without any guessing:
- Code: Select all
|low_clue/90_clue | puzzles/sec| usec/puzzle| %no_guess|guesses/puzzle|
|-----------------------|-----------:|------------:|-----------:|-------------:|
|minisat_augmented_01 | 1,091.8 | 915.9 | 0.0% | 100.98 |
|_tdev_dpll_triad_scc_i | 847.9 | 1,179.4 | 38.1% | 12.69 |
|fsss2_locked | 2,168.9 | 461.1 | 0.0% | 619.49 |
|tdoku | 137,498.8 | 7.3 | 15.0% | 4.83 |
I think it's almost axiomatic that puzzles approaching minimal cluefulness also tend to be easy. In such puzzles each clue needs to pull its weight by ruling out a large independent swath of the space, and this is at odds with the complex clue interactions that contribute to puzzle hardness.
Of course, "easy" depends on having the right tool kit. Vanilla 17 clue Sudoku are easy if a solver can exploit hidden singles, but hard if it can't. Something similar is operating with Mladen's previously posted list of low clue killers. They are easy for Minisat, but hard and extremely sensitive to heuristics for other solvers that can't quite connect the dots:
- Code: Select all
|dobrichev_93_clue_hard | puzzles/sec| usec/puzzle| %no_guess|guesses/puzzle|
|-----------------------|-----------:|------------:|-----------:|-------------:|
|minisat_augmented_01 | 755.0 | 1,324.5 | 0.0% | 129.26 |
|_tdev_dpll_triad_scc_i | 0.0 |99,114,673.8 | 0.0% | 1,560,519.33 |
|fsss2_locked | 0.5 | 1,898,407.2 | 0.0% | 1,815,772.12 |
|tdoku | 0.1 |17,486,087.6 | 0.0% |34,116,990.40 |
The 90 and 91 clue puzzles I found were the result of 60 processes running for 24 hours on a Threadripper 2990WX. I just finished another 24 hour search, but this time looking for hard puzzles instead of low-clue ones, where "hard" is defined as "causing lots of backtracking for Minisat averaged over 10 random permutations of the puzzle".
The resulting puzzles are pretty hard for all the solvers I've tested:
- Code: Select all
|hard.gt35 | puzzles/sec| usec/puzzle| %no_guess|guesses/puzzle|
|-----------------------|-----------:|------------:|-----------:|-------------:|
|minisat_augmented_01 | 0.6 | 1,798,868.2 | 0.0% | 37,195.21 |
|_tdev_dpll_triad_scc_i | 0.0 |27,714,685.4 | 0.0% | 255,830.55 |
|fsss2_locked | 1.8 | 553,853.5 | 0.0% | 320,814.63 |
|tdoku | 3.7 | 267,548.8 | 0.0% | 293,757.68 |
I'm curious what their SE ratings might be.
. If Mini-sat struggled with these then I suspect they would be very difficult. The way tdillon describes the process reminds me of dukosu's Suexrat9.