The New Sudoku Players' Forum

[blue]

Hi Mladen,

@Blue: Congratulations for your full enumeration of 11-clue puzzles!

Is this a toy project for testing the 17-clue search, and now you are waiting for confirmation that your method gave the correct result?
Hope the 17-clue enumeration is ongoing and these 13 cpu-days you spent for this branch is worth it.

Thank you, and thanks to all.

It wasn't a project to test ideas for the 17-clue search.
All I got out of it, was some new "128-bit register" code for finding UA's, and the satisfaction of knowing that all of the 11's have been found.

OK ... I'm using it now too, to get a good estimate of the # of grids with 12-clue puzzles.
Also it has made me realize (again), that 13 days of fan noise from a "tied up" computer, is more than I can bear.

Cheers,
Blue.

[blue]

This is sort of a continuation of this post.

Here are a few additional puzzles, with interesting shapes.

Code: Select all

+-------+-------+-------+    +-------+-------+-------+    +-------+-------+-------+
| 5 . 6 | . . . | 7 . 1 |    | 4 2 8 | . . . | 5 6 1 |    | 5 3 8 | 4 2 7 | 1 . . |
| . 1 . | . . . | . 3 . |    | 6 . . | . . . | . . 3 |    | 9 4 6 | 8 1 3 | 7 . . |
| 7 . 9 | . . . | 6 . 5 |    | 5 . . | . . . | . . 7 |    | 2 7 . | . . . | . . . |
+-------+-------+-------+    +-------+-------+-------+    +-------+-------+-------+
| . . . | . . . | . . . |    | . . . | . . . | . . . |    | 7 9 . | . . . | . . . |
| . . . | . . . | . . . |    | . . . | . . . | . . . |    | 1 2 . | . . . | . . . |
| . . . | . . . | . . . |    | . . . | . . . | . . . |    | 8 6 . | . . . | . . . |
+-------+-------+-------+    +-------+-------+-------+    +-------+-------+-------+
| 1 . 2 | . . . | 3 . 9 |    | 9 . . | . . . | . . 5 |    | . . . | . . . | . . . |
| . 7 . | . . . | . 2 . |    | 8 . . | . . . | . . 4 |    | . . . | . . . | . . . |
| 3 . 4 | . . . | 5 . 7 |    | 7 5 1 | . . . | 3 9 2 |    | . . . | . . . | . . . |
+-------+-------+-------+    +-------+-------+-------+    +-------+-------+-------+

+-------+-------+-------+    +-------+-------+-------+    +-------+-------+-------+
| . . . | . . . | 2 1 6 |    | . . . | . . . | 1 4 . |    | . . . | 2 4 . | 8 9 . |
| . . . | . . . | 5 7 3 |    | . . . | . . . | 3 8 7 |    | . . . | 5 3 8 | 1 6 2 |
| . . . | . . . | . . . |    | . . . | . . . | . 5 6 |    | . . . | . 1 9 | . 7 5 |
+-------+-------+-------+    +-------+-------+-------+    +-------+-------+-------+
| . . . | 4 3 5 | . . . |    | . . . | 6 8 . | . . . |    | 4 3 . | . . . | . . . |
| . . . | . . . | . . . |    | . . . | 1 3 9 | . . . |    | 2 1 5 | . . . | . . . |
| . . . | 1 8 9 | . . . |    | . . . | . 7 4 | . . . |    | . 8 6 | . . . | . . . |
+-------+-------+-------+    +-------+-------+-------+    +-------+-------+-------+
| . . . | . . . | . . . |    | 8 3 . | . . . | . . . |    | . . . | . . . | . . . |
| 7 3 9 | . . . | . . . |    | 6 7 2 | . . . | . . . |    | . . . | . . . | . . . |
| 2 1 8 | . . . | . . . |    | . 4 9 | . . . | . . . |    | . . . | . . . | . . . |
+-------+-------+-------+    +-------+-------+-------+    +-------+-------+-------+

It's likely that at least one, if not all of these will be non-minimal.

[Mathimagics]

.
Hi blue,

For all but ~460000 grids (the ones that I knew had 12's, and the grids with non-trivial automorphisms) ...

Do you mean the grids that you knew had 12-clue solutions? But that's only 45K, if I understand correctly. Are the others all non-trivial automorphism cases? In which case why does that influence the HSet enumeration outcome?

Also, I understood that your CF(soln + puzzle) function operates basically by canonicalising the solution, and applying the same transformations to the puzzle.

So if I give it a solution-puzzle pair where the solution is already in CF, I should expect no change in the puzzle.

If that is so, can you take a look at this example? The solution S for puzzle P is already in CF, but I got a modified puzzle (CP) back.

Code: Select all

 P = ..3...7..4.6...123....2..5..14.67.9..6759.21..9.21..6.841....75.........9758.....
 S = 123456789456789123789123456214367598367598214598214367841632975632975841975841632
CP = ......7...5.7..123.....3.56.14.6759..6.59.21..9..14.6.84....9.......58...7..41..2
 G = 00045500


[blue]

Hi Mathimagics,

Last question first: The solution grid has 12 automorphisms, and so the canonicalization routine tried 11 other transformations on the puzzle, looking for a smaller minlex puzzle to be produced. It found at least one, it seems.

For all but ~460000 grids (the ones that I knew had 12's, and the grids with non-trivial automorphisms) ...

Do you mean the grids that you knew had 12-clue solutions? But that's only 45K, if I understand correctly. Are the others all non-trivial automorphism cases? In which case why does that influence the HSet enumeration outcome?

Yes the others were cases with non-trivial automorphisms.
There are 414489 such grids, in total, or ~0.772% of the total.
There was an overlap between the two grid sets.
355 of the 45093 grids with known 12's, also had non-trivial automorphisms ... ~0.787% of them ... not unexpected, I guess.

Early on, seeing that 3 of the 12 grids with (known) 11's, had >1 automorphism, I was interested to know whether any of the other such grids, also had 11's. Looking into that, I ran into a lot of "killer" testing times, it seemed. When I tested random grids, though, that didn't seem to happen ... or at least not very often. That's why I separated them out, along with the grids with 12's, which I naturally assumed would take longer than the others.

About the effect on hitting set counts: In the end, I think that except for the "killer time" cases, the grids with >1 automorphism, actually tested a little faster than the average. On the other hand, after seeing your post, I've gone back and looked at the automorphism counts for the worst case grids. I had 12 grids that took > 1000 seconds. All but one of them has non-trivial automorphisms. The six grids from your earlier post are included in the list, and they all have >1 automorphism.

Hidden Text: Show

Code: Select all

   grid #  | #Aut |      timing |     HS count
-----------+------+-------------+-------------
# 53666688 |  108 | 25915.0625s |  20047963823
# 23199970 |   54 | 14386.8906s |  47561944352
# 53658890 |    2 |  8654.9219s |  17877667846 (1 ED 11, 2 total)
# 53666687 | 1296 |  7512.3438s |   8877298313
# 53664625 |    4 |  4898.0781s |  10456885720
# 53658889 |    2 |  5226.7656s |  11898451461 (1 ED 11, 2 total)
# 23199968 |    4 |  4367.4688s |   9295824254
# 53658888 |    1 |  2578.0781s |   7458593883
# 23199962 |    2 |  2562.9531s |   7383782810
# 53577383 |    6 |  1766.5938s |   3626494540
# 53577379 |    2 |  1722.4063s |   3099601071
# 23199965 |    2 |  1186.8125s |   2461006110

123456789564897231978312645647938512389125476251764893895271364712643958436589127 # 53666688
123456789456897231978312456564978312789123564231564897897231645312645978645789123 # 23199970
123456789457891236968372451571948362689723145234615897895237614312564978746189523 # 53658890
123456789564897231978312645645978312789123456231564897897231564312645978456789123 # 53666687
123456789457918362896237154671894235589723641342561978968342517234175896715689423 # 53664625
123456789457891236968372451571948362689523174234617895895234617312765948746189523 # 53658889
123456789456897231978312456247968315589173624631524897894631572312745968765289143 # 23199968
123456789457891236968372451571938642389624175246715893895267314712543968634189527 # 53658888
123456789456897231978312456245968317789143625631725894894631572312574968567289143 # 23199962
123456789457298613869371452594837261382169574716524938678912345931745826245683197 # 53577383
123456789457298613869371452578912364931764825246583197695837241382149576714625938 # 53577379
123456789456897231978312456247638915389125674561749823894571362712963548635284197 # 23199965


I don't have a good explanation for why things should be like that.

There's this: for the top time grid, with 108 automorpihsms ... if U is an unavoidable set, then there are up to 108 distinct versions of U, obtained through transformation by one of the automorphisms. If U was a large 2-digit set, that would suggest that there are a lot of large 2-digit sets in the grid -- leaving "not much room" for smaller 2-digit sets. The same thing works the other way too, though -- if U was small, there should be a lot of small UA sets.

That all makes some kind of sense, but then most of the grids listed above, have relatively small automorphism counts. In the end, it's all a mystery to me.

Cheers,
Blue.

[Mathimagics]

Thanks!

No shortage of mysteries in this topic!

[Mathimagics]

.
I am working on trying to improve my (clearly inefficient) HS enumerator. It seems to me that even getting it to the stage where it's only 3-4 times slower than blue's, would be a significant improvement, since it probably is 10+ times slower right now.

I think I can improve in 3 main areas:

• improve throughput by using bit-vectors for the UA/HS logical operations in the HS main loop. I'm using standard C so I'll start with 64-bit operands, so 256 UA's would involve 4 words, 512 would require 8.

• implementing a secondary UA cache. As dobrichev has kindly indicated, I can get additional UA's directly from intermediate solver invocations

• improving the quality of the UA's deployed

It's that last point on which that I would appreciate some guidance. I assume from Mladen's comments above that I can be selective in my choice of UA's to increase their effectiveness. Would this involve testing them for their degree of overlap (cells in common)? I can see that having two UA's with many cells in common might indicate that we could discard one.

Am I on the right track here? (I do have a tendency to wander off! )

[dobrichev]

Do multiple-solution puzzles with less than 11 clues exist, with all solutions being morphs of the same solution grid?

[Mathimagics]

Do multiple-solution puzzles with less than 11 clues exist, with all solutions being morphs of the same solution grid?

Not sure if that's a hint or not ... is the question related to MODE_EDIFFERENT in GridChecker's solver? That could provide the answer to this question ...

[Leren]

Here's an oddity. Whilst doing work for the 12 clue project I came across this - an "almost 11 clue puzzle". It only has 3 solutions.

12.......3.............45....6.....5..............7..8.......6.................2.

The 3 solutions are

124653789365789412789214536836491275971528643452367198518942367297136854643875921
124653789365789412789214536836941275971528643452367198518492367297136854643875921
124653789365978412879214536936841275781529643452367198518492367297136854643785921

Anybody else found something similar ?

Leren

[Leren]

Wow, I've even beat that, just discovered an 11 clue puzzle with just 2 solutions : 12.......3.............45....6...........6..........278.........................8

The 2 solutions are :

124568739365917842789234516276491385538726491491853627817642953653189274942375168
124568739365917842789234516276491385538726491941853627817642953653189274492375168

Maybe they are more common than I thought.

Leren

[Serg]

Hi, Leren!

Wow, I've even beat that, just discovered an 11 clue puzzle with just 2 solutions : 12.......3.............45....6...........6..........278.........................8

The 2 solutions are :

124568739365917842789234516276491385538726491491853627817642953653189274942375168
124568739365917842789234516276491385538726491941853627817642953653189274492375168

Maybe they are more common than I thought.

You can see unhitted UA set U4 (more strictly speaking: "2-digit strongly minimal bi-valent U4 UA set").

Let's "subtract" both solutions from each other - retain cell values when those cells contain different digits, otherwise - discard them. We'll get

.............................................49.........................94.......
.............................................94.........................49.......

The same in two-dimensional view:

Code: Select all

     Solution 1              Solution 2
+-----+-----+-----+     +-----+-----+-----+
|. . .|. . .|. . .|     |. . .|. . .|. . .|
|. . .|. . .|. . .|     |. . .|. . .|. . .|
|. . .|. . .|. . .|     |. . .|. . .|. . .|
+-----+-----+-----+     +-----+-----+-----+
|. . .|. . .|. . .|     |. . .|. . .|. . .|
|. . .|. . .|. . .|     |. . .|. . .|. . .|
|4 9 .|. . .|. . .|     |9 4 .|. . .|. . .|
+-----+-----+-----+     +-----+-----+-----+
|. . .|. . .|. . .|     |. . .|. . .|. . .|
|. . .|. . .|. . .|     |. . .|. . .|. . .|
|9 4 .|. . .|. . .|     |4 9 .|. . .|. . .|
+-----+-----+-----+     +-----+-----+-----+

The group of 4 cells (r6c1, r6c2, r9c1, r9c2) form UA set - changing cells digits to opposite ("4" to "9" and otherwise) preserves validity of rows r6 and r9, columns c1 and c2, boxes B4 and B7, p-sets p7 and p8.

To get valid SudokuP puzzle you must break this UA set by selecting 1 clue cell from r6c1, r6c2, r9c1, r9c2, because clue cell prohibits changing of cell's content. (And you'll get valid 12-clue SudokuP puzzle.)

Serg