Pencilmark Sudoku

Programs which generate, solve, and analyze Sudoku puzzles

Re: Pencilmark Sudoku

Postby m_b_metcalf » Tue Oct 08, 2019 9:28 am

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

Could you kindly provide a link to these?

Thanks.
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 10786
Joined: 15 May 2006
Location: Berlin

Re: Pencilmark Sudoku

Postby rjamil » Tue Oct 08, 2019 11:27 am

Hi Mike,

m_b_metcalf wrote:
creint wrote: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
rjamil
 
Posts: 541
Joined: 15 October 2014
Location: Karachi, Pakistan

Re: Pencilmark Sudoku

Postby m_b_metcalf » Tue Oct 08, 2019 4:13 pm

rjamil wrote:I think creint refers to this list.

Many thanks. Some harder ones in that list than in the Sukaku one, I must say.
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 10786
Joined: 15 May 2006
Location: Berlin

Re: Pencilmark Sudoku

Postby tdillon » Tue Oct 08, 2019 9:09 pm

m_b_metcalf wrote: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.
tdillon
 
Posts: 42
Joined: 14 June 2019

Pencilmark Sudoku (Variants)

Postby Mathimagics » Sun Nov 17, 2019 2:06 pm

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
User avatar
Mathimagics
2017 Supporter
 
Posts: 1495
Joined: 27 May 2015
Location: Canberra

Re: Pencilmark Sudoku

Postby tarek » Sun Nov 17, 2019 2:55 pm

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 :lol:

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
User avatar
tarek
 
Posts: 3537
Joined: 05 January 2006

Re: Pencilmark Sudoku (Variants)

Postby dobrichev » Sun Nov 17, 2019 7:10 pm

Mathimagics wrote: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.
Last edited by dobrichev on Mon Nov 18, 2019 3:18 am, edited 1 time in total.
dobrichev
2016 Supporter
 
Posts: 1779
Joined: 24 May 2010

Re: Pencilmark Sudoku

Postby Mathimagics » Mon Nov 18, 2019 2:09 am

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
User avatar
Mathimagics
2017 Supporter
 
Posts: 1495
Joined: 27 May 2015
Location: Canberra

Re: Pencilmark Sudoku

Postby dobrichev » Mon Nov 18, 2019 3:15 am

Oops... I didn't realised SudokuP is a variant beyond pencilmark sudoku.
No, I didn't check it as Disjoint Groups puzzle.
dobrichev
2016 Supporter
 
Posts: 1779
Joined: 24 May 2010

Re: Pencilmark Sudoku

Postby Mathimagics » Mon Nov 18, 2019 4:14 am

dobrichev wrote: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 !! 8-)

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?
User avatar
Mathimagics
2017 Supporter
 
Posts: 1495
Joined: 27 May 2015
Location: Canberra

Re: Pencilmark Sudoku

Postby dobrichev » Mon Nov 18, 2019 5:05 am

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.
dobrichev
2016 Supporter
 
Posts: 1779
Joined: 24 May 2010

Disjoint Groups (Box Position) Pencilmark Sudoku?

Postby Mathimagics » Mon Nov 18, 2019 7:47 am

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

I'd forgotten about that! :lol:

But independent verification is always a good idea, so I will use SAT to verify any PM puzzles that I post.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1495
Joined: 27 May 2015
Location: Canberra

Re: Pencilmark Sudoku (Variants)

Postby m_b_metcalf » Mon Nov 18, 2019 7:44 pm

Mathimagics wrote: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
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 10786
Joined: 15 May 2006
Location: Berlin

Re: Pencilmark Sudoku

Postby Mathimagics » Tue Nov 19, 2019 1:31 am

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)
User avatar
Mathimagics
2017 Supporter
 
Posts: 1495
Joined: 27 May 2015
Location: Canberra

Tom Dillon's Benchmark 100

Postby Mathimagics » Tue Nov 19, 2019 5:33 am

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.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1495
Joined: 27 May 2015
Location: Canberra

PreviousNext

Return to Software