The New Sudoku Players' Forum

[Mathimagics]

.
Thanks to blue's Canonical Form for SudokuP, we now have a catalog of the 214,038,113 P-different SudokuP grids, and a catalog of the 53,666,689 PF-different SudokuP grids.

We can now proceed with Min Clue Phase 1 ...

Nice work, blue, you are a scholar and a gentleman!

[coloin]

That sounds good ....
my initial alternative approach is as ever not completely viable ... so rather of academic interest ...

At the 8 clue stage [ one of each clue]
these are the ED ways - and then add 2 clues to (not) get a 10, or, potentially, at greater cost, add 3 clues to get a valid sudoku-dg 11.

8 clue transversal - 1
7plus1 - 39
6plus2 - 2178
5plus3 - 23420
4plus4 - 79284

At the 6plus2 level - my puzzle maker program can add 2 clues and test [normal sudoku] at 75 /minute
so 100,000 subgrids would take a day
Adding 2 clues with an additional programmed constraint would potentially be at least 10 % quicker - but my program isn't adaptable - by me.

Adding 3 clues takes significantly longer - under 2 minute per subgrid
Given that the published 11-clue sudoku-dg have a 6clue transversal plus 5 clues, potentially all these 11s could be found. [in < 3 days]

Anyway - did you decide how many of the MC grids you need to test ? 1,5,73 or 648 ! ?

[Mathimagics]

did you decide how many of the MC grids you need to test ? 1, 5, 73 or 648 ! ?

Now that we have a CFP (Canonical Form for SudokuP) tool, this is easily checked. The 73 P-isotopes that I counted actually reduce to just 6 P-different cases (my isotope-counting procedure did not check for equivalences within the isotope sets).

Here they are, with the number of P-equivalent forms:

Code: Select all

  1: 123456789456789123789123456231564897564897231897231564312645978645978312978312645
  2: 123456789564897231978312645645978312789123456231564897897231564312645978456789123
  4: 123456789456789123789123456564897231897231564231564897978312645312645978645978312
 12: 123456789456789123789123456231564897564897231897231564645978312978312645312645978
 18: 123456789456789123789123456231564897564897231897231564312645978978312645645978312
 36: 123456789456789123789123456231564897897231564564897231645978312312645978978312645


Interestingly, the same result is obtained for PF-equivalence, so the number of {MC} forms that we will actually test is 6.

[coloin]

as ever - one possibly gets caught out
this valid 11-clue sudoku-dg puzzle

Code: Select all

+---+---+---+
|1.2|...|...|
|..3|...|...|
|...|...|..4|
+---+---+---+
|.4.|.5.|...|
|.6.|...|...|
|...|...|.1.|
+---+---+---+
|.7.|...|...|
|...|.8.|...|
|...|...|7..|
+---+---+---+


has a 6-transversal .... but

Code: Select all

+---+---+---+
|..2|...|...|
|...|...|...|
|...|...|..4|
+---+---+---+
|...|.5.|...|
|.6.|...|...|
|...|...|.1.|
+---+---+---+
|...|...|...|
|...|...|...|
|...|...|7..|
+---+---+---+


moving the 6 in r5c2 to r5c1

Code: Select all

+---+---+---+
|..2|...|...|
|...|...|...|
|...|...|..4|
+---+---+---+
|...|.5.|...|
|6..|...|...|
|...|...|.1.|
+---+---+---+
|...|...|...|
|...|...|...|
|...|...|7..|
+---+---+---+


can / do we get an equivalent valid puzzle by adding 5 more clues ? I'm thinking not.

[blue]

can / do we get an equivalent valid puzzle by adding 5 more clues ? I'm thinking not.

This is valid. It's an isomorph of Ocean's 4th puzzle.

Code: Select all

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

[Leren]

At the risk of being labelled a buttinsky here I just had a fun day coding up a SudokuP solver.

What was interesting, was that most of the puzzles in this thread so far solve with singles or basics. The only exceptions being Ocean's puzzles 5 and 10.

Here are blue's puzzles with some redundant clues removed.

Code: Select all

.........
.........
.........
.........
.....8..9
...631.87
.........
...2..643
...46.27.


...8.6.54
...92.863
.........
46.......
389......
.........
215......
.74......
.........

The first one solves with singles and basics and the second with singles only.

Could any of this actually be useful ? Possibly. If your objective is to prove that a 10 clue puzzle exists, you could do a "quick and dirty" survey first, using only singles and basics, which could speed up your process.

If your objective is to prove that no 10 clue puzzle exists I suppose you would be wasting your time. Well, I had fun anyway.

Leren

[coloin]

Hi Leren if you have coded up a SudokuP solver - that is good - there doesn't seem to be one freely available to non-coders ! [like me]
Those puzzles always had the potential to have redundant clues removed. There is much room for development for harder puzzles for example.
In the search for a 10-puzzle - a "quick and dirty" search for 11-puzzles would be appropriate - and the final test for non-minimality for a 10 would be the approach much used in the past !

Going back to making those 11-puzzles
Clearer thoughts will conclude that taking one of those puzzles and their subpuzzles - it will only have the isomorphic swaps which keep the SudokuP solution grid valid.
Each SudokuP puzzle will have the band swaps 6^2 at least .....actually as has been said before 2 x 6^4 = 2592
[1. Transposing - 2 ways.
2. Permutations of 3 bands - 6 ways.
3. Permutations of 3 stacks - 6 ways.
4. The same permutations of rows in every band - 6 ways.
5. The same permutations of columns in every stack - 6 ways. ]

But some SudokuP solution grids have more of these than others - depending on the band for example -a simple single column swap maintains sudoko-P property..

So clearly there may be many more than the 4 x "ED" SudokuP 6-transversals
[ perhaps each will have 6^4 single row/column swaps which potentially interfere with the Sudoku-P property]..... or maybe there really is just one ?

Do the 10 posted 11-puzzles come from 5 different sudoku-SF equivalent grids - or 10 different sudoku-S equivalent ones ... that's my other question ?

[Mathimagics]

Leren, coloin

If you're running Windows, I have made a SudokuP version of Brian Taylor's BB solver, adapted from a standard Sudoku version provided by dobrichev, which I could make available. Would that be useful?

Regarding ease of solving vs minimum clues, I believe it is true of standard Sudoku, too, that less clues doesn't mean harder puzzles ... often the reverse is true

[EDIT] I have posted executables for Win32/64 here.

[Mathimagics]

Do the 10 posted 11-puzzles come from 5 different sudoku-SF equivalent grids - or 10 different sudoku-S equivalent ones ... that's my other question ?

If this helps, here are the SudokuP canonical forms, there are 6 P-different and 3 PF-different ones in the 10:

Code: Select all

 P-different = 6
  2: 123456789457892316986731452594317268231648975678529143842975631769183524315264897
  2: 123456789457298631896317452568972314974183526231645978645831297312769845789524163
  1: 123456789457298136869173542378942615945761823216385497594837261682519374731624958
  2: 123456789457893162968217453631978245589624371742531896894362517216745938375189624
  2: 123456789457398612986271453574912368261783945398645127645837291839124576712569834
  1: 123456789457289631986371542678512394514793826239864157841937265362145978795628413

 PF-different = 3
  4: 123456789457398612869127534698512347735964821241783956974831265586249173312675498
  4: 123456789457298136968371452395817264812643975746529813671932548589764321234185697
  2: 123456789457289631986371542678512394514793826239864157841937265362145978795628413


[Leren]

Mathemagics

Downloaded your solver but Windows 10 doesn't like it, so I won't proceed further on that front.

In any event I was mainly interested in the differences between a SokokuP solver and an ordinary Sudoku solver. As SokokuP solving is not a mature subject like Sudoku solving there may be discoveries (hopefully shortcuts) to be made.

FWIW, what I did was adapt my Sudoku solver by:

1. Increasing the groups of cells that can see each other from 20 to 24 (obvious).

2. Adding nine P houses (my name) and allowing them to have naked and hidden pairs, triples and quads (also obvious).

3. Adding two new basic move - P House/row/column intersection moves.

4. Ignoring Sudoku uniqueness moves (they cause errors - obvious when you relalise that the solution to Ocean's puzzle 5 is not Sudoku unique but it is SodokuP unique).

5. All other ordinary Sudoku moves appear to be OK for Sudoku P (at least I think so).

For the puzzles tested I got a few hits on P house naked doubles, but the hit rate on P House/row/column intersections was huge - much higher than I expected and very productive.

Anything I've missed ? If this is boring you just ignore me.

PS - What might be more interesting to me is if you could make available the list of 53 million PF different grids, unless you regard that as proprietary.

Coloin

On page 2 of this thread blue mentioned that the second 5 of Ocean's puzzles were F transforms of the first 5. They are different but solve with similar ease/difficulty in each case.

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 ?

Leren

[coloin]

I will try the solver too......

I think what the results mean is that there are found 6 P-different SudokuP puzzles
Each puzzle has an isomorphic brother which is reachable by blues transformation swapping the triples.
So depending on how you view things - i would say that there are known 3 different sudokuP puzzles.

The presumed paucity of 11-puzzles makes a 10-puzzle extremely unlikely.

Each SudokuP puzzle / grid has 6^4 x 2 isomorphs - this preserves the SudokuP characteristic.

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 !
I suspect a minlexing tool would be needed too.

I think the bad news is that to search every essentially ED 6-transversal for an 11- we would have to add the 2 new clues and then add any 3.....
We would then have to morph the potential puzzles 6^6 / 6^2 times ? ....and then solve - how fast is the solver again ?

[coloin]

Except on a little thought ... was it just chance that i picked a row swap out of the many i could have chosen - and blue found a different puzzle ?.
Maybe as each puzzle has so many isomorphs - we only need to search one each of the four 6-transversals after all .....but the sudoku gods are ususally not that kind, I have learnt .....

[Mathimagics]

The presumed paucity of 11-puzzles makes a 10-puzzle extremely unlikely.

The general assumption we make is that no 10-clue puzzle exists, but as discussed earlier on, this has not been demonstrated conclusively, as Russel & Jarvis did for 16-clue Sudoku. So I thought I that I would step up to the plate on this question.

But it is not entirely out of the question that a 10-clue puzzle might be found. It is not easy finding 11-clue puzzles, so one expects it to be harder to find 10-clue ones, should they exist. Interestingly, it only takes a few changes to the PSETS (see my SudokuPX thread) to turn a 14-clue puzzle into a 10-clue, or even an 8-clue puzzle. So a 10-clue SudokuP may well exist, just hard to track down.

I suspect a minlexing tool would be needed too.

blue has given us that, a SudokuP CF procedure. I can give you an EXE wrapper for that, if you like.

We would then have to morph the potential puzzles 6^6 / 6^2 times ? ....and then solve - how fast is the solver again ?

Thanks to Brian Turner, and dobrichev, I get 64K SudokuP puzzles/sec with uniqueness testing, reduced forms, on a 4.7GHz CPU. That's excluding I/O, of course, I load 100 reduced forms, then solve them over and over. But it is fast.

[Mathimagics]

.
Phase 1, which aims to eliminate as many candidate grids as cheaply as possible, is now complete. You can appreciate the size of the problem computationally by the fact this "express" culling process still took 4 processes 3.5 days to complete.

But we have eliminated 77% of the grids from consideration as 10-clue candidates, as this table shows:

Code: Select all

Phase 1:
  mc =  0:         4
  mc =  2:         3
  mc =  3:        19
  mc =  4:       198
  mc =  5:      2118
  mc =  6:     15961
  mc =  7:    128612
  mc =  8:    691034    1%
  mc =  9:   2928539    5%
  mc = 10:   8032026   14%
  mc = 11:  14101485   26%
  mc = 12+: 27766690   51%
  ------------------
            53666689


The minimum clue count (mc) is the lower-bound obtained by finding cliques (sets of disjoint UA's), this search doesn't find all cliques, so in most cases the actual minimum clue number is higher, and the actual minimum clue count required to hit every UA is higher still.

I have produce a 2nd version of the clique finder that is more aggressive, and while slower than the method used in Phase 1, is still much quicker than enumerating the Hitting Sets, so I am running that as Phase 2, on the candidates not eliminated in Phase 1. This process should eliminate another 10% from 10-clue consideration.

That should take a few days as well.

I also looked at the cases where the UA process didn't identify anything useful. I looked at the 26 cases with mc < 4. These correspond to very low numbers of UA sets. In most cases I am able to improve the UA count by selecting the best candidate from the 10368 PF-equivalent forms. This will make the Hitting Set algorithm (Phase 3) more effective, although it has little impact on the clique-based MC values we get for the Phase 1/2 calculations.

But how about this? All test cases have isotopes with more UA's available, with the notable exception of the 4 cases where we found no UA's at all (mc = 0). These 4 have NO isotope with any usable UA's. That's a little bit mind-blowing.

I list them here. One thing I have noticed is that all four have distinct values along both diagonals. Is this significant?

[ † EDIT] It has come to my attention that I have been overlooking something blindingly obvious! (See my post further down for details)

Code: Select all

123 | 456 | 789   123 | 456 | 789   123 | 456 | 789   123 | 456 | 789
456 | 897 | 231   456 | 897 | 312   564 | 897 | 231   564 | 897 | 231
978 | 312 | 456   978 | 231 | 456   978 | 312 | 645   978 | 312 | 645
---------------   ---------------   ---------------   ---------------
564 | 978 | 312   564 | 978 | 231   645 | 978 | 312   647 | 938 | 512
789 | 123 | 564   789 | 123 | 564   789 | 123 | 456   389 | 125 | 476
231 | 564 | 897   312 | 564 | 897   231 | 564 | 897   251 | 764 | 893
---------------   ---------------   ---------------   ---------------
897 | 231 | 645   897 | 312 | 645   897 | 231 | 564   895 | 271 | 364
312 | 645 | 978   231 | 645 | 978   312 | 645 | 978   712 | 643 | 958
645 | 789 | 123   645 | 789 | 123   456 | 789 | 123   436 | 589 | 127


[Mathimagics]

.
While I think of it, I should mention that I am keeping an audit trail of what happens to every grid. I even wrote a "random audit" function, which picks eliminated grids from the log files at random, which are written along with the 12-member clique that supposedly caused that elimination, and verifies that

• the clique contains 12 or more disjoint UA's

• each UA is valid, ie every clue in the UA acts as expected