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: 1738
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: 702
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: 760
Joined: 27 May 2015

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: 43
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: 760
Joined: 27 May 2015

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: 1903
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: 760
Joined: 27 May 2015

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: 607
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: 760
Joined: 27 May 2015

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: 607
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: 760
Joined: 27 May 2015

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: 760
Joined: 27 May 2015

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: 760
Joined: 27 May 2015

Previous

Return to Sudoku variants