The New Sudoku Players' Forum

by **Mathimagics** » Thu Mar 08, 2018 4:05 am

.
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?

by **coloin** » Thu Mar 08, 2018 9:04 am

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

by **Leren** » Thu Mar 08, 2018 9:23 am

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

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.

by **blue** » Thu Mar 08, 2018 10:25 am

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.

by **Leren** » Thu Mar 08, 2018 11:28 am

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

by **Mathimagics** » Fri Mar 09, 2018 4:45 pm

.
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

by **blue** » Fri Mar 09, 2018 5:42 pm

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.

by **blue** » Fri Mar 09, 2018 6:26 pm

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)) = X D(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 D derive: 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.

by **blue** » Fri Mar 09, 2018 6:52 pm

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 ?

by **Mathimagics** » Fri Mar 09, 2018 8:35 pm

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.

by **Leren** » Fri Mar 09, 2018 8:59 pm

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

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

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

Leren

by **coloin** » Sun Mar 11, 2018 10:56 am

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

by **Mathimagics** » Sun Mar 11, 2018 5:15 pm

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

by **Leren** » Sun Mar 11, 2018 8:07 pm

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

by **blue** » Sun Mar 11, 2018 8:59 pm

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.

The New Sudoku Players' Forum

SudokuP - Min Clue Project

Re: SudokuP - Min Clue Project

Re: SudokuP - Min Clue Project

Re: SudokuP - Min Clue Project

Re: SudokuP - Min Clue Project

Re: SudokuP - Min Clue Project

Min Clues for any Sudoku Variant

Re: Min Clues for any Sudoku Variant

Re: SudokuP - Min Clue Project

Re: SudokuP - Min Clue Project

Re: Min Clues for any Sudoku Variant

Re: SudokuP - Min Clue Project

Re: SudokuP - Min Clue Project

Re: SudokuP - Min Clue Project

Re: SudokuP - Min Clue Project

Re: SudokuP - Min Clue Project