The New Sudoku Players' Forum

[Moschopulus]

The 35 was found in the canonical grid, which has a 19 but no 18.

Would there be a higher chance of finding a 36 in a grid which has a 20 but no 19?

145726983837495261926381574293874156581269347674153892318547629459632718762918435

[coloin]

Thanks Mosch.
It does sound logical.......
Have you a list of all the no 19 grids ?
Are there only 2 ?

The trouble is I didnt know which grid to look in first - probably best to totally explore the canon grid.......perhaps we have........I think 35 is an amazing result though. And then there is the isomorph puzzles which I am going to use try and get a 36...

However there could well be another grid out there which just happens to have 36 unavoidable sets which are exclusive to the 35 other given clues.........I think it is highly probable because each grid has now 1*e^63 ways to fill in any 35 clues.....but are we ever going to find it.?

The original Oceanmax grid with 33s was spectactularly average ! It had an 18 clue minimal - and ten of those 18 clues were also in the maximal 33 ! [Explain that !]

Your miracle grid was exceptional in having so many 19s, so perhaps it is also worth analysing.

I have looked at the SF grid but not got more than a 31. !

Red Ed has suggested a grid
http://forum.enjoysudoku.com/viewtopic.php?t=3177&start=45

Code: Select all

157|629|834
826|743|591
493|185|267
---+---+---
268|491|375
934|257|618
571|836|942
---+---+---
385|914|726
619|572|483
742|368|159

I presume Ocean's computor is continuing to scan the canonical for a 36 !

C

[Ruud]

Here are two minimal sudokus with 35 clues:
#
100056780780120450400700103201064800060090001800200500302645000640070000000002000
103006780780120450400700103201064800060090001800200500302645000640070000000002000
#

Minimal as in: Not able to remove a clue without causing a puzzle with multiple solutions?

That would make the following 2 non-existent?

Code: Select all

100006780780120450000700103201064800060090001800000500302645000640070000000002000
103006780780100450000700103001064800060090001800000500302645000640070000000002000

Ruud.

[coloin]

Here are two minimal sudokus with 35 clues:

Code: Select all

+---+---+---+
|1..|.56|78.|
|78.|12.|45.|
|4..|7..|1.3|
+---+---+---+
|2.1|.64|8..|
|.6.|.9.|..1|
|8..|2..|5..|
+---+---+---+
|3.2|645|...|
|64.|.7.|...|
|...|..2|...|
+---+---+---+
 and
+---+---+---+
|1.3|..6|78.|
|78.|12.|45.|
|4..|7..|1.3|
+---+---+---+
|2.1|.64|8..|
|.6.|.9.|..1|
|8..|2..|5..|
+---+---+---+
|3.2|645|...|
|64.|.7.|...|
|...|..2|...|
+---+---+---+

Code: Select all

Minimal as in: Not able to remove a clue without causing a puzzle with multiple solutions?

Yes.....which makes your puzzles have multiple solutons....

That would make the following 2 non-existent?

Code: Select all

100006780780120450000700103201064800060090001800000500302645000640070000000002000
103006780780100450000700103001064800060090001800000500302645000640070000000002000

.......which they do, 15 and 55 respectively.

That Ocean has found a 35 - is remarkable.

C

[Ocean]

Here are two minimal sudokus with 35 clues:
#
100056780780120450400700103201064800060090001800200500302645000640070000000002000
103006780780120450400700103201064800060090001800200500302645000640070000000002000
#

Minimal as in: Not able to remove a clue without causing a puzzle with multiple solutions?

That would make the following 2 non-existent?

Code: Select all

100006780780120450000700103201064800060090001800000500302645000640070000000002000
103006780780100450000700103001064800060090001800000500302645000640070000000002000

Ruud.

Umm... that's correct - as your first puzzle has 15 solutions, your second has 55. (See list of 'reduced' puzzles below.)

coloin: thanks - didn't see your post until after I made my comment...
And to the previous:

Is there a way of working out which are the non-common clues in one grid which map to the non-common clues in the other

Sure - that is straightforward if you have the right tool (which i do not have). But there is no point in distinguishing between common and non-common clues in that respect. Planned do write some tools which could give further insight, but haven't got time for it yet - it takes time to figure out how to do things in a proper way.

The 35 was found in the canonical grid, which has a 19 but no 18.
Would there be a higher chance of finding a 36 in a grid which has a 20 but no 19?
145726983837495261926381574293874156581269347674153892318547629459632718762918435

Had a 'quick' look at it. Found two minimal 32s in this grid so far. Maybe you can do better...

I presume Ocean's computor is continuing to scan the canonical for a 36 !

Would rather say considering how to effectively do it. No point in starting jobs lasting for years. The good thing with all the symmetry in the canonical grid, is that there is much less to 'scan' - the symmetry factor of 648 could make two years become one day...

O.

ADDENDUM:
Here is a list of all multi-solution puzzles you get when removing one clue from each of the two minimal 35s. (The number behind the P is the number of solutions for that particular puzzle. P1 on the original 35-clue puzzles. Sorry for the random ordering.)
#
100056780780120450400700103201064800060090001800200500302645000640070000000002000 P1
100056780780120450400700103201060800060090001800200500302645000640070000000002000 P2
100056780780120450400700103200064800060090001800200500302645000640070000000002000 P5
100056780780120450400700103201064800000090001800200500302645000640070000000002000 P2
100056780780120450400700103001064800060090001800200500302645000640070000000002000 P5
100056780780120450400700100201064800060090001800200500302645000640070000000002000 P36
100056700780120450400700103201064800060090001800200500302645000640070000000002000 P2
100056780780120050400700103201064800060090001800200500302645000640070000000002000 P2
100056780780120450400700103201064800060090001800200500302645000640070000000000000 P4
100056780780120450400700103201064800060090001800200000302645000640070000000002000 P4
100056780780120450400700003201064800060090001800200500302645000640070000000002000 P2
100056780780120450400700103201064800060090000800200500302645000640070000000002000 P3
100056780780120400400700103201064800060090001800200500302645000640070000000002000 P6
100056780780120450400700103201064800060090001800200500302045000640070000000002000 P2
100056780780120450400700103201064800060000001800200500302645000640070000000002000 P21
100056780780020450400700103201064800060090001800200500302645000640070000000002000 P2
100056780700120450400700103201064800060090001800200500302645000640070000000002000 P2
100056780780100450400700103201064800060090001800200500302645000640070000000002000 P11
100056780780120450400000103201064800060090001800200500302645000640070000000002000 P3
100056780780120450400700103201004800060090001800200500302645000640070000000002000 P2
100056780780120450400700103201064800060090001800200500002645000640070000000002000 P4
100056080780120450400700103201064800060090001800200500302645000640070000000002000 P2
100056780780120450400700103201064800060090001000200500302645000640070000000002000 P15
100006780780120450400700103201064800060090001800200500302645000640070000000002000 P5
100056780780120450400700103201064800060090001800200500302645000640000000000002000 P5
000056780780120450400700103201064800060090001800200500302645000640070000000002000 P5
100050780780120450400700103201064800060090001800200500302645000640070000000002000 P4
100056780780120450400700103201064800060090001800200500302645000040070000000002000 P2
100056780780120450400700103201064800060090001800200500302645000600070000000002000 P7
100056780780120450400700103201064000060090001800200500302645000640070000000002000 P4
100056780780120450000700103201064800060090001800200500302645000640070000000002000 P9
100056780080120450400700103201064800060090001800200500302645000640070000000002000 P2
100056780780120450400700103201064800060090001800200500300645000640070000000002000 P4
100056780780120450400700103201064800060090001800000500302645000640070000000002000 P3
100056780780120450400700103201064800060090001800200500302605000640070000000002000 P2
100056780780120450400700103201064800060090001800200500302640000640070000000002000 P2
#
103006780780120450400700103201064800060090001800200500302645000640070000000002000 P1
103006780780120450400700103201064800060090000800200500302645000640070000000002000 P3
103006780780120450400700103001064800060090001800200500302645000640070000000002000 P5
103006780780120450400700103201064000060090001800200500302645000640070000000002000 P3
103006780780120450400700103201064800060090001800200500302645000600070000000002000 P4
103006780780120450400700103201064800060090001800000500302645000640070000000002000 P3
103006780780120450400700103200064800060090001800200500302645000640070000000002000 P2
103006780780120450400700103201064800000090001800200500302645000640070000000002000 P2
103006780780100450400700103201064800060090001800200500302645000640070000000002000 P19
103006700780120450400700103201064800060090001800200500302645000640070000000002000 P5
103006780780120450400700103201064800060090001800200500302640000640070000000002000 P2
103006780780120450400700103201064800060090001800200500302645000640000000000002000 P4
103000780780120450400700103201064800060090001800200500302645000640070000000002000 P2
103006780780020450400700103201064800060090001800200500302645000640070000000002000 P2
103006780080120450400700103201064800060090001800200500302645000640070000000002000 P2
103006780780120450400700003201064800060090001800200500302645000640070000000002000 P2
103006780780120450400700103201064800060090001800200500302645000640070000000000000 P3
103006780780120450400700103201064800060090001000200500302645000640070000000002000 P12
103006780780120450400700103201064800060090001800200500300645000640070000000002000 P3
003006780780120450400700103201064800060090001800200500302645000640070000000002000 P5
103006780780120450400700100201064800060090001800200500302645000640070000000002000 P21
103006780780120450400000103201064800060090001800200500302645000640070000000002000 P3
103006780780120450400700103201064800060090001800200500302645000040070000000002000 P2
103006780780120050400700103201064800060090001800200500302645000640070000000002000 P2
100006780780120450400700103201064800060090001800200500302645000640070000000002000 P5
103006780780120450000700103201064800060090001800200500302645000640070000000002000 P5
103006780780120400400700103201064800060090001800200500302645000640070000000002000 P6
103006780780120450400700103201064800060090001800200500302605000640070000000002000 P7
103006780780120450400700103201004800060090001800200500302645000640070000000002000 P2
103006780700120450400700103201064800060090001800200500302645000640070000000002000 P2
103006780780120450400700103201060800060090001800200500302645000640070000000002000 P2
103006080780120450400700103201064800060090001800200500302645000640070000000002000 P2
103006780780120450400700103201064800060090001800200000302645000640070000000002000 P4
103006780780120450400700103201064800060000001800200500302645000640070000000002000 P37
103006780780120450400700103201064800060090001800200500302045000640070000000002000 P2
103006780780120450400700103201064800060090001800200500002645000640070000000002000 P2
#

[Ocean]

Interesting that you have shown the morphed puzzles....number 2 and number 3 in your list have 20 common clues.

Code: Select all

.2.4.6.89.89.23.56.5..8.12.23.5.4.9...4..72...9..3..6.31.645....45..8......3.....
.23.5.7.9.89.23.5645..8..2..3.56.8.75....7..1.9..3..6....64.978....78..2......6..
.2......9.89.23.56.5..8..2..3.5..........7....9..3..6....64.........8............

Most have considerably less - was this deliberate ?

Maybe there are ones which are even better than this ?

Is there a way of working out which are the non-common clues in one grid which map to the non-common clues in the other ?
C

If the symmetry op is known, then just apply this on each clue, and you get the mapping directly. So, I guess you address the case when the symmetry op is not explicitly known. We have two isomorphic sudokus S1 and S2 in the same grid, not knowing the particular symmetry op used. Then I can think of two quite different methods:

1. Calculate the symmetry op, and apply it on each clue in S1 gives the mapping into S2. [This is not considered here.]
2. Exploit the fact that the two isomorphs S1 and S2 have many properties in common! Take any property that is unique for a particular clue in S1. Then there will be exactly one clue in S2 that has the same property, and these two clues are the corresponding, or mapped ones.

Example: When we delete any clue from our minimal 35 puzzle, we get a new puzzle with multiple solutions. For some clues the number of of solutions for the reduced puzzle is unique: Only one clue leads to 11 solutions, and only one clue leads to 15 solutions. These clues are marked with X and Y below. Cell X (P11) from one isomorph maps into X in the other isomorph. And similarly, Y (P15) from S1 maps into Y in S2.

Code: Select all

.2.4.6.89.89.23.56.5..8.12.23.5.4.9...4..72...9..3..6.31.645....45..8......3.....
.2.4.6.89.89.2..56.5..8.12.23.5.4.9...4..72...9..3..6.31.645....45..8......3.....
.2.4.6.89.89.23.56.5..8.12.23.5.4.9...4..72......3..6.31.645....45..8......3.....
--------------X-------------------------------Y----------------------------------

.23.5.7.9.89.23.5645..8..2..3.56.8.75....7..1.9..3..6....64.978....78..2......6..
.23.5.7.9.89.23.5.45..8..2..3.56.8.75....7..1.9..3..6....64.978....78..2......6..
.23.5.7.9.89.23.5645..8..2..3.56.8.75....7..1.9.....6....64.978....78..2......6..
-----------------X-------------------------------Y-------------------------------

(The 20 common clues:)
.2......9.89.23.56.5..8..2..3.5..........7....9..3..6....64.........8............

[coloin]

Thankyou Ocean
I think the common clues might be useful but we need 24 or 25 in common to have any chance of going through all possible possibilities.

Until we find [if we ever do] a better overlap of isomorphs, maybe the following method could be used:

For one puzzle [puzzle 1] it will be made up of 3 types of clue - w.r.t a "similar" isomorph puzzle. [puzzle 2]

For example there "may" be :
20 common clues which map to 20 unspecified clues in puzzle 2.
8 non common clues which map to 8 of the common clues in puzzle 2
7 non common clues which map to the other 7 non common clues in puzzle 2. [This will be reciprical]

It would certainly be possible with my program to go through an attempt with the 20 common clues and the 8 common clue generators and go through all the possibilities - no guarentee of a 36 but we might generate more 35s.

There are too different many ways to go through a mult of all the ways to remove 7 clues and adding 8 more minimally.

C

[Ocean]

Until we find [if we ever do] a better overlap of isomorphs, ...
C

I must admit I can not quite see the point of "overlapping the isomorphs" - but maybe there is something I don't understand.

I thought we could regard the 648 symmetries as 648 separate but identical/equivalent globes. If we know one, we know them all. Therefore, if we stick to one of the globes, we save a factor 648 ('time' or 'effort') - or cover 648 times more - compared to an average grid.

[coloin]

Maybe there isnt anything in it. But it is a hunch to perform a deeper than normal search. We have 20 clues which complete with 2 different sets of 15 clues. Adding 15 clues is too many however.

I have analysed the mapping - its a simple vertical chute interchange [1-2,2-3,3-1] and relabelling - it did turn out to be 7 clues which werent envolved in the common clues.

I have run it [28 clues plus any 7 of the remaining] over one of the grids. To reduce the number of options I excluded the clues in box 9 - but it didnt generate any more 35s. To exclude any 35s over the whole grid will take longer. [2 days].

I dont think I will get a 36 if I cant generate more 35s [do you agree ?]

I do regard the 648 symmetries as identical / equivalent - as you say.

We may have reached the limit with the set of clues we have in the two 35s....but how will we ever know that there isnt another region in the grid that is better ?

To go back to the minimum clues problem - the "region" was identified because a set of 14 or so clues had a significantly higher number of minimal clue completions. Thus if this could be identified it was easy to find the minimum clues in the grid. This method failed however if there were a lot of other sets of clues/regions which clouded statistical analysis.

This will happen in the canonical grid here - and I cant see any way to exclude the puzzle morphs.

As an aside I have - looked at other grids with some similarities to the canonical grid here. I analysed the 6280 grid solutions to the B1B2B3B4B7 in the canonical grid.

There are plenty of canonical equivalents which have an average minimal sudoku count ot 25.7...[average grid is 24.4]....[SF was 24.1]

I have looked at a non symetrical grid canon varient with a highish value 25.3

Code: Select all

123456789789123456456789123231548967564937218897612345312875694645391872978264531

This has plenty of 32s and I will update when I get a 33.

The question as to where the best region is in this grid is unanswered as yet.

C.

[coloin]

This grid

Code: Select all

123456789789123456456789123231548967564937218897612345312875694645391872978264531

is constructed from the 12347 Boxes of our canonical grid

I thought there would be a 33 but.......here is a minimal 34.

Code: Select all

+---+---+---+
|...|45.|7..|
|7.9|.23|4.6|
|4.6|7.9|.23|
+---+---+---+
|2..|54.|...|
|56.|.37|21.|
|..7|..2|3..|
+---+---+---+
|.12|...|6..|
|6.5|...|.7.|
|...|...|.3.|
+---+---+---+

EDIT
Here are another 3

Code: Select all

...45.7..7.9.234.64.67.9.232..54..6.564.372.......23...12......6.5....7.9......3.
...45.7..7.9.234.64.67.9.232..54..6.56..3721...7..23...12......6.5....7........3.
...45.7..7.9.234.64.67.9.232..54..6.56..372....7..23...12......6.5....7.9......3.
...45.7..7.9.234.64.67.9.232..54....56..3721...7..23...12...6..6.5....7........3.

C

[Ocean]

This grid

Code: Select all

123456789789123456456789123231548967564937218897612345312875694645391872978264531

is constructed from the 12347 Boxes of our canonical grid

I thought there would be a 33 but.......here is a minimal 34.

This is interesting! It's the first grid besides the canonical where minimal sudokus with 34 clues are found. You have four of them so far - so there might be a possibility of finding 35s (or higher).

[coloin]

Yes it is interesting......Do you think it is possible for someone to explain just how unlikely a task this all is ?

Here are three more from the canonical varient

Code: Select all

...45.7..7.9.234.64.67.9.232..54..6.564.372.......23...12......6.5....7.9......3.
...45.7..7.9.234.64.67.9.232..54..6.56..3721...7..23...12......6.5....7........3.
...45.7..7.9.234.64.67.9.232..54..6.56..372....7..23...12......6.5....7.9......3.
...45.7..7.9.234.64.67.9.232..54....56..3721...7..23...12...6..6.5....7........3.
...45.7....9.234.6..67.9.232..54..6.564.3721...7..23...12......6.5....7.9......3.
...45.7....9.234.6..67.9.232..54..6.56..3721...7..234..12......6.5....7.9......3.
....5.7..7.9.234.6..67.9.232..54..6.56..372....7..23...12...6.46.5....7........31

and yes, I think there could well be a 36 hiding out there in some other grid.

I have found another three 34s in "another grid". Even more interestingly there are much fewer 2-gridsolution clues - only 4 of the 34 - which makes me think there is furthur to go than 35.

For example Guenter posted this last September !

here is some statistics, starting from a full grid and generating 1e6
random locally minimal sudokus from it.

1) one grid from each G-class at random
2) Gordon's grid with 29 17s, the SF grid
3) our canonical grid,(1,1,1-1,1,1)

Code: Select all

clues , 1)     2)      3)         
----------------------------
17,     0       0       0       
18,     0       0       0       
19,     0     4.3       0     
20,    59     182       0     
21,  2428    6051      85     
22, 33966   61826    1775   
23,170727  227480   21648   
24,342620  352289  116766   
25,298349  248568  286836   
26,122691   86061  329853   
27, 25237   15908  185028   
28,  2733    1547   50469     
29,   205      74    7040       
30,   7.6     8.6     486       
31,     0       0      12       
32,     0       0     2.4       
-------------------------------
aver.24.38   24.10   25.72   

He randomly generated a million grids and counted.

"Normal" grids didnt produce a 31 randomly. Mind you we knew there were 32s !

Maybe the canonical grid is not that good........after all there are 648 isomorph puzzles, therefore the stats for the canonical grid are inflated by this factor.

Recognize this grid ?

Code: Select all

+---+---+---+
|6.9|.4.|...|
|.8.|.65|..3|
|5.7|983|6..|
+---+---+---+
|...|...|..6|
|79.|.3.|85.|
|...|..9|23.|
+---+---+---+
|.4.|..8|...|
|8..|.94|37.|
|..5|326|4..|
+---+---+---+  34 clue minimal

Code: Select all

6.9.4.....8..65..35.79836..........679..3.85......923..4...8...8...9437...53264..
6.9.4.....8..65..35.79.36.....8....679..3285......923..4...8...8...9.37...53264..
6.9.4........65..35.79.36.....8....679..3285...8..923..4...8...8...9.37...53264..

Its Strangely Familiar !

C

[coloin]

I think i've reached a point in this problem where it becomes difficult to know for certain which way to proceed. We have one grid with several minimal 35s and now two grids with some minimal 34s. It is of note that despite the high frequency of clues the puzzles tend to need a guess to solve !

There are a very large number of ways to insert 35 clues from a valid 81 solution grid and there are relativly few ways to insert 35 clues that cant possibly solve. Relativly because the number of ways not to have at least 8 clues numbers used or not to fill two rows or whatever is considerable...but not when you compare it to the very large number of ways.

Hitting at least one of every unavoidable in a grid is crucial to any solution to a puzzle - I ran 35 random clue positions over 1000 random grids and only about 10% solved the grid - non minimally of course. The 90% that failed - failed because they missed at least one of the unavoidable sets. This proportion wil reduce as the number of clues used reduces.

Code: Select all

clues   % solved with these clues
78         100
40          28
35          10
30           2
16           0         sample size 1000 for 40,35,30

Methods of finding the clues so far have included using established high clue puzzles and searching around. A full search of all possible possibilites is possible when the number of variable clues is around 6, ie 28 clues are fixed and looking at all the combinations of 6 furthur clues. Random generation from reduced grids is another way to generate 30 and 31 clue puzzles, leaving out selected clues and one whole box seems to generate high clue minimal puzzles. Deciding which clues to leave out is not an exact science ! It is difficult to believe that we have found the optimal reduced grid.

So it is highly probable that there will be a way of inserting more than 35 clues minimally.

In a minimal grid with 35 clues we are looking for 35 clues each of which have sole occupancy of one [or more] of the unavoidable set[s] in the grid. In the 34 in the SF grid there are fewer[4] of these single unavoidable set / 2 grid solution clues - especially compared to Ocean's 33. This might mean there is furthur to go in the number of possible clues.

I think the reason I enjoy this challenge is that I [Edit I thought I understood] understand just how big it is.

EDIT
For Correction see next posting

Code: Select all

clue count   total number of ways       incidence of minimal puzzles
                   
35 clues     81!/46! = 1.1*e^63         one grid has two   
30 clues     81!/51! = 3.7*e^54         generated at the rate of 7.6 per million
24 clues     81!/57! = 1.4*e^44         all grids have a "very large" number.  A guess would be 10^10
19 clues     81!/62! = 1.8*e^35         perhaps one per million generated - almost all grids have at least one
18 clues     81!/63! = 2.9*e^33         one in seven grids have at least one
17 clues     81!/64! = 48*10^30         one in ten thousand grids may have at least one   

In case you didnt know, the grid with the most number of 17 clue puzzles is also one of the grids with a 34 !

1.One was eventually able to count up the total number of grids 6*10^21, in less than half a second now.
2.Gfroyle was able to find minimal puzzles of size 17,perhaps almost all......Aside from the very improbable task of hitting all the unavoidable sets, only a small proportion will fulfill the 8 clue, no 2 empty column and no 3 empty box rules which we mentioned earlier. On top of that a 17 will be only be found in around 1 in 10,000 grids approx.
3.Ocean has found 2 puzzles out of a total number of a large number of possible possible combinations, in one grid.

Analogy:

1.We have counted the number of blades of hay in a very large haystack
2.We have found one of the many needles in this haystack
3.We have found in the eye of one of the needles a non-mutated bird-flu virus particle.

C

[frazer]

Hi coloin,

I think that your clue counts aren't quite right; the number of ways of choosing n squares from a completed 81-square grid should be 81!/(n!(81-n)!). In particular, the number of 35-clue sets should be 81!/35!46!, which is about 1e23, not 1e63. (Your answer would be right if it mattered which order you choose the 35 squares.) To see why your answer can't quite be right, think about specifying 80 clues, say, which your answer would give 81!/1!=81!, whereas choosing 80 is equivalent to choosing which 1 of the 81 squares to leave out, and there are clearly 81 squares to choose from. (Of course, the quantitative difference here doesn't alter the nature of the qualitative statements you make - these are both numbers well beyond what we can reasonably exhaust.)

[coloin]

Yes, not quite right !

Thankyou for explaining that, I was concerned that the numbers were so big, and I had remembered that the options for 16 or 17 clues was around 10^16.

Code: Select all

clue count  total number of ways        incidence of minimal puzzles
                   
35 clues    81!/35!46! = 1.01*10^23     three grids have several   
30 clues    81!/30!51! = 1.41*10^22     generated at the rate of 7.6 per million
24 clues    81!/24!57! = 2.30*10^20     all grids have a "very large" number.   ? 10^11 [maybe more ?]
19 clues    81!/19!62! = 1.51*10^18     almost all grids have at least one
18 clues    81!/18!63! = 4.56*10^17     one in seven grids have at least one
17 clues    81!/17!64! = 7.14*10^15     one in ten thousand grids may have at least one   

C