Pencilmark only Sudoku

For fans of Killer Sudoku, Samurai Sudoku and other variants

Re: Pencilmark only Sudoku

Postby blue » Tue Aug 20, 2019 11:33 pm

From another thread:

blue wrote:
denis_berthier wrote:A more interesting question for me would now be: can one find a Sukaku not in B7B?

Tarek's "singles backdoor size 6" puzzles are all "TE[singles](4)" -- "in BBBB, but not in BBB".
There were two more puzzles of interest, mentioned here:

The others (with high SE ratings) were "TE[singles](2)", and so in BB.
I can't say whether they're in B7B.

I should have added that if locked candidate and locked set eliminations are added to the techniques that are employed (initially, and after each guess or elimination), then the "singles backdoor size 6" puzzles become "T&E(3)", and "tareknasty1" becomes T&E(2).

Something else worth mentioning:
  • Sudoku Explainer's "Cell/Region Forcing chains" eliminations, cover Denis Berthier's "(singles) braids" eliminations.
  • Sudoku Explainer's methods cover all T&E[singles](1) eliminations; some part of the T&E[singles](2) eliminations, and some part of T&E[?](2) eliminations involving naked/hidden pairs and X-wings, and (I think) small chains.
  • (*) Sudoku Explainer's "Dynamic Cell/Region Forcing chains" cover something that, doesn't correspond to anything in the category of "T&E" eliminations -- common outcomes produced (in a complex way) from any one of a short list of possible guesses, one of which is inevitably "correct" (assuming the puzzle actually has a solution).
Aligned Pair and Aligned Triple eliminations, I don't really understand, but it's likely that they fall outside the scope of T&E eliminations too.

Disregard what follows.
The differences were due to a bug in by code. Thanks tarek.

@Dobrichev: referring to your latest post; for the first of the BDS 6 puzzles SE+ "failed" here:

Code: Select all
+-------------------------------+-------------------------------+-------------------------------+
| 3678      13456789  12346789  | 23456789  46789     12456789  | 2346789   3456789   4789      |
| 2356789   37        23457     | 2389      2346789   248       | 23689     1         2345789   |
| 12346789  1234567   1234678   | 12345689  123456789 12345678  | 23689     234569    2346789   |
+-------------------------------+-------------------------------+-------------------------------+
| 23456789  46789     12456789  | 1356789   13456789  145789    | 23456789  46789     12456789  |
| 23689     12346789  123456789 | 12356789  1379      12345789  | 12356789  2346789   12478     |
| 12345689  12346     123456789 | 123569    12345679  12347     | 12345689  2346      12345678  |
+-------------------------------+-------------------------------+-------------------------------+
| 12346789  156789    1246789   | 123456789 12345678  1245678   | 236789    3456789   12346789  |
| 12356789  179       1245789   | 123689    12346789  12478     | 2356789   379       12345789  |
| 12369     12345679  12346789  | 12345689  12346     12345678  | 12346789  2345679   12347     |
+-------------------------------+-------------------------------+-------------------------------+
ED=20.0/2.3/2.3

T&E[singles](2), T&E[singles + locked candidates](2), T&E[singles + locked candidates + locked sets](2), and T&E[singles + locked candidates + locked sets + basic fish](2) ... all "fail" at this point:

Code: Select all
+--------------------------------+--------------------------------+------------------------------+
| 3678       13456789  12346789  | 23456789   46789      12456789 | 2346789    3456789  4789     |
| 2356789    37        23457     | 2389       2346789    248      | 23689      1        2345789  |
| 12346789   1234567   1234678   | 12345689   123456789  12345678 | 23689      234569   2346789  |
+--------------------------------+--------------------------------+------------------------------+
| 23456789   46789     12456789  | 1356789    13456789   145789   | 23456789   46789    12456789 |
| 23689      12346789  123456789 | 12356789   1379       12345789 | 12356789   2346789  12478    |
| 12345689   12346     123456789 | 123569     12345679   12347    | 12345689   2346     12345678 |
+--------------------------------+--------------------------------+------------------------------+
| 123456789  156789    1246789   | 123456789  12345678   1245678  | 236789     3456789  12346789 |
| 12356789   179       1245789   | 123689     12346789   12478    | 2356789    379      12345789 |
| 12369      12345679  12346789  | 12345689   12346      12345678 | 123456789  2345679  12347    |
+--------------------------------+--------------------------------+------------------------------+

Interestingly(?), nothing happens at level 2, except in the T&E[singles] case.

The difference between the two final states, is that SE has two additional eliminations: 5r7c1 and 5r9c7.
Is it an easy job to plug the PM state from just above, into SE, and "ask it" if it can still eliminate those two candidates, and if so, how ?

BTW: I'm only asking out of curiosity.
You guys are on you own here.
Good luck, and have fun :)
Last edited by blue on Wed Aug 21, 2019 10:30 am, edited 2 times in total.
blue
 
Posts: 853
Joined: 11 March 2013

Re: Pencilmark only Sudoku

Postby tarek » Wed Aug 21, 2019 7:47 am

I had a go at the Sukaku Explainer GUI which accepts parsing the Pencilmark grid as you posted it
Pressing Solve Step would give 1st this step with difficulty rating of 9.2

Double Forcing Chain: I2.5 on & off ==> G9.5 off
Dynamic Double Forcing Chain
With this solving technique, we will prove the two following assertions:
If I2 contains the value 5, then G9 cannot contain the value 5
If I2 does not contain the value 5, then G9 cannot contain the value 5
Because the two assumptions are complementary, and the results are the same, we can conclude that G9 cannot contain the value 5.
Each assertion is proved by a different chain of simple rules. The chains can be dynamic, which means that the conclusions of multiple sub-chains must be combined in some cases.
The details of each chain are given below. Use the view selector below the grid to switch between the graphical illustrations of the two different chains.

chain 1 with image: Show
Chain 1: If I2 contains the value 5, then G9 cannot contain the value 5 (View 1): (1) If I2 contains the value 5, then I4 cannot contain the value 5 (the value can occur only once in the column) (2) If I2 contains the value 5 (initial assumption), then I6 cannot contain the value 5 (the value can occur only once in the column) (3) If I6 does not contain the value 5 and I4 does not contain the value 5 (1), then G9 cannot contain the value 5 (Pointing: Cells G4,G5,G6: 5 in block and column)
Image

chain 2 with image: Show
Chain 2: If I2 does not contain the value 5, then G9 cannot contain the value 5 (View 2): (1) If I2 does not contain the value 5, then B1 cannot contain the value 5 (Claiming: Cells A2,C2: 5 in row and block) (2) If I2 does not contain the value 5 (initial assumption), then B3 cannot contain the value 5 (Claiming: Cells A2,C2: 5 in row and block) (3) If B3 does not contain the value 5 and B1 does not contain the value 5 (1), then A8 cannot contain the value 5 (Claiming: Cells B7,B9: 5 in column and block) (4) If B3 does not contain the value 5 (2) and B1 does not contain the value 5 (1), then C8 cannot contain the value 5 (Claiming: Cells B7,B9: 5 in column and block) (5) If C8 does not contain the value 5 and A8 does not contain the value 5 (3), then G9 cannot contain the value 5 (Claiming: Cells G8,I8: 5 in row and block)
Image
User avatar
tarek
 
Posts: 3027
Joined: 05 January 2006

Re: Pencilmark only Sudoku

Postby blue » Wed Aug 21, 2019 10:29 am

Thank you tarek,

I had a stupid bug in my code ...
Code: Select all
if (solution[9 * r + c] == d)
    continue; // impossible elimination
should have been:
Code: Select all
if (solution[9 * r + c] == d + 1)
    continue; // impossible elimination

SE has its particular way of explaining things.
The two eliminations can be done with (simple) "grouped candidate" AICs, too ... starting from that PM state.
(Something else, that has been missing in SE).

BTW: After fixing the bug, nothing had changed in the T&E depth(s) that were required to solve the puzzles.
blue
 
Posts: 853
Joined: 11 March 2013

Re: Pencilmark only Sudoku

Postby tarek » Wed Aug 21, 2019 12:45 pm

Explainer indeed has a language of its own. It remains a valuable tool nevertheless.

The future release(s) of Sukaku explainer will show more efficient and faster solving in general. The GUI also would accept pasting pencilmarked grids like the one you posted with explainer continuing solution from that point as I demonstrated.
User avatar
tarek
 
Posts: 3027
Joined: 05 January 2006

Re: Pencilmark only Sudoku

Postby m_b_metcalf » Tue Sep 03, 2019 10:40 am

This type of puzzle has somehow escaped my notice until now. For program testing I found the 729-digit string the most convenient format, so here are five published puzzles in that form for other adventurers:

Code: Select all
123456789123456789023456789123406789123456789120406789123406789123406780123456789123456789103050000023056700023056789123456789123456789123456789023000700123456789123456789123456789123456789120056789123456789120450789123456789123406789123456789123456789123456789123456789020056789123456789123456789123456789123456789123456789123456789100400000123456789120450789123456789123456789000450000123456789123456789123456789123456789123456789123056789123456789123456789123456789123456789123456789123456789123456789023456789123456789123456009123406789123456789020000700123456789123456789123456789123456789123456789103450009100406009123456789123456789123456789123456789123456789020050000123456789123456709123456709123456789020000700020050700
dobrichev 637

120050700023400709120400709020406080120456709100456080000050709003050700103450080103056709123456789000456700003056780023056000020056789020456009023400000003056709023400080120056000123056780120400780003450789100400709000456709103400000120006789123056789000456709003056000103000080020456000123400089120456700103000080120406700123406080103406709003406709020406080100056780123406789123406789000000780123456000020050780120006080003406789000056089123456780000450080123456700000006709120450789023456700020406780120450080100000009103456789123406089023050080023450089120006709003000780100006089100456089123456789123406780020050780120006000123456089003050089103056080103400709103400089103000789003456080003056089123400780000006700023056780
ruud's first

123000700120056000003006789020050789000400789000456009100006709023450700103400080020456000103400089003450009103056000003006709120400700020400780000050789123006080023050080020400789120006700020400089123450700103406080003456009000456080120000709100056009020050780003450700100456780003450009023056000023406089123006000100406789003006709123400080020400089123006000000056789100056009023050700100400089000450709100406089100056700023406780123000700120400089003450780123050000000050789000006789020400789003006780100406009103406000120406000103050700000056089120056789023450000123000080000456009120056780003050709023400700020006089100400709103400080023056000003450700003000789120056000023400089100456080020056789100050780023056009100450700
ruud 13.10.2006

000000009000000080123450000000000700003406000120406000123400000100450000023050000000000700123050000123450000123400080003400089120400089000006000100450089023050089123400000123000000000006000123400080000050000120400089123400780100400789023000789120006080000400000120000009100006080000006780000050000020000780003000000020006789123006080123006000000000700000000009003406080100406080000050000000406080020006080003056080003056009003050009003406080020000000000406780000400780000406789100000000123456000123056700000000080000056000000406700020406700000000009100056700003056700023056000023056709023050009020056080100000000020006789003000780000056780000400000100456000100056709100450009000456080000406789003000000100000780020000000000056780
champagne dry with r7c4 changed to 56

000400009120000000023000000003050000020050000100000080003006000000400700100000009000056000003400000000000709000000780020400000000400700100000700000000089000450000100000080003000700000050080000006009003006000100000009000406000020050000023000000020050000000406000100006000100000080003000700003000080020000009020000009103000000103000000020050000000000709000400700000050009020006000003006000000450000000050080003400000000000089000000780020400000100006000003050000000400700100006000000400080020000700000406000003050000100050000020400000000000709000006080100050000000400700000006009000000089103000000000006080003400000000006700020050000000400700120000000000000780020050000100400000100050000003000080020000009000050009003000080003006000
81 pairs
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 10101
Joined: 15 May 2006
Location: Berlin

Re: Singles backdoor size 6

Postby m_b_metcalf » Fri Sep 13, 2019 11:46 am

tarek wrote:Here are the original 11 puzzles in the 729 line format

After much huffing and puffing, my solver finally solved the second version:
Hidden Text: Show
Code: Select all
  3  8  1  4  7  6  2  5  9   
  5  7  4  2  9  8  6  1  3
  9  2  6  1  5  3  8  4  7
  2  4  9  6  8  1  3  7  5
  8  6  5  7  3  9  1  2  4
  1  3  7  5  4  2  9  6  8
  4  9  2  3  1  5  7  8  6
  7  1  8  9  6  4  5  3  2
  6  5  3  8  2  7  4  9  1

and I'd be grateful for confirmation that that result is correct.

Thanks,

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

Re: Pencilmark only Sudoku

Postby creint » Fri Sep 13, 2019 4:20 pm

Result is correct, easy with minisat in 0.12 seconds. Did your solver use logic or DLX?
creint
 
Posts: 97
Joined: 20 January 2018

Re: Pencilmark only Sudoku

Postby m_b_metcalf » Fri Sep 13, 2019 4:50 pm

creint wrote:Result is correct, easy with minisat in 0.12 seconds. Did your solver use logic or DLX?

17 candidates were eliminated by logic, the rest was brute force.
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 10101
Joined: 15 May 2006
Location: Berlin

Re: Pencilmark only Sudoku

Postby creint » Fri Sep 13, 2019 6:12 pm

m_b_metcalf wrote:17 candidates were eliminated by logic, the rest was brute force.


So 5 in all corners from the corner boxes + 9r1c7. And how long did the solver take to find those?
With my current logic it took 0.6 seconds to reach that state.
creint
 
Posts: 97
Joined: 20 January 2018

Re: Pencilmark only Sudoku

Postby m_b_metcalf » Fri Sep 13, 2019 6:38 pm

creint wrote:
m_b_metcalf wrote:17 candidates were eliminated by logic, the rest was brute force.


So 5 in all corners from the corner boxes + 9r1c7. And how long did the solver take to find those?
With my current logic it took 0.6 seconds to reach that state.

Code: Select all
 At  7  1 cannot have   5
 At  7  9 cannot have   5
 At  9  1 cannot have   5
 At  9  9 cannot have   5
 At  1  1 cannot have   5
 At  1  3 cannot have   5
 At  1  7 cannot have   5
 At  1  7 cannot have   9
 At  1  9 cannot have   5
 At  3  1 cannot have   5
 At  3  3 cannot have   5
 At  3  7 cannot have   5
 At  3  9 cannot have   5
 At  7  3 cannot have   5
 At  7  7 cannot have   5
 At  9  3 cannot have   5
 At  9  7 cannot have   5

 phase 1 took .30 seconds
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 10101
Joined: 15 May 2006
Location: Berlin

Re: Pencilmark only Sudoku

Postby tarek » Mon Sep 16, 2019 10:56 am

Here on the hardest sudokus thread there was also a discussion on how convoluted some of these pencilmark sudokus (sukakus) can get
User avatar
tarek
 
Posts: 3027
Joined: 05 January 2006

Previous

Return to Sudoku variants