## SudokuP - Min Clue Project

For fans of Killer Sudoku, Samurai Sudoku and other variants

### Re: SudokuP - Min Clue Project

.
Ok, public humiliation time again!

It should be obvious to anybody paying attention that, even if there seem to be no valid (A,B) cycles, such as in the allegedly "zero-UA" examples above, one can always resort to combining them, ie. EVERY (A, B) can be exchanged in every row and we have simply relabelled the grid, so the result is always a SudokuP, and the 18 cells thus always form a UA set of size 18.

If all else fails, ie we find no smaller cycles, then we still have C(9,2) = 36 UA-18's that we can use ...

Is that dobrichev I hear laughing?

Mathimagics
2017 Supporter

Posts: 1901
Joined: 27 May 2015
Location: Canberra

### Re: SudokuP - Min Clue Project

Yes , in normal sudoku the 2-clue unavoidables [with 18 clues] need 1,2,3 or 4 clues.
There are 36 pairs
And there will always be 4 disjoint pairs of 18-clues
coloin

Posts: 2216
Joined: 05 May 2005
Location: Devon

### Re: SudokuP - Min Clue Project

Here is a list of forty 11 clue SudokuP puzzles, based on the ten previously found by Ocean, and the F group theory put forward by Mathemagics, blue and others.

Hidden Text: Show
1.2........3..............4.4..5.....6..............1..7...........8..........7.. O1
1.2..3....................4.4..6.....5..............1..7...........8..........7.. F(O1)
1.........................7.47.5.....6...8..........1.2........3..............4.. G(O1)
1.....2.....45.......7...........3.....6.........8............4.....1.....7...... E(O1)
1.2........3..............4.4..5.....6..7...........2..8......................8.. O2
1.2..3....................4.4..6.....5..7...........2..8......................8.. F(O2)
1.........................8.48.5.....6..7...........2.2........3..............4.. G(02)
1.....2.....45.......8...........3.....67.....................4.....2.....8...... E(O2)
1.2........3..4...........5.5..6.....7..............1..8......................8.. (O3)
1.2..3........4...........5.5..7.....6..............1..8......................8.. F(O3)
1.........................8.58.6.....7..............1.2........3..4...........5.. G(O3)
1.....2.....56.......8...........34....7......................5.....1.....8...... E(O3)
1.2........3..4...........5.5..6.....7..............2..8......................8.. O4
1.2..3........4...........5.5..7.....6..............2..8......................8.. F(O4)
1.........................8.58.6.....7..............2.2........3..4...........5.. G(O4)
1.....2.....56.......8...........34....7......................5.....2.....8...... E(O4)
1.2......3..4...........5...6..7.....7..............2..8......................8.. O5 = F(10)
1.23........4...........5...6..7.....7..............2..8......................8.. F(O5) = O10
1........3..4...........5.8.68.7.....7..............2.2.......................... G(O5)
1.....2.....67.......8.....34..........7................5...........2.....8...... E(O5) = G10(T)
1.2..3....................4.4..5.....6..............1..7...........8..........7.. O6 = R(FO1)
1.2........3..............4.4..6.....5..............1..7...........8..........7.. F(O6)
1.........................7.47.5.....6...8..........1.2..3....................4.. G(O6)
1.....23....45.......7.................6.........8............4.....1.....7...... E(O6)
1.2..3....................4.4..5.....6..7...........2..8......................8.. O7 = R(FO2)
1.2........3..............4.4..6.....5..7...........2..8......................8.. F(O7)
1.........................8.48.5.....6..7...........2.2..3....................4.. G(O7)
1.....23....45.......8.................67.....................4.....2.....8...... E(O7)
1.2..3........4...........5.5..6.....7..............1..8......................8.. O8 = R(FO3)
1.2........3..4...........5.5..7.....6..............1..8......................8.. F(O8)
1.........................8.58.6.....7..............1.2..3........4...........5.. G(O8)
1.....23....56.......8............4....7......................5.....1.....8...... E(O8)
1.2..3........4...........5.5..6.....7..............2..8......................8.. O9 = R(FO4)
1.2........3..4...........5.5..7.....6..............2..8......................8.. F(O9)
1.........................8.58.6.....7..............2.2..3........4...........5.. G(O9)
1.....23....56.......8............4....7......................5.....2.....8...... E(O9)
1.23........4...........5...6..7.....7..............2..8......................8.. O10 = F(O5)
1.2......3..4...........5...6..7.....7..............2..8......................8.. F(O10) = O5
1..3........4...........5.8.68.7.....7..............2.2.......................... G(O10) = E(O5) T
13....2.....67.......8......4..........7................5...........2.....8...... E(O10)

O1 - O10 refer to Ocean's ten puzzles and the transformations F, G and E have the meanings they have here.

Contrary to blue's assertion, only Ocean's puzzles 5 and 10 were related by an F transformation. The other pairs looked like they were, but there were minor differences, so Ocean had actually found 9 different non F-Group related 11 clue SudokuP puzzles. For completeness I've included all ten puzzles and their F, G and E transforms, but there are only 36 different puzzles.

Also, as public humiliation is not my preferred MO I'd better say I have not extensively checked these puzzles for isomorphisms.

Leren

<Edit> That public humiliation statement I made above was a good tactical move, as blue has pointed out that, whilst O6 was, strictly speaking, not F(O1) it was a simple isomorphism of it. Here are two puzzles compared

1.2..3....................4.4..6.....5..............1..7...........8..........7.. F(O1)
1.2..3....................4.4..5.....6..............1..7...........8..........7.. O6

A simple relabelling of the clues 5 and 6 in r4c5 and r5c2 is the only difference between the two, so they are isomorphisms, and thus not essentially different.

Similar comments apply to O2 and F(O7), O3 AND F(O8) and O(4) and F(O9). I've denoted this by O6 = R(F(O1)) etc and thus the number of essentially different (in the ordinary Sudoku sense) puzzles is reduced to 20.
Last edited by Leren on Thu Mar 08, 2018 8:33 pm, edited 3 times in total.
Leren

Posts: 4338
Joined: 03 June 2012

### Re: SudokuP - Min Clue Project

Leren wrote:Contrary to blue's assertion, only Ocean's puzzles 5 and 10 were related by an F transformation. The other pairs looked like they were, but there were minor differences.

You're right, but the minor differences can be removed by a "relabling" transformation that swaps the digits in r4c5 and r6c2.
There really are only 5 "essentially distinct" puzzles.

For completeness I've included all ten puzzles and their F, G and E transforms, but there are only 38 different puzzles.
[snip ... ] I'd better say I have not extensively checked these puzzles for isomorphisms.

The last part is confusing, since E,F and G are isomorphisms (for SudokuP).
In other words, F(X) is isomorphic to X, by definition ... and so on.
blue

Posts: 909
Joined: 11 March 2013

### Re: SudokuP - Min Clue Project

Hi blue, I take your point about the puzzle pairs being F transforms plus a minor relabelling for the first 4 pairs. Also, I realised two that two pairs of puzzles were transposes, so I reduced the number of distinct puzzles to 36 whilst you were posting.

I'm still confused about what it means for two F Group SudokuP puzzles to be "isomorhpisms". For example, puzzles 5 and 10 really do solve fundamentally differently (for me) and I'm not used to that being the case for isomorphisms. The only thing I can think of is that there is some deficiency in my (quickly cobbled together) SodokuP solver that doesn't prevent the two puzzles being solved correctly, but stops them being solved in the same way.

Leren
Leren

Posts: 4338
Joined: 03 June 2012

### Min Clues for any Sudoku Variant

.
This is probably nothing new, but we can use UA-18's to prove that no puzzle for any Sudoku variant can have less than 8 clues.

By "Sudoku variant" I mean any puzzle whose solution is a Sudoku grid, and where any relabelling of a valid solution grid for the puzzle variant is also a valid solution grid. This is true for all variants that I can think of.

The proof goes like this:

• all solution grids have at least 36 UA sets of size 18 that correspond to swapping any pair of values (A, B) throughout the grid
• any clue-set (puzzle) must hit each of these sets
• the Hitting Set problem for these UA sets is the same for any grid (in graph-theoretical terms, the hypergraph defined by these 36 UA sets is identical for all grids)
• the minimum Hitting Set size for these UA sets is 8

Mathimagics
2017 Supporter

Posts: 1901
Joined: 27 May 2015
Location: Canberra

### Re: Min Clues for any Sudoku Variant

Mathimagics wrote:.This is probably nothing new, but we can use UA-18's to prove that no puzzle for any Sudoku variant can have less than 8 clues.

I don't know about the extension to Sudoku variants, but (otherwise) it's old news.
The usual claim is that a valid puzzle needs to have clues for at least 8 digits.
The usual proof, argues that if there were two digits with no clues, then swapping those digits in one solution, would produce a second solution.
blue

Posts: 909
Joined: 11 March 2013

### Re: SudokuP - Min Clue Project

Leren wrote:Hi blue, I take your point about the puzzle pairs being F transforms plus a minor relabelling for the first 4 pairs. Also, I realised two that two pairs of puzzles were transposes, so I reduced the number of distinct puzzles to 36 whilst you were posting.

You must have seen that, G(O10) = D(E(O1)) and E(O10) = D(G(O1)), where D is the transpose operation.

If you bring the relabeling transformations back in, the total count reduces to 20.
Each "1,E,F,G" puzzle for O1, has a "mate" among the "1,E,F,G" puzzles for O6, for example.

It's possible to prove that for (any) puzzles X and Y, if Y = m(F(X)), where 'm' is a relabeling transformation,
then also: F(Y) = m(X), G(Y) = m(D(E(X))) and E(Y) = m(D(G(X))).

The proof exploits a couple of points from this list of identity's:
Code: Select all
`D(D(X)) = E(E(X)) = F(F(X)) = G(G(X)) = XD(E(X)) = E(D(X)) = F(G(X)) = G(F(X))D(F(X)) = E(G(X)) = F(E(X)) = G(D(X))D(G(X)) = E(F(X)) = F(D(X)) = G(E(X))`

For the proof(s) ...
Code: Select all
`assume:   Y  =   m(F(X))derive: F(Y) = F(m(F(X))) = m(F(F(X))  = m(X)derive: G(Y) = G(m(F(X))) = m(G(F(X))) = m(D(E(X))) - connecting G(Y) with E(X), via Dderive: E(Y) = E(m(F(X))) = m(E(F(X))) = m(D(G(X))) - connecting E(Y) with G(X), via D`

------
Leren wrote:I'm still confused about what it means for two F Group SudokuP puzzles to be "isomorhpisms". For example, puzzles 5 and 10 really do solve fundamentally differently (for me) and I'm not used to that being the case for isomorphisms. The only thing I can think of is that there is some deficiency in my (quickly cobbled together) SodokuP solver that doesn't prevent the two puzzles being solved correctly, but stops them being solved in the same way.

The way you described things here, if one can be solved with singles, line/box or line/pset eliminations, and "tuples" (at least), then the other one should, too.
If you needed fish or chains, then what you would see, would depend on how far you pushed things.

Cheers,
Blue.
blue

Posts: 909
Joined: 11 March 2013

### Re: SudokuP - Min Clue Project

coloin wrote:I dont think anyone has really started searching on these puzzles via simple quick and dirty methods ... eg with {+2-2} - but i might be able to do that now I have a solver !

Leren wrote:As the number of P different SudokuP grids is about 4 times the number of PF different grids, does that suggest that there may be (at least) another ten 11 clue SudokuP puzzles not yet discovered ?

After about a day and a half times 4 cores, I can only find 9 new 11's.
They came in the 1st 3 hours, in a single core test run.

Code: Select all
`.2.45..........13........6.....9...........7............7..............5.....3...12..........79.......3...................1...........8.4.....67.............8......3...........82.1.79......................7.2............3...........6..4...............9......2....8..........4...........7................6.2......3..7.1..4..............6.....2...............53..8..............9.........77.1..........89...1........4.....3............6......7.89.....5....4...................2.......2........6...4.7.....2..........................3..5..........3.....8....96..4.............7.9.......3..6...2............6..............8.........1........4.7...8.....................69..........1...........3..5.............3.....1....97..4.....2.`

Leren, would you check these for "singles solvable", etc ?
blue

Posts: 909
Joined: 11 March 2013

### Re: Min Clues for any Sudoku Variant

blue wrote:.The usual claim is that a valid puzzle needs to have clues for at least 8 digits.
The usual proof, argues that if there were two digits with no clues, then swapping those digits in one solution, would produce a second solution.

Quite right, and indeed the argument applies to all variants. I even defined "variant" to imply that relabelling of solutions always gives a valid grid, so should have stopped right there!

Thanks, by the way, blue and Leren, for providing useful additional 11-clue cases. I will use these as additional test cases for the HS enumerator, ie to make sure it finds them all via Hitting Sets.

Mathimagics
2017 Supporter

Posts: 1901
Joined: 27 May 2015
Location: Canberra

### Re: SudokuP - Min Clue Project

Hi blue, congratulations on those new finds. You don't say whether you have checked these for isomorphisms . Here are my SudokuP solver's results with some brief (hopefully good enough at this stage) comments.

Hidden Text: Show
.2.45..........13........6.....9...........7............7..............5.....3... B1 Sudoku basics only
12..........79.......3...................1...........8.4.....67.............8.... B2 SP basics + simple chains
..3...........82.1.79......................7.2............3...........6..4....... B3 More difficult but no FC's
........9......2....8..........4...........7................6.2......3..7.1..4... B4 SP basics + 1 Skyscraper
...........6.....2...............53..8..............9.........77.1..........89... B5 SP basics + simple chains
1........4.....3............6......7.89.....5....4...................2.......2... B6 Forcing chains
.....6...4.7.....2..........................3..5..........3.....8....96..4....... B7 SP basics + 1 H wing
......7.9.......3..6...2............6..............8.........1........4.7...8.... B8 SP basics + Some simple wings
.................69..........1...........3..5.............3.....1....97..4.....2. B9 Forcing chains

Also, I've realised that I should extend my SudokuP solver by adding SudokuP equivalents to a lot of the non basic moves, but whether this changes the above results substantially is debatable.

One feature I do have in my SudokuP solver is that I can automatically create, for any SudokuP puzzle X : F(X), G(X) and E(X), so you can claim 36 new discoveries ! Here they are :

Hidden Text: Show
.2.45..........13........6.....9...........7............7..............5.....3... B1
.2.......45..........13..6...........9...........7......7..............3.....5... F(B1)
...4...........1...........2..59..........37.......6....7..............5.....3... G(B1)
.4.25........9..........7....1..3........7...........5.....6...................3. E(B1)
12..........79.......3...................1...........8.4.....67.............8.... B2
12..........79.3.........................1...........8.4..............8..67...... F(B2)
1...........7........3.....2.4.....6...9..........8...........7....1...........8. G(B2)
1..2.................4.6..7.7..9...........1...........3...............8....8.... E(B2)
..3...........82.1.79......................7.2............3...........6..4....... B3
..3....79.....8......2.1.........2...............7...........4..3...........6.... F(B3)
...............2...2............3..........767.4......3...........8..1..9........ G(B3)
......3...............3......2....81.....7........6......7..9..2...........4..... E(B3)
........9......2....8..........4...........7................6.2......3..7.1..4... B4
........8...........92...............4...........7..........7.1........46.23..... F(B4)
........6......2.3..7..........4...........7................9.2.........8.1..4... G(B4)
........9....4......6.....2..2...........7.....3............8...........7.....14. E(B4)
...........6.....2...............53..8..............9.........77.1..........89... B5
.....6.................2.......8.............53.....9....7.1..........89..7...... F(B5)
.......5...7......................3..8............8.9.........76.1...2.......9... G(B5)
...........5..3...........7......6.2...8.....7.....1................9.......8..9. E(B5)
1........4.....3............6......7.89.....5....4...................2.......2... B6
1..4.................3......6..89..........4...7..5....................2...2..... F(B6)
1........4.....3.2..........6........8...........4...........7..9.....5......2... G(B6)
1...........6....7.........4.3.........8..9.5..2...................4...........2. E(B6)
.....6...4.7.....2..........................3..5..........3.....8....96..4....... B7
...4.7.....6...........2...........5..............3.......8..4..3..........96.... F(B7)
.........4.......9..............3.....8.....6..4.........6.....7.....23..5....... G(B7)
.......6..............3....4.....7.2........3..98.6..................5.....4..... E(B7)
......7.9.......3..6...2............6..............8.........1........4.7...8.... B8
.......6.........27.9.3.......6....................8........7.........8..1..4.... F(B8)
......7...6.........7....8.........1......3.46....8.........9..............2..... G(B8)
..7.....9..............1........3...6.............4......6...2...8......7...8.... E(B8)
.................69..........1...........3..5.............3.....1....97..4.....2. B9
......9................6.....1...........3........5.......1..4..3..........97..2. F(B9)
.................99.............3.....1.....7..4.....2.1...........3.65.......... G(B9)
...............1......3............6.......35..91.7...9....................4.2... E(B9)

Leren

PS : It was a simple exercise for me to create a Morph of your puzzle B1 such that r1c1 = 1. So M(B1) = 15..2..........43........6..9..............7...............7...........5..3......

So, to get to an 11 clue puzzle with r1c1 = 1 there are 2 steps. 1. Your search algorithm that eventually finds B1 2. Simple Morph of B1 to get M(B1) with r1c1 = 1.

But what if you always start your search algorithm by assuming r1c1 = 1. Wouldn't you eventually find M(B1) directly ?

The point is that by always assuming r1c1 = 1 wouldn't your search algorithm be faster (because you have removed a degree of freedom) ?

Leren

PPS : Well, here they are. Blue's puzzles Morphed so that r1c1 = 1. Should this be a "standard" way to present a new discovery ? All of Ocean's puzzles were presented this way.

Hidden Text: Show
15..2..........43........6..9..............7...............7...........5..3...... M(B1)
12..........79.......3...................1...........8.4.....67.............8.... M(B2) = B2
1...........8..3.297.......................7...2..........1...........6..4....... M(B3)
1.................7.....8................4...4.........36....2.....1......2.....9 M(B4)
1......2....3.9......5.......9........8................7.....6.....8.....1....... M(B5)
1........4.....3............6......7.89.....5....4...................2.......2... M(B6) = B6
1...........2..7.4.....................3...........5...3...........19.8........4. M(B7)
1.........3....94.7....8.....2..............8....................6..........6...7 M(B8)
1..............49......9....................3....3...........1.......27..6..5.... M(B9)

Leren
Leren

Posts: 4338
Joined: 03 June 2012

### Re: SudokuP - Min Clue Project

Three ways that I can see to make min clue SudokuP puzzles - say 11 clues

1. Remove grids that cant have an 11, scan every other grid for a 11 - using hitting sets of UAs.
2. Randomly generate 13s and successively reduce these with a thorough {-1+1} to get a non-minimal 13 -> 12 ..... and repeat
3. Generate ED 8 clue subpuzzles [all with different clue values] and add 3 clues. Morph each 6^4 times and test for validity.

Its not looking good for finding a 10-clue
coloin

Posts: 2216
Joined: 05 May 2005
Location: Devon

### Re: SudokuP - Min Clue Project

coloin wrote:Its not looking good for finding a 10-clue

We don't really expect to find a 10-clue SudokuP. We want to prove that such a beast exists or not.

coloin wrote: Remove grids that cant have an 11, scan every other grid for a 11 - using hitting sets of UAs.

Actually I was just about to post the results of my initial foray into the actual generation of Hitting Sets and testing the associated puzzle sets.

I had hoped to piggy-back the enumeration of 11-clue puzzles along with the 10-clue testing, but that now looks to be an impossible dream.

I tested the process (generate puzzles using HSets and test-solve) using one of the known cases, namely the first one in the original set of 10:

Code: Select all
`182764593493528176657193284841259637765831942329476815976315428214687359538942761`

The process reported these known cases (so is on the right track). There may be more, the job is only 70% complete:

Code: Select all
`1.2........3..............4.4..5.....6..............1..7...........8..........7..1.2........3..8...........4.4..5.....6..............1..7......................7..`

The largest set of UA's that I could assemble (using GridChecker, as my simplistic UA generator proved to be inadequate) was 124, from which I obtained:

• 1,130 HSets of size 8
• 375,331 HSets of size 9
• 27,266,402 Hsers of size 10
• 620,690,909 HSets of size 11

These are "net" figures, ie the HSets of size 9 do not include any repeats of size 8, etc.

The first 3 cases need to be multiplied by the "free cell multiplier", for size 8 this is C(73, 3) = 62,196, for size 9 it's C(72,2) = 2,556, and for size 10 it's 71.

So the total number of 11-clue puzzle candidates that need to to be tested is (1130 x 62196) + (375331 x 2556) + (27266402 x 71) + 620690909 = 3,586,232,967 .

Even at 50,000 grids/second (and we have to to add the overhead of generating the HSets, a non-trivial exercise), that's roughly one whole day to completely enumerate.

If this "profile" is typical of an 11-clue puzzle, and it does appear to be so, then that's the death sentence for exhaustive enumeration!

The same job runnng in 10-clue mode, where the multipliers are more favourable, invoves (1130 x 2628) + (375331 x 72) + 27266402 = 57,259,874 10-clue puzzles to test.

This only took about 35 minutes, which I can live with, so the project remains alive and kicking.

Months I can do, years is well outside my comfort zone!

Mathimagics
2017 Supporter

Posts: 1901
Joined: 27 May 2015
Location: Canberra

### Re: SudokuP - Min Clue Project

Mathemagics wrote : I had hoped to piggy-back the enumeration of 11-clue puzzles along with the 10-clue testing, but that now looks to be an impossible dream.

Not quite sure what you mean by that if you manage to enumerate all 11 clue puzzles haven't you also solved the 10 clue question ?

It seems to me that all 10 clue puzzles must have a number of 11 clue extensions, with the 11th clue being redundant. Now assume that you have enumerated all 11 clue puzzles. Then, for each such puzzle, all you have to do is remove one clue and run the result through a solution counter. If you never get a 1 then you have proved that no 10 clue puzzles exist. If you do get a 1 then you have found a 10 clue puzzle. Isn't that right ?

Even if the 10 clue puzzle problem is not resolved, the enumeration of all 11 clue puzzles is, to me, an equally meritorious achievement, and should be completed.

That's why I'm following blue's 11 clue searching effort with interest. He hasn't said exactly what he is doing, but if he is searching in such a way that he can be certain that all 11 clue puzzles will eventually enumerated then there you have it.

So far, we appear to have found 14 essentially different 11 clue puzzles (and trivially their 42 F group brothers); 5 by Ocean and 9 by blue.

Also, if some search algorithm is devised that is exhaustive, but may take, say, months, then presumably it could be broken up into segments, and farmed out to willing participants to use their idle PC time to shorten the search time.

Leren

PS - the PS in my previous post was wrong, but I did manage some solving progress. I originally found that Blue' s B4 and F(B4) were solvable with SudokuP basics plus a skyscraper, but G(B4) and E(B4) required a multi digit wing. That didn't sound right but the solution was simple. I added a new move, a SudokuP analogue of a skyscraper, and that made the required eliminations in G(B4) and E(B4). So all members of the F group for B4 are solvable in essentially the same way, but I suspect blue knew that anyway

Leren
Last edited by Leren on Sun Mar 11, 2018 9:01 pm, edited 1 time in total.
Leren

Posts: 4338
Joined: 03 June 2012

### Re: SudokuP - Min Clue Project

Hi Leren,

I've been meaning to thank you for checking the solving details for the new 11's.
Thank you !

Leren wrote:(...)
So all members of the F group for B4 are solvable in essentially the same way, but I suspect blue knew that anyway

Yes, but it's nice to see that you've confirmed it.

Leren wrote:That's why I'm following blue's 11 clue searching effort with interest. He hasn't said exactly what he is doing, but if he is searching in such a way that he can be certain that all 11 clue puzzles will eventually enumerated then there you have it.

I was using the 2nd method that coloin outlined here -- except that I was starting from 16's and working down to 12's, and hoping for an 11 or two to come out of the 12's. I've more or less given up on finding anything new. I'm trying one last thing now, but it's looking like it won't pan out.

Cheers.
blue

Posts: 909
Joined: 11 March 2013

PreviousNext