The New Sudoku Players' Forum

by **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.

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

by **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...

by **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

by **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:

by **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.

by **Ruud** » Sat Oct 14, 2006 3:06 pm

The new record is 512 candidates.

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

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

by **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

by **Ruud** » Sun Oct 15, 2006 9:45 am

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

by **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.)

by **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

by **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.

by **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.

by **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

by **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

by **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

The New Sudoku Players' Forum

Pencilmark only Sudoku