## Pencilmark only Sudoku

For fans of Killer Sudoku, Samurai Sudoku and other variants

I was hoping that the last one would require a size 4. So far, I have accumulated the following data:

- 4 is the highest minimum constraint size.
- a valid puzzle can be made with at least 5 candidates in each cell. 6 is not (yet) possible.
- 450 is my current record number of candidates. I wonder if there is a theoretical maximum?

udosuk, the format is not new, as I state on my website, but nobody has cared to give it a name. I remember a PM grid that was posted on this forum long ago, but I have not been able to find it. It was hand-made and the candidates had very regular patterns. There are also 2 "gremlin" puzzles posted by r.e.s. which sort-of qualify. Thanks for the link to the "one digit too much" variant. That answers the question about the lower limit.

Here is the 450 candidates grid. It has 2 starting singles and requires no guess. It is easily solved with 85 forcing nets.

Code: Select all
`12478    12345689  234569   234568   1248     35       123789    123457    3456746789    1245678   2345678  1349     12569    12345689 2345679   23459     236712456789 2345678   2345679  13456    127      2468     13679     136       23456791568     123456789 45       14678    1235679  1245678  123456789 14567     678912679    1238      245678   1356     23479    23567    3456789   19        2345682345789  2589      1245679  12367    12345689 1235789  12345678  1345689   2345912356789 235689    167      1234568  36789    14579    235       12368     127824789    134578    2456789  169      134789   13489    2456789   12356789  12345691234679  23789     1234578  368      124679   23479    1345689   49        12578`
Ruud

Posts: 664
Joined: 28 October 2005

Ruud wrote:- 4 is the highest minimum constraint size.
What does that mean? Could you elaborate a little please...

Ruud wrote:- a valid puzzle can be made with at least 5 candidates in each cell. 6 is not (yet) possible.
Wonderful! Would you like to post that puzzle please?

Ruud wrote:- 450 is my current record number of candidates. I wonder if there is a theoretical maximum?
An obvious upper bound would be 81x9=729. I would be surprised to see one over 600 (avg 7.4 candidates/cell)... But I think 500-550 could be achievable...

And don't rule out hybrid ones... A puzzle with 3-4 initial clues but a large number of candidates (i.e. 7 or more) in most cells could give us surprising results...
udosuk

Posts: 2698
Joined: 17 July 2005

Technically, that wouldn't even be a hybrid, as a clue is nothing more than a cell with 1 candidate.

Bill Smythe
Smythe Dakota

Posts: 564
Joined: 11 February 2006

You're right Bill... I suppose Ruud isn't distinguishing them when he does the analysis...

I have another crazy idea... Seeing how it's so clumsy to represent these grids, I went out and sought ways to shorten the representation... One simple way is to use binary code conversion for the presence/absence of each of 9 digits... E.g. {35}=2^2+2^4=20, {127}=2^0+2^1+2^6=67...

For example, the 450-candidate grid becomes this:
Code: Select all
`203 447 318 190 139  20 455  95 124488 251 254 269 307 447 382 286 102507 254 382  61  67 170 357  37 382177 511  24 233 375 251 511 121 480355 135 250  53 334 118 508 257 190478 402 379 103 447 471 255 445 286503 438  97 191 484 345  22 167 195458 221 506 289 461 397 506 503 319367 454 223 164 363 334 445 264 211`

But, to make things even shorter, notice each of these numbers must not be larger than 511... Which is smaller than 26x26, so 2 letters are enough to represent each of them:
Code: Select all
`Hv Rf Mg Hi Fj Au Rn Dr EuSu Jr Ju Kj Lv Rf Os La DyTn Ju Os Cj Cp Go Nt Bl OsGv Tr Ay Iz Ol Jr Tr Er SmNr Ff Jq Cb Mw Eo To Jx HiSk Pm Op Dz Rf Sd Jv Rd LaTj Qw Dt Hj Sq Nh Aw Gl HnRq In Tm Ld Rt Ph Tm Tj MhOd Rm Ip Gi Nz Mw Rd Ke Id`

The capital letter represent the quotient of the number divided by 26, the small letter the remainder... For example, Au=0x26+20 (A is the 1st letter, u the 21st)... Now, get rid of the spaces and join the lines, we can use 2 or 3 lines to represent it (a single line would be too long for this forum):
Code: Select all
`HvRfMgHiFjAuRnDrEuSuJrJuKjLvRfOsLaDyTnJuOsCjCpGoNtBlOsGvTrAyIzOlJrTrErSmNrFfJqCbMwEoToJxHiSkPmOpDzRfSdJvRdLaTjQwDtHjSqNhAwGlHnRqInTmLdRtPhTmTjMhOdRmIpGiNzMwRdKeIdHvRfMgHiFjAuRnDrEuSuJrJuKjLvRfOsLaDyTnJuOsCjCpGoNtBlOsGvTrAyIzOlJrTrErSmNrFfJqCbMwEoToJxHiSkPmOpDzRfSdJvRdLaTjQwDtHjSqNhAwGlHnRqInTmLdRtPhTmTjMhOdRmIpGiNzMwRdKeId`

Excel would make it easy to do the conversion, which I'm happy to share the codes to do it...
udosuk

Posts: 2698
Joined: 17 July 2005

You certainly have a way to make things complicated, udosuk. Deciphering this code would take more time than solving the Sudoku itself.

A simple coding would be nnn for each cell, where each n can be 0-7, values 1, 2 and 4 representing the 3 candidates. 777 is a cell with all 9 candidates set.

- 4 is the highest minimum constraint size.
What does that mean? Could you elaborate a little please...

A sudoku has 324 constraints. 81 cells, 9 rows x 9 digits = 81 row constraints, same for columns and boxes. The size of a constraint is determined by the number of candidates left. At the start, each constraint has size 9. A hidden single or a naked single is a constraint of size 1. I can tell my generator not to disable a candidate when any of its 4 constraints would drop below a minimum size. Initially, I used a minimum of 2 to prevent the puzzle from having initial singles, but I discovered that I was able to increase this minimum to create more difficult puzzles. 4 is the highest minimum that I could achieve, but it is possible to set a cell minimum of 5 when I lower the other limits.

- a valid puzzle can be made with at least 5 candidates in each cell. 6 is not (yet) possible.
Wonderful! Would you like to post that puzzle please?

I posted it here on the UK forum.
Ruud

Posts: 664
Joined: 28 October 2005

The new record is 512 candidates.

Code: Select all
`1246    123456789 123457   12345678 134689  1346      12346789 13579     1234567923456   23459     1345679  23456789 136     1234689   2345789  3459      1356789125789  345789    12346789 1235678  234589  12345678  125789   123589    345891245679 123456789 2345679  1256789  1679    123456789 123678   12345679  12457913459   12345679  124569   145678   1345789 1234567   1235689  134569    1234591245789 3456789   1678     1245679  145789  134789    1235789  123456789 1234891245789 3456789   25789    2567     235679  123457    1234789  145789    1367891345679 23468     28       2568     123489  134568    12345678 12346789  1234567892345789 1245789   23578    12345689 1234689 123579    179      1345789   3579`

Solution:
621394857597218436843756129184965372379182564256473918968537241732841695415629783

The new record is 554 candidates

Code: Select all
`12357     12589     12356789 12578     2357      123456789 1356789   123567    1256789123456789 1246789   346789   123456789 12345678  1234569   1345689   124679    24568935789     1237      1235789  3457      1234578   234578    123456789 12379     1235678912467     1245789   2345679  1345679   345678    2456789   1234567   1379      123456789124689    12345789  234568   345678    123478    2345678   13456789  123       1236891356      12345789  23456789 1356789   12678     12346789  12345678  12356789  12356891346789   12345789  1345679  123456789 123456789 13489     134789    123456789 12345679135679    123456789 145679   1346789   1345678   123456789 13479     1235789   1234567891345678   123456789 456      1456789   12345678  1245689   123456789 12356789  123456789`

Solution:
216534879478269315539718426187356294952847631643921758825693147361475982794182563
Ruud

Posts: 664
Joined: 28 October 2005

Okay, to keep things straight forward, here is the "777" code proposed by you, for the 554-candidate puzzle...
Code: Select all
`724 623 737 626 324 777 537 734 637777 657 157 777 776 771 573 655 273127 704 727 164 766 366 777 705 737654 667 375 575 176 277 774 505 777653 767 372 176 746 376 577 700 713530 767 377 537 616 757 776 737 733557 767 575 777 777 543 547 777 775535 777 475 557 576 777 545 727 777576 777 070 477 776 673 777 737 777`

And in 3 lines:
Code: Select all
`724623737626324777537734637777657157777776771573655273127704727164766366777705737654667375575176277774505777653767372176746376577700713530767377537616757776737733557767575777777543547777775535777475557576777545727777576777070477776673777737777`
udosuk

Posts: 2698
Joined: 17 July 2005

The record has been broken again.

This is truly a shiver waiting to go up your spine. It has 590 candidates.

Code: Select all
`12345689  345689    123456789 134589    1234678   123456789 123456789 12346789  23456789 125689    12345689  1234568   14589     1234678   12348     12356789  12345789  12345678 125689    1256789   123456789 1234589   123689    123456789 125679    12456789  1234567891234578   1234578   1234568   123456789 13467     234567    23456789  123456789 12345678 145689    13456789  134568    14589     123456789 12456789  1456789   14579     1234567891236      123456789 123       1235689   123678    123456789 1236789   1246789   126789   12456789  14579     1234678   123489    1236789   12346789  123456789 123456789 12345789 123456789 123456789 1234568   123456789 12346789  23478     12345689  45        12345678 123456789 123456789 123456789 12346789  12369     12346789  123456789 1234689   12345789 `

Solution:
Code: Select all
`147365829295148736863297154382716495974852613651934278518479362726583941439621587`

It does not even require a guess to solve. 65 table conflicts are included in the solving path of 208 steps.
Ruud

Posts: 664
Joined: 28 October 2005

Ruud,

Does your method of constructing these Pencil Mark Sudokus give you much insight into how many PMS's there are, relative to the number of standard Sudokus? (ISTM that standard Sudokus comprise a very tiny subset of the PMS's.)
r.e.s.

Posts: 337
Joined: 31 August 2005

Here is the code for the 590-grid:
Code: Select all
`773 173 777 563 756 777 777 757 377633 773 772 463 756 742 737 767 776633 637 777 763 713 777 635 677 777766 766 772 777 554 374 377 777 776473 577 572 463 777 677 477 465 777710 777 700 733 716 777 717 657 617677 465 756 743 717 757 777 777 767777 777 772 777 757 346 773 060 776777 777 777 757 711 757 777 753 767773173777563756777777757377633773772463756742737767776633637777763713777635677777766766772777554374377777776473577572463777677477465777710777700733716777717657617677465756743717757777777767777777772777757346773060776777777777757711757777753767`
udosuk

Posts: 2698
Joined: 17 July 2005

r.e.s. wrote:Does your method of constructing these Pencil Mark Sudokus give you much insight into how many PMS's there are, relative to the number of standard Sudokus?

A PM grid can go from anywhere between 82 marks to the current record of 590. I expect that record to be broken soon. We may find PM grids that have more than 600 candidates. The number of PM grids is much higher than the set that can be created with clues, but I have no idea what the factor might be. Since only a few clues eliminate all 28 candidates, estimating the eliminations for a given number of clues is non-linear and not easily calculated. A statistical approach might give us some insight. Help wanted.

I've noticed that the high scoring grids all have a cascading series of singles at the beginning. A clever puzzle setter (not me) should be able to construct a series of cascading singles that would allow more than 600 PMs in the grid. Gordon's collection of minimum sudokus would be a good searching ground to find such a puzzle.

I've generated a new batch of puzzles that have a minimum constraint size 4. You can find them in this text file. There might be a puzzle with a backdoor size 4 in it, since I've found several that require 5 guesses in SudoCue. Maybe gsf can find them.

Generating these tough puzzles takes a lot of time. Since we're balancing on the edge of the maximum candidate grid, DLX requires much more time to validate each single candidate change. I wonder if there is some fractal behaveour behind this. When I did some fractal imaging, I also noticed that the borders were giving my CPU a hard time. When there are several surplus candidates, DLX can quickly find a second solution. When there are several candidates missing, DLX can quickly determine that there is no solution possible. This changes exponentially when we are approaching the the borders.
Ruud

Posts: 664
Joined: 28 October 2005

I'm wondering whether it would be interesting to look at some low-clue-count PMS's -- i.e. between 1 and 16 clue-cells (single-candidate cells), the rest being multi-candidate cells.
r.e.s.

Posts: 337
Joined: 31 August 2005

No new records to report, just some statistics.

The domain is a set of generated puzzles, where each cell has at least 2 candidates and there is no lower limit for the RCB constraints. All puzzles are fully 'maximized'.

Code: Select all
`candidates  puzzles460-469     6470-479     20480-489     61490-499     166500-509     296510-519     388520-529     302530-539     236540-549     132550-559     52560-569     22570-579     8580-589     3590         1`

The average is 518 candidates.
The standard deviation is 18.6

Looking at this distribution, it seems that the chances are low to find a puzzle with more than 600 candidates. Any mathematicians in the house who can confirm (or even calculate) this?

There must also be a lower limit for maximized PM grids.

Ruud
Ruud

Posts: 664
Joined: 28 October 2005

Ruud wrote:No new records to report, just some statistics.
Looking at this distribution, it seems that the chances are low to find a puzzle with more than 600 candidates. Any mathematicians in the house who can confirm (or even calculate) this?

the distribution may be skewed by the generation algorithm
mine tends towards lower 20's minimal with clues
and hardly ever strays below 19 or above 30 clues for minimal sudoku

here are, in row order, the singles <backdoor-size,number-backdoors>
for the 57 pm-only grids from a few posts back
it took 1h55m @ 3.2GHz and some reworked backdoor logic
there are some 5's but no 6's

Code: Select all
`4 11    4  1    4  2    4  3    5 33    4  4    4  2    5 474 15    4  3    4  2    4  1    5 31    5 48    4  6    4  44  1    4  1    4  3    5 48    4  4    4  1    5 35    4  24  1    4  2    5 31    5 27    4  1    4  2    4  1    4  44  4    5 41    4  1    4  4    4  2    4  3    4  7    4  14  5    5 34    5 44    4  4    4  4    4  1    4  8    5 364  2    4  1    4  2    5 47    4  4    4  3    5 20    5 355 43`
gsf
2014 Supporter

Posts: 7306
Joined: 21 September 2005
Location: NJ USA

A new record: 592 candidates, 1 solution.

Code: Select all
`12346789  234579    123456789 12345689  124       12467     123689    123456789 1234567891234578   123456789 23458     235       234       12345     123458    1234      1234567812345789  123456789 23456789  123456789 12345689  135678    12356789  12346789  13678913456789  123456789 123456789 1356789   12456789  123456789 235789    278       13568912345789  12345679  12346789  12356789  123456789 123456789 125789    12456789  12356789123456789 1235679   123456789 23456789  12345679  1235678   12356789  12345678  123567912345679  1234569   12345689  1345689   1345689   123456789 1345689   12345689  13469123567    12345679  23467     123456789 234579    123456789 123456789 123456789 134567912345679  23569     123456789 2456789   1245679   123456789 1234589   246789    123456789351826974792534816486791523679142385243685197815973642928367451164258739537419268`
Ruud

Posts: 664
Joined: 28 October 2005

PreviousNext