Pencilmark only Sudoku

For fans of Killer Sudoku, Samurai Sudoku and other variants

Postby Ruud » Sat Oct 14, 2006 12:11 pm

gsf, thanks for your analysis.

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.:D

Code: Select all
12478    12345689  234569   234568   1248     35       123789    123457    34567
46789    1245678   2345678  1349     12569    12345689 2345679   23459     2367
12456789 2345678   2345679  13456    127      2468     13679     136       2345679
1568     123456789 45       14678    1235679  1245678  123456789 14567     6789
12679    1238      245678   1356     23479    23567    3456789   19        234568
2345789  2589      1245679  12367    12345689 1235789  12345678  1345689   23459
12356789 235689    167      1234568  36789    14579    235       12368     1278
24789    134578    2456789  169      134789   13489    2456789   12356789  1234569
1234679  23789     1234578  368      124679   23479    1345689   49        12578
Ruud
 
Posts: 664
Joined: 28 October 2005

Postby udosuk » Sat Oct 14, 2006 12:47 pm

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

Postby Smythe Dakota » Sat Oct 14, 2006 1:04 pm

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: 534
Joined: 11 February 2006

Postby udosuk » Sat Oct 14, 2006 1:36 pm

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 124
488 251 254 269 307 447 382 286 102
507 254 382  61  67 170 357  37 382
177 511  24 233 375 251 511 121 480
355 135 250  53 334 118 508 257 190
478 402 379 103 447 471 255 445 286
503 438  97 191 484 345  22 167 195
458 221 506 289 461 397 506 503 319
367 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 Eu
Su Jr Ju Kj Lv Rf Os La Dy
Tn Ju Os Cj Cp Go Nt Bl Os
Gv Tr Ay Iz Ol Jr Tr Er Sm
Nr Ff Jq Cb Mw Eo To Jx Hi
Sk Pm Op Dz Rf Sd Jv Rd La
Tj Qw Dt Hj Sq Nh Aw Gl Hn
Rq In Tm Ld Rt Ph Tm Tj Mh
Od 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
HvRfMgHiFjAuRnDrEuSuJrJuKjLvRfOsLaDyTnJuOsCjCpGoNtBlOsGvTrAyIzOlJrTrErSmNrFfJqCbM
wEoToJxHiSkPmOpDzRfSdJvRdLaTjQwDtHjSqNhAwGlHnRqInTmLdRtPhTmTjMhOdRmIpGiNzMwRdKeId

HvRfMgHiFjAuRnDrEuSuJrJuKjLvRfOsLaDyTnJuOsCjCpGoNtBlOs
GvTrAyIzOlJrTrErSmNrFfJqCbMwEoToJxHiSkPmOpDzRfSdJvRdLa
TjQwDtHjSqNhAwGlHnRqInTmLdRtPhTmTjMhOdRmIpGiNzMwRdKeId

Excel would make it easy to do the conversion, which I'm happy to share the codes to do it...:idea::)
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby Ruud » Sat Oct 14, 2006 2:19 pm

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

Postby Ruud » Sat Oct 14, 2006 3:06 pm

The new record is 512 candidates.:D

Code: Select all
1246    123456789 123457   12345678 134689  1346      12346789 13579     12345679
23456   23459     1345679  23456789 136     1234689   2345789  3459      1356789
125789  345789    12346789 1235678  234589  12345678  125789   123589    34589
1245679 123456789 2345679  1256789  1679    123456789 123678   12345679  124579
13459   12345679  124569   145678   1345789 1234567   1235689  134569    123459
1245789 3456789   1678     1245679  145789  134789    1235789  123456789 123489
1245789 3456789   25789    2567     235679  123457    1234789  145789    136789
1345679 23468     28       2568     123489  134568    12345678 12346789  123456789
2345789 1245789   23578    12345689 1234689 123579    179      1345789   3579

Solution:
621394857597218436843756129184965372379182564256473918968537241732841695415629783

[edit]

The new record is 554 candidates:D

Code: Select all
12357     12589     12356789 12578     2357      123456789 1356789   123567    1256789
123456789 1246789   346789   123456789 12345678  1234569   1345689   124679    245689
35789     1237      1235789  3457      1234578   234578    123456789 12379     12356789
12467     1245789   2345679  1345679   345678    2456789   1234567   1379      123456789
124689    12345789  234568   345678    123478    2345678   13456789  123       123689
1356      12345789  23456789 1356789   12678     12346789  12345678  12356789  1235689
1346789   12345789  1345679  123456789 123456789 13489     134789    123456789 12345679
135679    123456789 145679   1346789   1345678   123456789 13479     1235789   123456789
1345678   123456789 456      1456789   12345678  1245689   123456789 12356789  123456789

Solution:
216534879478269315539718426187356294952847631643921758825693147361475982794182563
Ruud
 
Posts: 664
Joined: 28 October 2005

Postby udosuk » Sat Oct 14, 2006 4:56 pm

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 637
777 657 157 777 776 771 573 655 273
127 704 727 164 766 366 777 705 737
654 667 375 575 176 277 774 505 777
653 767 372 176 746 376 577 700 713
530 767 377 537 616 757 776 737 733
557 767 575 777 777 543 547 777 775
535 777 475 557 576 777 545 727 777
576 777 070 477 776 673 777 737 777

And in 3 lines:
Code: Select all
724623737626324777537734637777657157777776771573655273127704727164766366777705737
654667375575176277774505777653767372176746376577700713530767377537616757776737733
557767575777777543547777775535777475557576777545727777576777070477776673777737777
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby Ruud » Sun Oct 15, 2006 9:45 am

The record has been broken again.:D

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  123456789
1234578   1234578   1234568   123456789 13467     234567    23456789  123456789 12345678
145689    13456789  134568    14589     123456789 12456789  1456789   14579     123456789
1236      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

Postby r.e.s. » Sun Oct 15, 2006 3:56 pm

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

Postby udosuk » Sun Oct 15, 2006 4:12 pm

Here is the code for the 590-grid:
Code: Select all
773 173 777 563 756 777 777 757 377
633 773 772 463 756 742 737 767 776
633 637 777 763 713 777 635 677 777
766 766 772 777 554 374 377 777 776
473 577 572 463 777 677 477 465 777
710 777 700 733 716 777 717 657 617
677 465 756 743 717 757 777 777 767
777 777 772 777 757 346 773 060 776
777 777 777 757 711 757 777 753 767

773173777563756777777757377633773772463756742737767776633637777763713777635677777
766766772777554374377777776473577572463777677477465777710777700733716777717657617
677465756743717757777777767777777772777757346773060776777777777757711757777753767
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby Ruud » Mon Oct 16, 2006 11:58 am

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

Postby r.e.s. » Mon Oct 16, 2006 7:39 pm

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

Postby Ruud » Wed Oct 18, 2006 10:51 am

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  puzzles
460-469     6
470-479     20
480-489     61
490-499     166
500-509     296
510-519     388
520-529     302
530-539     236
540-549     132
550-559     52
560-569     22
570-579     8
580-589     3
590         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

Postby gsf » Wed Oct 18, 2006 3:38 pm

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 47
4 15    4  3    4  2    4  1    5 31    5 48    4  6    4  4
4  1    4  1    4  3    5 48    4  4    4  1    5 35    4  2
4  1    4  2    5 31    5 27    4  1    4  2    4  1    4  4
4  4    5 41    4  1    4  4    4  2    4  3    4  7    4  1
4  5    5 34    5 44    4  4    4  4    4  1    4  8    5 36
4  2    4  1    4  2    5 47    4  4    4  3    5 20    5 35
5 43
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby Ruud » Tue Oct 24, 2006 9:01 pm

A new record: 592 candidates, 1 solution.

Code: Select all
12346789  234579    123456789 12345689  124       12467     123689    123456789 123456789
1234578   123456789 23458     235       234       12345     123458    1234      12345678
12345789  123456789 23456789  123456789 12345689  135678    12356789  12346789  136789
13456789  123456789 123456789 1356789   12456789  123456789 235789    278       135689
12345789  12345679  12346789  12356789  123456789 123456789 125789    12456789  12356789
123456789 1235679   123456789 23456789  12345679  1235678   12356789  12345678  1235679
12345679  1234569   12345689  1345689   1345689   123456789 1345689   12345689  13469
123567    12345679  23467     123456789 234579    123456789 123456789 123456789 1345679
12345679  23569     123456789 2456789   1245679   123456789 1234589   246789    123456789

351826974792534816486791523679142385243685197815973642928367451164258739537419268
Ruud
 
Posts: 664
Joined: 28 October 2005

PreviousNext

Return to Sudoku variants