SudokuP: 12-clue Puzzle Search

For fans of Killer Sudoku, Samurai Sudoku and other variants

Re: SudokuP: 12-clue Puzzle Search

Postby coloin » Thu Jul 26, 2018 11:02 pm

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: 1804
Joined: 05 May 2005

Re: SudokuP: 12-clue Puzzle Search

Postby blue » Fri Jul 27, 2018 1:24 am

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: 854
Joined: 11 March 2013

Re: SudokuP: 12-clue Puzzle Search

Postby Mathimagics » Wed Aug 01, 2018 4:09 am

.
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
User avatar
Mathimagics
2017 Supporter
 
Posts: 1284
Joined: 27 May 2015
Location: Canberra

Re: SudokuP: 12-clue Puzzle Search

Postby creint » Wed Aug 01, 2018 12:54 pm

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

Colors from steps will eventually be added in my solver.
creint
 
Posts: 97
Joined: 20 January 2018

Re: SudokuP: 12-clue Puzzle Search

Postby Mathimagics » Wed Aug 01, 2018 1:13 pm

.
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! :?
User avatar
Mathimagics
2017 Supporter
 
Posts: 1284
Joined: 27 May 2015
Location: Canberra

Re: SudokuP: 12-clue Puzzle Search

Postby eleven » Fri Aug 03, 2018 2:33 pm

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.

[Added for completeness:]

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: 2091
Joined: 10 February 2008

Re: SudokuP: 12-clue Puzzle Search

Postby Mathimagics » Fri Aug 10, 2018 1:57 pm

.
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.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1284
Joined: 27 May 2015
Location: Canberra

Re: SudokuP: 12-clue Puzzle Search

Postby Serg » Sat Aug 11, 2018 5:51 pm

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: 651
Joined: 01 June 2010
Location: Russia

Re: SudokuP: 12-clue Puzzle Search

Postby Mathimagics » Sat Aug 11, 2018 7:22 pm

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 ... 8-)
User avatar
Mathimagics
2017 Supporter
 
Posts: 1284
Joined: 27 May 2015
Location: Canberra

Re: SudokuP: 12-clue Puzzle Search

Postby Serg » Sat Aug 11, 2018 11:13 pm

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

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: 651
Joined: 01 June 2010
Location: Russia

Re: SudokuP: 12-clue Puzzle Search

Postby Mathimagics » Sun Aug 12, 2018 10:49 am

.
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).
User avatar
Mathimagics
2017 Supporter
 
Posts: 1284
Joined: 27 May 2015
Location: Canberra

Re: SudokuP: 12-clue Puzzle Search

Postby Mathimagics » Mon Aug 13, 2018 7:48 am

.
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 ... 8-)
User avatar
Mathimagics
2017 Supporter
 
Posts: 1284
Joined: 27 May 2015
Location: Canberra

Re: SudokuP: 12-clue Puzzle Search

Postby Mathimagics » Thu Sep 13, 2018 5:42 pm

.
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.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1284
Joined: 27 May 2015
Location: Canberra

SudokuP: Minimum Clue Puzzles

Postby Mathimagics » Tue Dec 18, 2018 5:40 pm

.
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?
User avatar
Mathimagics
2017 Supporter
 
Posts: 1284
Joined: 27 May 2015
Location: Canberra

Re: SudokuP: Minimum Clue Puzzles

Postby m_b_metcalf » Tue Dec 18, 2018 6:58 pm

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
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 10102
Joined: 15 May 2006
Location: Berlin

PreviousNext

Return to Sudoku variants