The New Sudoku Players' Forum

[m_b_metcalf]

A better comparison would be the 206 16x16 puzzles posted elsewhere on this forum.

Could you kindly provide a link to these?

Thanks.

[rjamil]

Hi Mike,

A better comparison would be the 206 16x16 puzzles posted elsewhere on this forum.

Could you kindly provide a link to these?

Thanks.

I think creint refers to this list.

R. Jamil

[m_b_metcalf]

I think creint refers to this list.

Many thanks. Some harder ones in that list than in the Sukaku one, I must say.

[tdillon]

But I still maintain that 9 is the easiest, it can be solved with naked pairs and pointing. In general, apart from basic logic techniques, many candidates in these puzzles can be eliminated by simple contradiction. None needed brute force (unlike Mladen's nightmares).

The puzzles on my list were just the first 100 from a process of random generation, random minimization, and filtering for cases where the solver did a certain amount of backtracking during minimization. They're not necessarily hard by usual measures, or even by the measure of whether the generating solver does a lot of backtracking on the final puzzle. I thought they were interesting because as a group they trigger so much backtracking for fsss2 and tdoku, while not presenting a problem at all for minisat or the scc solver.

I guess it's obvious that solver performance will be more sensitive to heuristics and forward inference capabilities when exploring the larger search space of pencilmark Sudoku. The behavior on this example and on Mladen's killers just drove home for me how large this sensitivity can be.

Another way to illustrate the sensitivity is to look at the number of backtracks different solvers do when given random band/stack/row/col/digit permutations of the same puzzle. Taking 1000 permutations of the first puzzle on my list we have:

Code: Select all

solver                    mean(log(bt)) sdev(log(bt))
------------------------   -----------  -------------
minisat_minimal_01             18.583       0.406      // 1+ digits/cell; no digit twice in a unit
minisat_natural_01             17.420       0.710      // exactly 1 digit/cell; no digit twice in a unit
minisat_complete_01             6.135       0.289      //   +hidden_singles
minisat_augmented_01            5.785       0.227      //   +hidden_singles,locked_candidates
_tdev_dpll_triad               17.735       1.960      // hidden_singles,locked_candidates,cardinality
_tdev_dpll_triad_scc_i         16.357       1.431      //   +scc_inference
_tdev_dpll_triad_scc_h          5.599       0.104      //   +scc_heuristic
_tdev_dpll_triad_scc_ih         5.577       0.240      //   +scc_inference,scc_heuristic
tdoku                          10.225       3.134      // hidden_singles,locked_candidates,cardinality


If minisat is given weak forward inference in the form of a representation that requires it to learn pigeonhole inferences, it does tens of thousands of times as much backtracking as it does with a better representation (for regular sudoku this difference is more like 5-10x).

If _tdev_dpll_triad operates without the benefit of strong scc-based variable selection heuristics, it also does tens of thousands of times as much backtracking as it does with better heuristics (for regular sudoku this difference is more like 3x at most).

Tdoku operates with the same forward inference capabilities as _tdev_dpll_triad, but it has different default heuristics (better apparently than the _tdev_dpll_triad default, but worse than the scc heuristics). Thanks to the high variance, in the experiment over 1000 permutations of this puzzle the median number of backtracks was 19497, but the minimum was 16 and the maximum was 4374072.

[Mathimagics]

I have managed to produce a variant-mode version of Mladen's PencilMarkSudoku. (v1.1).

My existing (fsss2-based) solver dSolve can already solve most common variants, and from pencilmarks input, but in order to do the really clever things, such as producing minimal pencilmark puzzles, I thought it best to modify PencilMarkSudoku separately so that its fsss2.cpp module was also able to work in variant modes.

It looks like I got it right, and I can now give a verified example of a minimal SudokuP pencilmark puzzle. It has 657 candidates.

Code: Select all

+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+
| 123456789 | 245       | 123456789 | 4         | 45        | 123456789 | 123456789 | 123456789 | 123456789 |
| 123456789 | 123456789 | 123456789 | 123456789 | 123456789 | 123456789 | 1         | 137       | 123456789 |
| 123456789 | 123456789 | 123456789 | 123456789 | 123456789 | 123456789 | 123456789 | 1367      | 123456789 |
+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+
| 123456789 | 123456789 | 123456789 | 123456789 | 259       | 123456789 | 123456789 | 123456789 | 123456789 |
| 123456789 | 123456789 | 123456789 | 123456789 | 123456789 | 123456789 | 123456789 | 378       | 123456789 |
| 123456789 | 123456789 | 123456789 | 123456789 | 123456789 | 123456789 | 123456789 | 123456789 | 123456789 |
+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+
| 123456789 | 123456789 | 3567      | 123456789 | 123456789 | 123456789 | 123456789 | 123456789 | 123456789 |
| 123456789 | 123456789 | 123456789 | 123456789 | 123456789 | 123456789 | 123456789 | 123456789 | 5         |
| 123456789 | 123456789 | 123456789 | 123456789 | 123456789 | 23        | 123456789 | 123456789 | 123456789 |
+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+


I suppose that 657 candidates is notionally equivalent to an 8-clue puzzle?

It was verified by checking it with BLISS (it's solvable with Bliss(1)):

"Bliss report": Show

Code: Select all

BLISS (SudokuP mode)
PM candidates = 657, givens = 3, verified with dSolve (255 guesses)

 (1c) [ 2r2c9]       r3c9 != 3, r3c9 != 6, r3c9 != 7, r3c9 != 8, r3c9 != 9,
                     r4c9 != 2, r4c9 != 4, r5c9 != 2, r5c9 != 4, r6c9 != 2,
                     r6c9 != 4, r7c9 != 2, r7c9 != 4, r9c9 != 2, r9c9 != 4
 (1c) [24r3c9]       r2c9 != 3, r2c9 != 6, r2c9 != 7, r2c9 != 8, r2c9 != 9
 (1c) [ 9r1c7]       r1c1 != 9, r1c3 != 9, r1c6 != 9
 (1c) [ 2r8c8]       r7c7 != 2, r7c7 != 9, r7c9 != 9, r8c7 != 2, r8c7 != 9,
                     r9c7 != 2, r9c7 != 9, r9c8 != 1, r9c8 != 3, r9c8 != 4,
                     r9c8 != 6, r9c8 != 7, r9c8 != 8, r9c9 != 9
 (1c) [ 9r1c7]       r1c9  = 9
 (1c) [ 8r1c7]       r1c1 != 8, r1c3 != 8, r1c6 != 8
 (1c) [ 8r5c6]       BD
S: 123456789456789132789231564674395218518624973392178456937562841261847395845913627


[tarek]

To produce 8 hidden singles you need the candidate to be missing from all other region peer cells. 64 candidates from 729 is 665. I would say after your last effort: you can do better

I was in the process of making a (for fun) ”transform into PM only grid” binary that would transform any ordinary vanilla sudoku into an PM equivalent by doing that process I mentioned above!

(P.S. joking aside, still well done)

Tarek

[dobrichev]

It looks like I got it right, and I can now give a verified example of a minimal SudokuP pencilmark puzzle. It has 657 candidates.

You might want to reconsider your algorithm in the part that checks for a secondary solution.
Edit: Wrong checking from my side.

[Mathimagics]

Hi Mladen!

Are you saying that the puzzle has multiple solutions? If so, can you provide evidence? Then I will have something to work with ...

You are solving the puzzle in SudokuP mode (Disjoint Groups) ??

Cheers
Jim

[dobrichev]

Oops... I didn't realised SudokuP is a variant beyond pencilmark sudoku.
No, I didn't check it as Disjoint Groups puzzle.

[Mathimagics]

Oops... I didn't realised SudokuP is a variant beyond pencilmark sudoku.

Ok, I should have made that clear, sorry!

I was not intending to suggest that I had exceeded the current 637 maximum (still true?) for a regular Sudoku PM puzzle !!

For SudokuP-PM, however, 657 candidates already looks like being very hard to beat ...

BTW, has anyone looked at maximum counts for:

• after initial DoSingles?

• after initial DoSingles + DoPairs?

[dobrichev]

No, your announce is correct. Just this time my immunity to your abbreviations has not served me well.

The size does matter, but after decomposition - maybe not.

[Mathimagics]

Just this time my immunity to your abbreviations has not served me well.

I'd forgotten about that!

But independent verification is always a good idea, so I will use SAT to verify any PM puzzles that I post.

[m_b_metcalf]

It looks like I got it right, and I can now give a verified example of a minimal SudokuP pencilmark puzzle. It has 657 candidates.

Thanks for the puzzle (but it would great if you could publish pencilmark puzzles also in line format):

Code: Select all

123456789020450000123456789000400000000450000123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789100000000103000700123456789123456789123456789123456789123456789123456789123456789123456789103006700123456789123456789123456789123456789123456789020050009123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789003000780123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789003056700123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789000050000123456789123456789123456789123456789123456789023000000123456789123456789123456789


I hope I got the right answer (in 0.05s):

Hidden Text: Show

Code: Select all

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

Regards,

Mike

[Mathimagics]

Mike, sorry for the 1-line format omission! I did give the solution above in the BLISS log, and yes, you do have the correct result.

Cheers
MM (not you, that other bloke)

[Mathimagics]

BLISS solves 87 of the benchmark puzzles and fails on 13. Total job time 0.254s.

If I enable BLISS(3), which does triple-cell checks, I get 99 solved in 10s. The only failure is on puzzle #48, which has no solution (verified with SAT). So BLISS completed the benchmark test.