## SudokuP: 12-clue Puzzle Search

For fans of Killer Sudoku, Samurai Sudoku and other variants

### Re: SudokuP: 12-clue Puzzle Search

FWIW
here are 2 minimal 19C in the MC grid
Code: Select all
`......78..5..9.......2....4..14..........8..2.9....5..3....2.....4....63...7.5.........78..5..91......2....4..14..........8..2.9....5..3....2.....4....6....7.5...`

the MC grid has no valid normal sudoku 19 [only one 20 with 648 isomorphs]
not sure if we can get an sudokuP 18C
coloin

Posts: 2218
Joined: 05 May 2005
Location: Devon

### Re: SudokuP: 12-clue Puzzle Search

coloin wrote:not sure if we can get an sudokuP 18C

There are 324 (I'm pretty sure) ... all isomorphic ... all with 8 automorphisms.
The one below has diagonal and 180 degree rotataional symmetry, and symmetry w/rsp to the "E" transformation.

Code: Select all
`+-------+-------+-------+| 1 . . | . . 6 | . 8 . || . . . | 7 . . | . . 3 || . . . | . 2 . | . . . |+-------+-------+-------+| . 3 . | . . . | . . 7 || . . 4 | . . . | 2 . . || 8 . . | . . . | . 6 . |+-------+-------+-------+| . . . | . 4 . | . . . || 6 . . | . . 8 | . . . || . 7 . | 3 . . | . . 5 |+-------+-------+-------+`
blue

Posts: 909
Joined: 11 March 2013

### Re: SudokuP: 12-clue Puzzle Search

.
We have passed the 60K mark, so an update is in order:

Code: Select all
` MCB |    grids |  12CG | 12CG/grids-----+----------+-------+-----------  0  |      404 |   388 |   96.0396%  1  |     8460 |  5557 |   65.6856%  2  |    80749 | 18936 |   23.4505%  3  |   465992 | 21061 |    4.5196%  4  |  1729441 | 10637 |    0.6151%  5  |  4263856 |  2086 |    0.0700%  6  |  7781962 |   518 |    0.0067%  7  | 10245574 |    38 |    0.0004%  8  | 10402287 |     3 |           -----+----------+-------+-----------     | 53666689 | 60124 |    0.1120%`

So we have found 2800 grids in the last 7.5 days. But the rate is coming down, predictably ...

Total puzzle count is 309K

Mathimagics
2017 Supporter

Posts: 1901
Joined: 27 May 2015
Location: Canberra

### Re: SudokuP: 12-clue Puzzle Search

The last one blue posted:
Code: Select all
`+-------+-------+-------+| 1 . . | . . 6 | . 8 . || . . . | 7 . . | . . 3 || . . . | . 2 . | . . . |+-------+-------+-------+| . 3 . | . . . | . . 7 || . . 4 | . . . | 2 . . || 8 . . | . . . | . 6 . |+-------+-------+-------+| . . . | . 4 . | . . . || 6 . . | . . 8 | . . . || . 7 . | 3 . . | . . 5 |+-------+-------+-------+`

Solves nicely with diagonal symmetry from upper left to lower right:
Hidden Text: Show

Colors from steps will eventually be added in my solver.
creint

Posts: 340
Joined: 20 January 2018

### Re: SudokuP: 12-clue Puzzle Search

.
Hmmm.. I didn't know that you could put hidden tags around image attachments, nice to know ...

Some people apparently don't even know these tags exist!

Mathimagics
2017 Supporter

Posts: 1901
Joined: 27 May 2015
Location: Canberra

### Re: SudokuP: 12-clue Puzzle Search

creint wrote:Solves nicely with diagonal symmetry from upper left to lower right:

Nice.
In the first step you can clear all but 159 from the diagonal. Then it is really simple.

Rotational symmetry maps the cells row n/colum m to row (10-n)/col (10-m), e.g. 7r2c4<->8r8c6. In the puzzle you can find only the digit mappings (1,5)(2,4)(3,6)(7,8). So it has the symmetry, and - if the puzzle is unique - the solution must have it too => the center r5c5 must be 9.

The symmetry at the main diagonal maps row n/col m to row m/col n, e.g 7r2c4<->3r4c2. Digit mappings here are (1,1)(2,4)(3,7)(5,5)(6,8). So you only can have 159 in the main diagonal of the solution.

The symmetry at the other diagonal maps row n/colum m to row (10-m)/col (10-n), e.g. 7r2c4<->6r6c8. Digit mappings here (1,5)(2,2)(3,8)(4,4)(6,7). So you only can have 249 in this sub diagonal.

[edit 2]:
Ooops, i had mixed E anf F transformation before. As blue (re)posted today, the E transformation can be defined as
"swapping rows 2&4, 3&7, 6&8, and columns 2&4, 3&7, 6&8".
So the original puzzle
Code: Select all
`+-------+-------+-------+| 1 . . | . . 6 | . 8 . || . . . | 7 . . | . . 3 || . . . | . 2 . | . . . |+-------+-------+-------+| . 3 . | . . . | . . 7 || . . 4 | . . . | 2 . . || 8 . . | . . . | . 6 . |+-------+-------+-------+| . . . | . 4 . | . . . || 6 . . | . . 8 | . . . || . 7 . | 3 . . | . . 5 |+-------+-------+-------+`

goes to
Code: Select all
`+-------+-------+-------+| 1 . . | . . 8 | . 6 . || . . . | 3 . . | . . 7 || . . . | . 4 . | . . . |+-------+-------+-------+| . 7 . | . . . | . . 3 || . . 2 | . . . | 4 . . || 6 . . | . . . | . 8 . |+-------+-------+-------+| . . . | . 2 . | . . . || 8 . . | . . 6 | . . . || . 3 . | 7 . . | . . 5 |+-------+-------+-------+`

and we have the number mapping (1)(24)(37)(5)(68)(9)

Since the transformation has the "fixed" cells r159c159 we can clear all but candidates 159 there.
eleven

Posts: 2805
Joined: 10 February 2008

### Re: SudokuP: 12-clue Puzzle Search

.
We have passed the 62K mark, so another update is in order:

Code: Select all
` MCB |    grids |  12CG | 12CG/grids-----+----------+-------+-----------  0  |      404 |   389 |   96.2877%  1  |     8460 |  5618 |   66.4066%  2  |    80749 | 19378 |   23.9978%  3  |   465992 | 21845 |    4.6878%  4  |  1729441 | 11080 |    0.6407%  5  |  4263856 |  3122 |    0.0732%  6  |  7781962 |   534 |    0.0069%  7  | 10245574 |    41 |    0.0004%  8  | 10402287 |     3 |           -----+----------+-------+-----------     | 53666689 | 62010 |    0.1155%`

So we have found 1886 grids in the last 9 days.

Total puzzle count is 320K.

Mathimagics
2017 Supporter

Posts: 1901
Joined: 27 May 2015
Location: Canberra

### Re: SudokuP: 12-clue Puzzle Search

Hi, Mathimagics!
Mathimagics wrote:Total puzzle count is 320K.

Do you mean you have 320K 12-clue SudokuP puzzles? Could you upload them?

Serg
Serg
2018 Supporter

Posts: 789
Joined: 01 June 2010
Location: Russia

### Re: SudokuP: 12-clue Puzzle Search

Serg wrote:Do you mean you have 320K 12-clue SudokuP puzzles? Could you upload them?

Hi Serg,

Indeed yes. The puzzles are in the mail ...

Mathimagics
2017 Supporter

Posts: 1901
Joined: 27 May 2015
Location: Canberra

### Re: SudokuP: 12-clue Puzzle Search

Hi, Mathimagics!
Mathimagics wrote:
Serg wrote:Do you mean you have 320K 12-clue SudokuP puzzles? Could you upload them?

Indeed yes. The puzzles are in the mail ...

I got these puzzles, thank you!

Original file contains 320675 puzzles. I checked them for ED-uniqness (by canonicalization) and found that 67 puzzles are duplicates

Serg
Serg
2018 Supporter

Posts: 789
Joined: 01 June 2010
Location: Russia

### Re: SudokuP: 12-clue Puzzle Search

.
Sorry, I forgot to the add the qualifier not necessarily unique ...

I have 3 people providing puzzles and 5 or 6 different methods of producing them.

So my "catalog" management is currently focused on the solution grids, and doesn't check the puzzles themselves. I was going to do the ED puzzle filtering later on.

What really surprises me is that there are only 67 duplicates ( a figure that I have confirmed).

Mathimagics
2017 Supporter

Posts: 1901
Joined: 27 May 2015
Location: Canberra

### Re: SudokuP: 12-clue Puzzle Search

.
I have rebuilt my HS enumerator, and while it is still a work in progress, it is already 25-30 times faster than its predecessor, and this makes it feasible to attempt "back-filling" operations.

By "back-fill" I mean explicitly HS-testing all of the remaining grids in a given MCB category for 12-clue puzzles, as blue did to get exact counts (390 for MCB = 0, 0 for MCB > 12) in his original table (page 3 of this thread).

For example, we had 389 known grids with MCB = 0, so I HS-tested the 15 = 404 - 389 remaining grids, and found 12-clue puzzles for just 1 of these, confirming his count.

Next up is MCB = 1, the pending grid count is 2842 = 8640 - 5619. This has been completed, and found 173 grids had 12-clue puzzles, so 5792 is, I think, the exact count.

Code: Select all
` MCB |    grids |  12CG | 12CG/grids-----+----------+-------+-----------  0  |      404 |   390 |   96.5347%  (*)  1  |     8460 |  5792 |   68.4634%  (*)  2  |    80749 | 19505 |   24.1551%  3  |   465992 | 21964 |    4.7134%  4  |  1729441 | 11136 |    0.6439%  5  |  4263856 |  3144 |    0.0737%  6  |  7781962 |   536 |    0.0069%  7  | 10245574 |    41 |    0.0004%  8  | 10402287 |     3 |           -----+----------+-------+-----------     | 53666689 | 62511 |    0.1165%(*) = exact`

Backfill for MCB = 1 is now running. This will take longer ...

Mathimagics
2017 Supporter

Posts: 1901
Joined: 27 May 2015
Location: Canberra

### Re: SudokuP: 12-clue Puzzle Search

.
Nearly time to wrap this up!

First of all, I had a bug in my backfill process, so the above "eaxct count" for MCB = 1 was rubbish.

In the end I took all the puzzles that my very valuable contributors (coloin, Leren) found, added them to my random morph walker finds, then generated all {+1,-1} and {+2,-2} morphs This was repeated until I found no more new puzzles.

The final puzzle tally is 352,859, on 68,493 ED grids:

Code: Select all
` MCB |    grids |  12CG | 12CG/grids-----+----------+-------+-----------  0  |      404 |   390 |   96.5347%  1  |     8460 |  5838 |   69.0071%  2  |    80749 | 20901 |   25.8839%  3  |   465992 | 24395 |    5.2351%  4  |  1729441 | 12662 |    0.7321%  5  |  4263856 |  3617 |    0.0848%  6  |  7781962 |   630 |    0.0081%  7  | 10245574 |    56 |    0.0005%  8  | 10402287 |     4 |    0.0000%-----+----------+-------+-----------     | 53666689 | 68493 |    0.1276%`

At 68493, the grid count is just a tad shy of the range predicted by blue (68687 - 72631), so I'm running a special random morph walker that will hopefully identify some stragglers which can be morphed into new puzzles. This version of the walker takes a suggestion made by coloin, that instead of just looking at 12-clue puzzle morphs directly, we can instead walk through the 13-clue space, checking for reducible cases, ie 13-clue with a redundant clue, or a {-2, +1} morph.

Mathimagics
2017 Supporter

Posts: 1901
Joined: 27 May 2015
Location: Canberra

### SudokuP: Minimum Clue Puzzles

.
I have just noticed that the Wikipedia page Mathematics of Sudoku still has this entry under "Minimum number of clues":

Disjoint Groups: some 12-clue puzzles have been demonstrated by Glenn Fowler. Later also 11-clue puzzles are found. It is not known if this is the best possible.

So we need it updated to reflect the fact that

• we have established beyond doubt that 11 is in fact the best possible
• that all 11-clue puzzles have been found. There are 11 ED grids with 18 different puzzles, giving a total of 10368 x 18 = 186624 distinct (up to relabelling) puzzles

Does anybody have experience in updating Wikipedia entries?

Mathimagics
2017 Supporter

Posts: 1901
Joined: 27 May 2015
Location: Canberra

### Re: SudokuP: Minimum Clue Puzzles

Mathimagics wrote:.

Does anybody have experience in updating Wikipedia entries?

It's not difficult. If you plan do do it often register with a screen name. You need to follow the conventions for the mark-up language, which is straightforward if you're just making small edits. You can preview your edits before you post them (like here). When you're done, you might like to completely revise the main Sudoku entry. (I had a running battle with a pedant there years ago and gave up.)

Regards,

Mike

m_b_metcalf
2017 Supporter

Posts: 13214
Joined: 15 May 2006
Location: Berlin

PreviousNext