Pencilmark only Sudoku

For fans of Killer Sudoku, Samurai Sudoku and other variants

Pencilmark only Sudoku

Postby Ruud » Thu Oct 12, 2006 2:59 am

Here is a Sudoku without given numbers. Instead, you have to start with the pencilmark grid. The absence of given numbers startles most solver programs, so you may have to use the grey matter for this one.

The unique solution has been verified with DLX.

Code: Select all
.------------------------------.------------------------------.------------------------------.
| 1257      23479     12479    | 2468      1245679   14568    | 579       357       13458    |
| 135679    12456789  4567     | 35678     2356      256789   | 24569     234       35679    |
| 2348      1256      1235678  | 12478     345789    1479     | 45679     134       126789   |
:------------------------------+------------------------------+------------------------------:
| 12356789  45679     356      | 138       2456      123489   | 124567    138       12467    |
| 123468    134679    34679    | 2468      15678     12346789 | 12346789  78        123456   |
| 2578      1268      346789   | 5689      12345678  458      | 1234567   679       1245789  |
:------------------------------+------------------------------+------------------------------:
| 234567    24678     12458    | 19        13456789  1234689  | 2358      234589    12679    |
| 378       1689      145689   | 123456789 1234678   2578     | 126       12345689  3589     |
| 13568     13479     13489    | 13789     34568     35689    | 123478    67        235678   |
'------------------------------'------------------------------'------------------------------'


Solution in tiny text:
729461538614835927358297641965328714143679285287514369472153896896742153531986472

Can anyone find a logical path to this solution?

[edit]

- added box boundaries to grid.

A candidate grid without givens allows us to reduce the info to the absolute minimum, making it possible to generate harder Sudokus than with given numbers. A given number always eliminates 28 candidates simultaneously, but here each candidate can be eliminated individually. I have already found several puzzles that require brute force (guessing). Some of these have a SudoCue rating around 50000. The hardest Sudokus from ravel's list rate arount 25000.

SudoCue can solve it with the following techniques:
- 6x ALS-xz
- 3x Nishio
- 39 table contradictions
- 1 guess

Ruud
Ruud
 
Posts: 664
Joined: 28 October 2005

Postby tarek » Thu Oct 12, 2006 2:01 pm

Interesting Ruud, I ran the thought of something like this when Carcul posted a puzzle with added candidates..............

The crowded neighbourhood makes it slower to extract advanced techniques.......but is do-able...........

The trick is to verify the puzzle using DLX, I'm not sure how tricky that would be for someone who still does not understand it well:( .........

My solver easily managed the one posted on your site (Which is supposed to be easy anyway).......This one may take some time though:D

tarek
User avatar
tarek
 
Posts: 3762
Joined: 05 January 2006

Postby udosuk » Thu Oct 12, 2006 2:06 pm

Very interesting indeed... This puzzle has stretched past the ability of Simple Sudoku, which reported it had multiple solutions... But some (okay, much) fiddling with the candidates would prove that the solution is indeed unique...
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby Ruud » Thu Oct 12, 2006 2:20 pm

Tarek,

Since DLX operates on the candidate space, it can handle this format very well.

I posted another puzzle on the { broken link = www.sudoku.org.uk/discus/messages/29/2727.html?1160659906 } UK forum. It has a difficulty level that exceeds my Nightmares, but does not require any tabling or brute force.

Udosuk,

I cross-checked the unique solution in SudoCue. Another program that you can use is Sudoku Susser, but it refuses to Recurse because there are not enough (in fact: none) givens. I tested several puzzles that allowed me to see Bowman's Bingo in action:D

Ruud
Ruud
 
Posts: 664
Joined: 28 October 2005

Postby Ruud » Thu Oct 12, 2006 3:01 pm

I just found one that would enter the list of the most difficult Sudokus at #1. It scores 70070 in SudoCue, which needs 221 solving rounds, including 70 tabling steps and 1 guess.

Here is the PM grid:

Code: Select all
.------------------------------.------------------------------.------------------------------.
| 2356789   1245678   1257     | 13458     136789    123689   | 45679     1456789   35678    |
| 136789    89        12456    | 13579     1234569   456      | 3589      59        1236789  |
| 14678     246       1236     | 1235689   12469     1348     | 246789    35689     347      |
:------------------------------+------------------------------+------------------------------:
| 12345679  12568     2345789  | 346789    14678     24589    | 1289      23589     134568   |
| 23568     1256789   1257     | 236       258       123489   | 13569     46789     149      |
| 1349      124689    135689   | 13469     12379     15678    | 123678    123689    1234568  |
:------------------------------+------------------------------+------------------------------:
| 234679    12358     123578   | 4678      12345689  2569     | 123578    13458     34678    |
| 2346789   134789    15       | 123456789 134567    2346789  | 37        1235679   123589   |
| 2389      234689    135789   | 23478     13569     1234679  | 134569    2456789   234578   |
'------------------------------'------------------------------'------------------------------'


And the solution:

Code: Select all
572193486984726351163548297718364925395281674426975813257639148641852739839417562


Ruud.
Ruud
 
Posts: 664
Joined: 28 October 2005

Postby udosuk » Thu Oct 12, 2006 3:45 pm

On a 1024x768 screen, your grid is (sometimes) line-wrapped and deformed badly...
Other times, the annoying horizontal scroll bar is brought out...:(

  2356789      1245678      1257          │  13458          136789        123689      │  45679          1456789      35678        
  136789        89                12456        │  13579          1234569      456            │  3589            59                1236789    
  14678          246              1236          │  1235689      12469          1348          │  246789        35689          347            
────────────────────┼────────────────────┼────────────────────
  12345679    12568          2345789    │  346789        14678          24589        │  1289            23589          134568      
  23568          1256789      1257          │  236              258              123489      │  13569          46789          149            
  1349            124689        135689      │  13469          12379          15678        │  123678        123689        1234568    
────────────────────┼────────────────────┼────────────────────
  234679        12358          123578      │  4678            12345689    2569          │  123578        13458          34678        
  2346789      134789        15              │  123456789  134567        2346789    │  37                1235679      123589      
  2389            234689        135789      │  23478          13569          1234679    │  134569        2456789      234578      

No I'm not telling you the secret about how to skip the code boxes...:D
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby gsf » Thu Oct 12, 2006 6:01 pm

both of the puzzles have singles backdoor size 3
(solve 3 backdoor cells and the puzzle solves with singles)
add in box constraints (and/or anything up to and including coloring) and the backdoor size is 2
there's not many backdoors, so unlucky guessers will have a hard time
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby Ruud » Thu Oct 12, 2006 10:02 pm

Thanks for checking the backdoor sizes, gsf.

While I was fine-tuning my generator, it came up with a remarkable puzzle. Every constraint has at least 4 candidates left.

Code: Select all
.------------------------.------------------------.------------------------.
| 1237    1256    36789  | 25789   4789    4569   | 1679    23457   1348   |
| 2456    13489   3459   | 1356    3679    1247   | 2478    5789    12368  |
| 2358    24789   1267   | 2489    123457  13468  | 34569   4568    1279   |
:------------------------+------------------------+------------------------:
| 1569    2578    3457   | 145678  3459    2356   | 234689  1236    146789 |
| 3679    12348   2489   | 1236    56789   1569   | 2357    1489    4579   |
| 14689   1567    234678 | 1237    12489   34578  | 1235    5789    6789   |
:------------------------+------------------------+------------------------:
| 24789   3678    1469   | 1346    1246    1357   | 5689    1256789 2345   |
| 1238    4569    125678 | 3579    2347    2689   | 1479    1348    2356   |
| 3457    3789    1256   | 23489   14568   256789 | 1578    23569   1457   |
'------------------------'------------------------'------------------------'

There is no logical move to start with. SudoCue has to start with a guess (using brute force). There are 3 guesses needed with all techniques including tabling enabled.

I wonder whether this has an effect on the backdoor size.

Here is the solution:

163574928589162473247938561625493817738651249914287356871325694356749182492816735

Ruud
Ruud
 
Posts: 664
Joined: 28 October 2005

Postby Mauricio » Fri Oct 13, 2006 12:05 am

Very interesting, I have 2 different ideas to generate that kind of sudokus:

1. Start from the linked list of DLX and then remove a file (rank?) randomly (one at a time, it will be useful to create a pemutation of the numbers 1,2,...,729 to do that); if it has 0 solutions, then add it again to the linked list. Repeat. If the final matrix has a solution, then we are done, if not, start again. (Will we have always 1 solution in the end with this process?)

2. Create a sudoku grid and a locally minimal solution (randomly both). Then add a file that was eliminated in the process(randomly) to the linked list; check the number of solutions, if it is 2(or more), eliminate that file again. Repeat. When we are done, we are sure that we have only 1 solution.

Do you use any of that ideas, Ruud?

I would think that idea 2 is faster than 1, though I have not implemented them yet.
Mauricio
 
Posts: 1175
Joined: 22 March 2006

Postby daj95376 » Fri Oct 13, 2006 1:38 am

Ruud, would you please consider making the first line of your PM grid look like the last line? The periods in the first line screw up my parsing because I use the same logic to load PMs as I do a standard grid; i.e., non-single line puzzle. Thanks!!!!

BTW: I was able to solve your first grid here and the one in the UK forum. However, the two grids (above) that needed guessing brought my solver to a screeching halt. Other than on multiple-solution puzzles, this has never happened before to my solver. My elimination-by-contradiction routine was always able to get past any previous obstacle.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby udosuk » Fri Oct 13, 2006 2:41 am

daj95376 wrote:Ruud, would you please consider making the first line of your PM grid look like the last line? The periods in the first line screw up my parsing because I use the same logic to load PMs as I do a standard grid; i.e., non-single line puzzle. Thanks!!!!

Ruud's format is custom-designed in his softwares, which also deal with killer sudoku puzzles (with cages or so)... The selection of those symbols makes the cages look very nice, so I doubt he would be willing to change it... After all, it only takes very simple editing for users like us (in Notepad etc) to change it to whatever format we want for ourselves!:)

BTW, I think a smart parser program should be able to read that format... Once it reads a "." followed by a row of "-"s it should be able to tell that the "." is used as a grid symbol and not as a blank cell... Also, if you just copy & paste from the 2nd line to the 2nd last line a good parser should be able to read those codes too...:idea:
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby Ruud » Fri Oct 13, 2006 1:32 pm

Mauricio wrote:Do you use any of that ideas, Ruud?

The answer to your question is on the Programmers forum.

daj, your question about the grid format has already been answered by udosuk.

Is      this       the      way     to     do      it,     udosuk?
Ruud
 
Posts: 664
Joined: 28 October 2005

Postby udosuk » Fri Oct 13, 2006 1:53 pm

Ruud wrote:Is      this       the      way     to     do      it,     udosuk?

Yes      it      is!      :D

I shouldn't have expected that to trouble a programming master...:D

Did you find it out yourself or from our "Slitherlink" discussion in another place?
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby gsf » Fri Oct 13, 2006 11:38 pm

Ruud wrote:I wonder whether this has an effect on the backdoor size.

I had to accomodate backdoor size 3
(normal sudoku is conjectured to have max backdoor size 2)
the question now is are there any singles backdoor size 4 clueless sudoku

of the last three clueless sudoku posted
the first two have 99 singles backdoors of size 3
the last has 2 singles backdoors of size 3:
Code: Select all
[19]8[81]3[83]6
[22]8[81]3[83]6

interesting that there are two cells in common in the backdoors, making them
especially hard to chance on
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby udosuk » Sat Oct 14, 2006 8:30 am

gsf, there is already another puzzle variant called "Clueless Sudoku" (check Ruud's website if you want to know what it is)...

For this variant, Ruud has coined it as "Sukaku" (Suuji Kakure, "the digits are hidden")... Though I doubt if he has invented this variant (many people should have thought about this way before)... Other possible names could be "Pencilmark Sudoku" or "Candidate Sudoku"...

The biggest difference between it and classical sudoku is that while classical sudoku can be presented as 81 characters, these need 81 strings of numbers to be presented... An interesting problem will be what's the maximum total lengths of these strings to give a unique solution, i.e. "to give a unique solution, how many total candidates you can allow at most?"...

In Pyrrhon's website there is a puzzle which has exactly 2 candidates in all 81 cells, "one digit too much", as shown below...
Code: Select all
49 12 23 35 25 18 36 47 19
56 34 79 78 24 47 17 89 45
18 37 58 69 36 19 46 25 23
25 46 16 18 37 38 29 29 13
13 25 79 47 59 26 36 45 58
34 89 78 24 16 35 47 16 48
27 46 35 15 24 79 68 15 47
69 89 13 68 34 67 25 47 12
78 25 14 15 38 29 59 38 36

This has to be the "minimum end" of this variant...
udosuk
 
Posts: 2698
Joined: 17 July 2005

Next

Return to Sudoku variants