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

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

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

145726983837495261926381574293874156581269347674153892318547629459632718762918435

- Moschopulus
**Posts:**256**Joined:**16 July 2005

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

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

C

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

- coloin
**Posts:**1638**Joined:**05 May 2005

Ocean wrote: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.

- Ruud
**Posts:**664**Joined:**28 October 2005

Ocean wrote: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....

.......which they do, 15 and 55 respectively.Ruud wrote:That would make the following 2 non-existent?

- Code: Select all
`100006780780120450000700103201064800060090001800000500302645000640070000000002000`

103006780780100450000700103001064800060090001800000500302645000640070000000002000

That Ocean has found a 35 - is remarkable.

C

Last edited by coloin on Thu Mar 23, 2006 7:11 pm, edited 1 time in total.

- coloin
**Posts:**1638**Joined:**05 May 2005

Ruud wrote:Ocean wrote: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:

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.coloin wrote: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

Had a 'quick' look at it. Found two minimal 32s in this grid so far. Maybe you can do better...Moschopulus wrote: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 wrote: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
**Posts:**442**Joined:**29 August 2005

coloin wrote: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............

- Ocean
**Posts:**442**Joined:**29 August 2005

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

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

- coloin
**Posts:**1638**Joined:**05 May 2005

coloin wrote: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.

- Ocean
**Posts:**442**Joined:**29 August 2005

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

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.

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
**Posts:**1638**Joined:**05 May 2005

This grid

is constructed from the 12347 Boxes of our canonical grid

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

EDIT

Here are another 3

C

- 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

- coloin
**Posts:**1638**Joined:**05 May 2005

coloin wrote: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).

- Ocean
**Posts:**442**Joined:**29 August 2005

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

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 !

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 ?

Its Strangely Familiar !

C

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

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 !

dukoso wrote: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
**Posts:**1638**Joined:**05 May 2005

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.

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

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

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

Last edited by coloin on Tue May 09, 2006 10:52 am, edited 3 times in total.

- coloin
**Posts:**1638**Joined:**05 May 2005

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

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

- frazer
**Posts:**46**Joined:**06 June 2005

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.

C

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

Last edited by coloin on Thu Jun 22, 2006 10:35 am, edited 2 times in total.

- coloin
**Posts:**1638**Joined:**05 May 2005