The New Sudoku Players' Forum

[David P Bird]

If I am interpreting that last post correctly, it seems that you now have a definitive answer to the question of how many-17 clue puzzles exist.

49157+42 ?
Somebody press a button !

Blue, Sorry if I got too enthusiastic, but surely I don't deserve ridicule. I was hoping that if a summary of this conclusion was produced I would at least have a chance of understanding it.

DPB

[dobrichev]

@David: Unfortunately no.

The above is based on the known 17s list which is not proven complete.

Blue and Champagne are developing highly refined method(s) for complete enumeration of the 17-clue puzzles. Their estimations are promising - the full scan would take ~10 to 100 CPU years (compared to 7 millions CPU years used for 16-clue search by McGuire). (correct me if I missed several trailing zeros)
The methods are complicated and the question whether the processing depends on some wrong assumption remains open.

P.S. cross-posting with Blue.

[blue]

Sorry David, I honestly thought you were just joking around ... although I didn't quite "get it".

[blue]

Blue and Champagne are developing highly refined method(s) for complete enumeration of the 17-clue puzzles. Their estimations are promising - the full scan would take ~10 to 100 CPU years (compared to 7 millions CPU years used for 16-clue search by McGuire). (correct me if I missed several trailing zeros)

For the 16-clue search, final version of McGuire's code took would have taken 500-600 core years (I think).
I made a version of it with the "secondary-level" UA cache that we were talking about the other day ... for 17's ... that would still have taken ~4000 core years. I don't quite remember, but without the cache, it would have been >40,000 for sure, and maybe more like 400,000.

Champagne is working independently now, with some of my and some of his ideas, and actively testing grids.
I don't know what his overall time will be, and I suspect that he isn't quite sure either.
I'm on indefinite leave of absence, but my latest code rev. would have taken ~10 core years.

Cheers,
Blue.

P.S. I see I'm cross-posting with Mladen again ... and need to read the post that follows this one.

[dobrichev]

I was hoping that if a summary of this conclusion was produced I would at least have a chance of understanding it.

The subject is spread here and there and below I will attempt to describe the statistics produced by Blue in this post.

The existence of low-clue puzzle which solution is a particular grid depends of grid's characteristics - the Unavoidable Sets.
Any valid puzzle hits all UA sets, else exchanging the values within the unhit UA set produces a secondary solution.

We divide the solution to a sub-structures - in this case 3 bands and 3 stacks.
We are forgetting about UA that are spread over multiple bands and investigate only those which are entirely located within a single band. Symmetrically, same for stacks.
Considering only a particular band, we can apply validity preserving transformations and represent it in its canonical form. It happens that there are only 416 different canonical bands. So we can investigate each of the 416 bands independently.
The opening post lists the minimal number of clues necessary to hit all UA sets within each canonical band. They are found by brute force. There, the absolute minimum is for band #29 (column 1) which can be completed by only 2 clues (column 4).

Code: Select all

Band    Sol     UA   MinClues  54+2    ...
29      516     81      2       9      ...


Irrelevant to the subject columns are the number of in-band UA sets (81, column 3) that, when unhit, lead to many solutions (516, column 2) but giving the required minimum of 2 clues in one of the 9 (column 5) ways resolves all of them.

Considering full grid and ONLY intra-band UA sets, a lower-band estimation of the minimal number of clues required to resolve the whole grid was done.
From one hand we need to resolve each of the 3 bands and it requires number of clues that is at least the sum of the minimally required number of clues for each of the 3 bands.
From other hand we need to resolve stacks in the same way, and this gives a second sum.
The worse (largest) sum from the bands and stacks gives the final lower-band estimation on the number of clues required to resolve the whole grid.

What Blue did is to scan all 5472730538 grids, cut-out them once to 3 bands and second time to 3 stacks, transform each of them to its canonical form, do a lookup for the minimal required clues for these 2 triples, find the larger sum, and display the count of grids having the respective sum.

Code: Select all

MCB |      grids |  17CG | 17CG/grids | 17CGP
----+------------+-------+------------+------
  6 |          0 |       |            |
  7 |          0 |       |            |
  8 |          6 |       |            |
  9 |    1239360 |   250 | 0.0201717% |   271
 10 |   97729312 |  5750 | 0.0058836% |  6215
 11 | 1082360670 | 20922 | 0.0019330% | 22235
 12 | 2631838676 | 16691 | 0.0006342% | 17642
 13 | 1364599022 |  2550 | 0.0001869% |  2654
 14 |  263770800 |   126 | 0.0000478% |   129
 15 |   28131065 |    10 | 0.0000355% |    10
 16 |    2785923 |     1 | 0.0000359% |     1
 17 |     228185 |       |            |
 18 |      47519 |       |            |
----+------------+-------+------------+------
    | 5472730538 | 46300 |            | 49157

From the result we see that there is no valid solution grid composed entirely from band 29 (all 3 bands and stacks being morphs of it). Such grid would have MCB=2+2+2=6.
In the same way combination of band 29 + band 29 + one of the bands requiring 3 clues is impossible too. No grids for MCB=2+2+3=7.
But we see that band 29 can successfully be combined by itself and a band requiring 4 clues (MCB=2+2+4=8), or by 2 other bands each requiring 3 clues (MCB=2+3+3=8), and this produces 6 different grids with MCB=8 which are listed in the next post.

Is there strong correlation between the number of clues required to resolve the substructures of the grid (bands and stacks) and the number of 17-clue puzzles actually found in this grid? Obviously yes. Grids, requiring less clues for resolving all intra-band UA, have better chance to be entirely resolved by 17 clues (column 4 in Blue's table).

Chance is estimated against the 49157 known so far 17-clue puzzles that resolve 46300 solution grids, shown in the bottom row.

These estimations are in use when knowing the solution grid you can test whether it is resolvable by 17 clues. Present algorithms are doing it for for average grid in less than 30 seconds, and in few minutes for a grid capable to be resolved by 17 clues.

[David P Bird]

Mladen,Thank you so much for that description. I now have a feel for the ingenuity behind the approach even though it will take me some further effort to absorb it as well as I would like.

Although I am a poor programmer, I am interested in the systems analysis aspects – organising the data so that the key information can be extracted and processed efficiently.

David
.

[coloin]

If you scan grids composed by intersecting the box 1 of the canonical representation of band #14 with the box 1 of stack #381, you get the ultimate answer of 42 17-clue puzzles, and no better combination exists.....
)

and i thought this was a joke reference to the old "hitchhiker" answer [42]

It took a super human search to find the minimum number of clues for a double band [7] [ range 7- ?12]

certainly all grids with a 3 X MCDB count of 35 cant have a 17 - but that wont be many

[dobrichev]

It is a fact on which I am joking 7 years later.

In the second post of this thread there is a table with columns
- number of ways you can produce 42 17-clue puzzles by crossing bands
- band number
- box-in-a-band number
- stack number
- box-in-a-stack number
- number of puzzles produced
Column 2,3,4,5 are for arbitrary exemplar for rows having column1 > 1, else they match the only exemplar.

Code: Select all

      1 014   1   381   1   42
      2 022   1   381   2   39
      1 014   3   176   2   37
      2 022   3   176   3   33
...


This is kind of fixing B12347, then expanding to valid grids, then finding all puzzles within these grids.

The top right value is really 42.

This could be checked by:
- taking band 14 and placing it on B123.

Code: Select all

123 456 789
456 789 123
798 231 564

- taking band 381

Code: Select all

123 456 789
457 289 631
689 713 254

- rotating band 381 90 deg clockwise so that it occupies B147

Code: Select all

641
852
973

724
185
396

267
538
419

- relabelling stack 381 so that its B1 matches band 14's box1

Code: Select all

6->1; 4->2; 1->3; 8->4; 5->5; 2->6; 9->7; 7->9; 3->8

123
456
789

962
345
817

619
584
237

Note: Now I am not sure whether relabelling is sufficient to produce all essentially different B12347 subgrids. If not, permutations should be involved.

- composing a sub-grid with B12347 fixed

Code: Select all

123 456 789
456 789 123
798 231 564

962 ... ...
345 ... ...
817 ... ...

619 ... ...
584 ... ...
237 ... ...

- finding all valid grids having these B12347 fixed (=45 grids)

- scanning each grid for 17s and the result is 42 puzzles.

- doing the same for all other combinations of (band number * crossing box in the band * stack number * crossing box in the stack) will result in less puzzles.

That said, the ultimate answer is 42 and we know the question.

[dobrichev]

Finally found the thread Minimal clues to complete a grid examining k-templates where statistics for max(sum(min_clues_per_partition)) were provided after partitioning the grid to 2+2+2+3 digit templates, 3+3+3 templates, and 4+5 templates. Not done for the whole grid catalogue.

[dobrichev]

Several statistics for low-clue puzzles/grids distribution are put together in this thread.