Max number of clues

Everything about Sudoku that doesn't fit in one of the other sections

Postby Red Ed » Tue Mar 14, 2006 8:21 am

coloin wrote:648 = ? 18*6*6 ....[could you explain these?]
The 648 comes from 18 (row perms) x 18 (col perms) x 2 (transpo). It's easier to see for a slightly reordered version of the grid, but it basically comes down to: any choice of band order (6), then any choice of cycling within all bands the same way (3), giving 18 row perms; same for columns; then similar with the grid transposed. To be sure, I actually checked the whole group of 3359232 ops and did indeed find 648 symmetries.

I guess your method is considering small deviations from a crop of 33s, so perhaps it's unsurprising that it's rare for two slightly-different grids to be isomorphic. None of the new (isomorphic) ones got by use of symmetry share the 15-clue backbone, for example.
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby coloin » Tue Mar 14, 2006 1:25 pm

I am getting confused between isomorphic grids and isomorphic puzzles. !

These isomorphs are grids which are equivalent and are over and above the normal symmetric isomorphs in a grid ? [relabeling and box/row/column swapping etc.]

Re thinking about your question......I am pretty certain that there should be no puzzles which come from another isomorphic grid in my list of 117. My method is to "mult" from one grid only - so they should all be from the same isomorphic grid. [.....Unless my program is doing things I dont know about....]

Can you show me which puzzle has/is an isomorph ? !

C
coloin
 
Posts: 1633
Joined: 05 May 2005

Postby Red Ed » Tue Mar 14, 2006 8:01 pm

coloin wrote:I am getting confused between isomorphic grids and isomorphic puzzles. !
OK, it's like this. Recall that there's a group of 9! x 3359232 transformations (cell permutations with symbol relabelling) that preserve the validity of any sudoku solution grid. For your particular solution grid, there is a subgroup of 648 transformations that leaves the solution grid unchanged. That's a lot! - your grid is quite special. If I apply any of those 648 transformations to a subgrid (i.e. a puzzle), I'll get another subgrid (i.e. puzzle) with the same solution. To my surprise, none of your 111 unique puzzles is mapped back to itself by any of these 648 ops: so each one of your puzzles can be expanded to a list of 648 isomorphic ones with the same solution; and, further, none of these 111 lists of 648 puzzles overlap.

coloin wrote:Can you show me which puzzle has/is an isomorph ? !
It's worse than just isomorphic: you've got duplicates, e.g. nr 1 and nr 115.
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby coloin » Tue Mar 14, 2006 8:58 pm

Wow

So 9! x 3359232 isomorphic grids - OK

But 648 transformations - each of which when applied to a puzzle gives a "different" puzzle but the grid solution is the same. As you say at least 111*648 33 puzzles. Perhaps it just goes to show how many total possible [invalid or non-minimal] 33 grids there are [4 e^59] that random generation of minimal puzzles come nowhere near any of these 33s.

Perhaps it is not unusual that the 15 clues were not repeated in a transformed puzzle - However this is good news in not decreasing the likelihood of a 34.

What do you think is the next move. ?

My methods to mult 25 + 8 unknowns over a reduced grid have been fruitful but......it is too big an ask to mult 15 + 19 unknowns over a full grid. [And we cant know for sure if these 15 are in a 34 - if there is one that is !]

I think an option would be to fix these 15 clues and perform a clue frequency count on randomly generated 30 something minimal sudoku puzzles. No guarentee that this would work as there are so many floating isomorphs around to cloud the picture. But it might.
coloin
 
Posts: 1633
Joined: 05 May 2005

Postby Red Ed » Tue Mar 14, 2006 10:10 pm

coloin wrote:So 9! x 3359232 isomorphic grids - OK
Actually 1/648 of that value: so, 9! x 5184. I'm guessing this arises as follows. Fill in B1 any old way. This gives you two sets of 3 numbers to go in the top minirow of B2 and B3, in any order (3!^2 x 2 = 72 ways); ditto for lefthand minicols of B4 and B7. Given that we're looking for an isomorph of your grid, the remaining cell values are then forced.

coloin wrote:What do you think is the next move. ?
Beats me. Finding max/min clue sets seems like a lottery.
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby coloin » Tue Mar 14, 2006 10:32 pm

Now Its clear. I wondered where the extra permutations came from.

You might be more likely to win Euromillions 3 times in a row than find a 34 by chance.

Code: Select all
Match                Odds
5+2 numbers          1:76,275,360


C
Last edited by coloin on Thu Jun 22, 2006 10:28 am, edited 1 time in total.
coloin
 
Posts: 1633
Joined: 05 May 2005

false alarm

Postby Moschopulus » Tue Mar 14, 2006 10:59 pm

I thought for a second this thread had a 34, but no, it does not.

http://www.setbb.com/sudoku/viewtopic.php?t=115&mforum=sudoku

They are making the assumption on this thread that the puzzle be symmetric.
Moschopulus
 
Posts: 256
Joined: 16 July 2005

Minimal 34s

Postby Ocean » Fri Mar 17, 2006 12:14 am

Here are some minimal sudokus with 34 clues:

100056700780023450400700103001064890000090001800200500302645008640070000000002000
100056700780103450400700103001064890000090001800200500302645008640070000000002000
100056700780120450400700103001064890000090001800200500302645008640070000000002000
103006780780023450400700103000064890060090001800200500302640008640070000000002000
103006780780103450400700103000064890060090001800200500302640008640070000000002000
103006780780120450400700103000064890060090001800200500302640008640070000000002000
103056000780023450400700103000064897000090001800200500302645008640070000000002000
103056000780103450400700103000064897000090001800200500302645008640070000000002000
103056000780120450400700103000064897000090001800200500302645008640070000000002000
103056700780023450000700103000064890004090001800200500302645008640070000000002000
103056700780023450400700103000064890000090001800200500302645008640070000000002000
103056700780023450400700103000064890060090001800200500302640008640070000000002000
103056700780103450000700103000064890004090001800200500302645008640070000000002000
103056700780103450400700103000064890000090001800200500302645008640070000000002000
103056700780103450400700103000064890060090001800200500302640008640070000000002000
103056700780103450400700103000064897000090001800200500302645000640070000000002000
103056700780120450000700103000064890004090001800200500302645008640070000000002000
103056700780120450400700103000064890000090001800200500302645008640070000000002000
103056700780120450400700103000064890060090001800200500302640008640070000000002000
103056700780120450400700103000064897000090001800200500302645000640070000000002000
#

Not checked for isomorphism. In this grid the nonisomorphic 34s can be multiplied by a factor up to 648 - as shown by Ed - giving a few thousand distinct minimal puzzles. The first '34' was found by playing around with coloins numerous 33s.
Ocean
 
Posts: 442
Joined: 29 August 2005

Re: Minimal 34s

Postby Red Ed » Fri Mar 17, 2006 12:44 am

Ocean wrote:Here are some minimal sudokus with 34 clues:
Nice ...
Ocean wrote:Not checked for isomorphism.
They're all non-isomorphic and not fixed by any of the 648 symmetries, so you've potentially got another 20 x 647 = 12940 distinct puzzles out there in isomorph land.
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby coloin » Fri Mar 17, 2006 4:51 pm

Very well done on the 34s.
Code: Select all
1.3.567..78.12.45.4..7..1.3....64897....9...18..2..5..3.2645...64..7.........2...
1.3.567..78.12.45.4..7..1.3....6489..6..9...18..2..5..3.264...864..7.........2...
1.3.567..78.12.45.4..7..1.3....6489.....9...18..2..5..3.2645..864..7.........2...
1.3.567..78.12.45.4..7..1.3.....4897.6..9...18..2..5..3.2645...64..7.........2...
1.3.567..78.12.45....7..1.3....6489...4.9...18..2..5..3.2645..864..7.........2...
1.3.567..78.1.345.4..7..1.3....64897....9...18..2..5..3.2645...64..7.........2...
1.3.567..78.1.345.4..7..1.3....6489..6..9...18..2..5..3.264...864..7.........2...
1.3.567..78.1.345.4..7..1.3....6489.....9...18..2..5..3.2645..864..7.........2...
1.3.567..78.1.345.4..7..1.3.....4897.6..9...18..2..5..3.2645...64..7.........2...
1.3.567..78.1.345....7..1.3....6489...4.9...18..2..5..3.2645..864..7.........2...
1.3.567..78..2345.4..7..1.3....64897....9...18..2..5..3.2645...64..7.........2...
1.3.567..78..2345.4..7..1.3....6489..6..9...18..2..5..3.264...864..7.........2...
1.3.567..78..2345.4..7..1.3....6489.....9...18..2..5..3.2645..864..7.........2...
1.3.567..78..2345.4..7..1.3.....4897.6..9...18..2..5..3.2645...64..7.........2...
1.3.567..78..2345....7..1.3....6489...4.9...18..2..5..3.2645..864..7.........2...
1.3.56...78.12.45.4..7..1.3....64897....9...18..2..5..3.2645..864..7.........2...
1.3.56...78.1.345.4..7..1.3....64897....9...18..2..5..3.2645..864..7.........2...
1.3.56...78..2345.4..7..1.3....64897....9...18..2..5..3.2645..864..7.........2...
1.3..678.78.12.45.4..7..1.3..1..489..6..9...18..2..5..3.264...864..7.........2...
1.3..678.78.12.45.4..7..1.3....6489..6..9...18..2..5..3.264...864..7.........2...
1.3..678.78.1.345.4..7..1.3....6489..6..9...18..2..5..3.264...864..7.........2...
1.3..678.78..2345.4..7..1.3....6489..6..9...18..2..5..3.264...864..7.........2...
1...567..78.12.45.4..7..1.3..1.6489.....9...18..2..5..3.2645..864..7.........2...
1...567..78.1.345.4..7..1.3..1.6489.....9...18..2..5..3.2645..864..7.........2...
1...567..78..2345.4..7..1.3..1.6489.....9...18..2..5..3.2645..864..7.........2...
five more for completeness.

You have done very well - removing 7 clues and adding 8 different ones.

The common backbone of 15 has changed.....
Code: Select all
.....6.8.78.1..45.4.......3.....4.......9...1..............5....4............2... 15 clues from the list of 33s
1....6...78....45....7..1.3.....489.....9...18..2..5..3.264....64..7.........2... 25 clues from above


I had gone on to generate a further 50 or so different 33s - and a few had begun to emerge without some of the 15..... I suppose the common clues are just an initial guide.

I had begun to wonder whether a visit to isomorphland could help !

Questions

1. Of the x 647 other transpuzzles per puzzle there will be varying degrees of siimilarity. On average 34*34/81 = 14.27 clues will be the same. But some will be more and some considerably less.

2. Which specific tranformation gets closest to our series ?

3. Might there be a transformed puzzle with 20 similar clues ? The mapping of the clues would then be relevant ?

C
coloin
 
Posts: 1633
Joined: 05 May 2005

Re: Minimal 34s

Postby Ocean » Sat Mar 18, 2006 6:36 pm

Red Ed wrote:They're all non-isomorphic and not fixed by any of the 648 symmetries, so you've potentially got another 20 x 647 = 12940 distinct puzzles out there in isomorph land.

Thanks! (Have not yet finished making those tools for analyzing symmetries..)

coloin wrote:five more for completeness.

Good. Here are three additional minimal 34s (same grid):
#
103056700780023450400700103200004097060090001800200500302645000640070000000002000 M34
103056700780103450400700103200004097060090001800200500302645000640070000000002000 M34
103056700780120450400700103200004097060090001800200500302645000640070000000002000 M34
#

(To coloin:) Not able to answer your questions without guessing - (tools not available...).
Ocean
 
Posts: 442
Joined: 29 August 2005

Minimal 35s

Postby Ocean » Sat Mar 18, 2006 10:02 pm

Here are two minimal sudokus with 35 clues:
#
100056780780120450400700103201064800060090001800200500302645000640070000000002000
103006780780120450400700103201064800060090001800200500302645000640070000000002000
#
Ocean
 
Posts: 442
Joined: 29 August 2005

Postby coloin » Sat Mar 18, 2006 11:00 pm

Incredible.:D
And all the clues are giving us less pseudopuzzles - rather than more.
Both of your 35s have all the 15 clues backbone.

Even more interesting is that both have 26 common clues with our original 32 clue ....... this was generated randomly so perhaps this is confirmation that we are on the right track. [perhaps we know this already]

When will we know when to stop ?

The empty box 9 precludes many of the matches available when transformed.

It would be interesting to look at the other 647. I suppose a total clue count will be the same for all clues over all 648 puzzles ?

Maybe it wont be of much use. It was convenient that you found the 35 so quickly. I would have thought that it would have been more difficult.

C
coloin
 
Posts: 1633
Joined: 05 May 2005

Postby Ocean » Sun Mar 19, 2006 4:54 am

coloin wrote:The empty box 9 precludes many of the matches available when transformed.

It would be interesting to look at the other 647. I suppose a total clue count will be the same for all clues over all 648 puzzles ?

A small sample set - these are all isomorphic to the 'first' minimal 35:
Code: Select all
003450709709103406006009023031560007500800030007001004012645000605900000000010000
020406089089023056050080120230504090004007200090030060310645000045008000000300000
023050709089023056450080020030560807500007001090030060000640978000078002000000600
023450700780120450400709100031500807060007030800200500312000908040000310008000000
100056780780120450400700103201064800060090001800200500302645000640070000000002000
103006780709103406056009003001064890060800200007001004000045978000908300000000040
103056080089023056050780020201060890004800001090030060312000970005000012900000000
120400089780120450406700100200504097004090030800200500000605978000970010000000005
120406009709103406006089003230004097500090200007001004312000078600000302070000000

The empty box is of course always present, but can move 'freely' to any position:
Code: Select all
 *-----------*
 |...|45.|789|
 |...|...|4..|
 |...|.89|..3|
 |---+---+---|
 |.31|.6.|8.7|
 |56.|.9.|.3.|
 |.97|.31|.64|
 |---+---+---|
 |.1.|64.|9.8|
 |6..|..8|..2|
 |.7.|.1.|.4.|
 *-----------*
#
 *-----------*
 |.23|.5.|7.9|
 |.89|.23|.56|
 |45.|.8.|.2.|
 |---+---+---|
 |.3.|56.|8.7|
 |5..|..7|..1|
 |.9.|.3.|.6.|
 |---+---+---|
 |...|64.|978|
 |...|.78|..2|
 |...|...|6..|
 *-----------*
#
 *-----------*
 |12.|4.6|..9|
 |7.9|1.3|4.6|
 |..6|.89|..3|
 |---+---+---|
 |23.|..4|.97|
 |5..|.9.|2..|
 |..7|..1|..4|
 |---+---+---|
 |312|...|.78|
 |6..|...|3.2|
 |.7.|...|...|
 *-----------*

It was convenient that you found the 35 so quickly. I would have thought that it would have been more difficult.

The 35s popped up because they were present not too far from the set of 34s.
Ocean
 
Posts: 442
Joined: 29 August 2005

Postby coloin » Sun Mar 19, 2006 1:48 pm

Indeed that is clearer......

With hindsight, the difference between some of our 32,33,34 and your 35s is indeed small.
Code: Select all
1...5678.78.12.45.4..7..1.32.1.648...6..9...18..2..5..3.2645...64..7.........2... m35
1.3..678.78.12.45.4..7..1.32.1.648...6..9...18..2..5..3.2645...64..7.........2... m35


1.3..678.78.12.45.4..7..1.3..1..489..6..9...18..2..5..3.264...864..7.........2... m34
1.3..678.78..2345.4..7..1.3....6489..6..9...18..2..5..3.264...864..7.........2... m34


1.3..678.78.12.45.4.....1.3..1.6489.....9...18.....5.......597864.97.3.......2... m33
1.3..678.78.12.45.4..7..1.3....6489.....9...18..2..5..3....597864..7.........2... m33

12...67..78.12.45.4.......3.3..6489.....9..318..2.....3.2.45...64.97.........2.4. m32


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
Last edited by coloin on Fri Mar 24, 2006 2:37 pm, edited 2 times in total.
coloin
 
Posts: 1633
Joined: 05 May 2005

PreviousNext

Return to General