## Structures of the solution grid

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

### Re: Structures of the solution grid

not much hope to find more fruit on the 9*9-tree
but maybe the method is useful for 16*16

Presumably it had been done for Latin Squares ?!

rookeries = k-plexes
dukuso

Posts: 479
Joined: 25 June 2005

### Re: Structures of the solution grid

dukuso wrote:not much hope to find more fruit on the 9*9-tree
but maybe the method is useful for 16*16

Presumably it had been done for Latin Squares ?!

rookeries = k-plexes

well I do have one more hope for the 9*9 17s:
that we can prove that all have been found
gsf
2014 Supporter

Posts: 7306
Joined: 21 September 2005
Location: NJ USA

### Re: Structures of the solution grid

Nice idea.
But as i understand it, this method would not find all 17's (only those, where 10 givens are from 3 dgits).
Last edited by eleven on Tue Jun 01, 2010 4:19 pm, edited 1 time in total.
eleven

Posts: 2031
Joined: 10 February 2008

### Re: Structures of the solution grid

eleven wrote:Nice idea.
But as i understand it, this method would not find all 17's (not those with less than 5 digits, which only have 1 given).

I figure it would be a divide and conquer situation
where we could assert: all 17s of this type have been counted up to isomorphism, now on to the next type ...
gsf
2014 Supporter

Posts: 7306
Joined: 21 September 2005
Location: NJ USA

### Re: Structures of the solution grid

Ok, the last type would be 2 digits, which solve a 3-rookery, and placing 15 out of 6 numbers in the 6-rookery.
There is much between ...
eleven

Posts: 2031
Joined: 10 February 2008

### Re: Structures of the solution grid

eleven wrote:Ok, the last type would be 2 digits, which solve a 3-rookery, and placing 15 out of 6 numbers in the 6-rookery.
There is much between ...

Not really. Once you've done 7 clues in a 6-rookery, then repeat it for 8, 9 10 and 11 clues in a 6-rookery and I think we have them all. For the later searches you can limit the search to puzzles with specific digit distributions, for example the last stage only needs to look for puzzles with the distribution 222222221.

RW
RW
2010 Supporter

Posts: 1000
Joined: 16 March 2006

### Re: Structures of the solution grid

You are right with the clue numbers "between", but the cases with more clues in the 6-rookery would need a multiple of the computation time.
Though dukuso and gsf always had surprising fast implementations, i dont think, that all could be calculated in feasible time.
eleven

Posts: 2031
Joined: 10 February 2008

### Re: Structures of the solution grid

Sure, it would take an enormous amount of time. But if gsf sees it plausible to find all puzzles with 7 clues in a 6-rookery, I say go for it! Perhaps that inspires some new ideas that make the rest of the puzzles easier to find...

dukuso wrote:checking gordon's 17s, the minimum numbers of clues required to uniquely
solve a 1,2,..,9 rookery are 0,1,2,3,5,7,10,13,17

If we believe these numbers are true for all 17s, specifically if we believe that a 5-rookery cannot be solved in 4 clues (which I seem to remember is proven already), then the 7 clues in the 6-rookery must have one of the following digit distributions:

011122
111112

If we also assume that a 7-rookery cannot be solved in less than 10 clues, then the remaining 3 digits must have the distribution 334. This should narrow the search quite a bit.

RW
RW
2010 Supporter

Posts: 1000
Joined: 16 March 2006

### Re: Structures of the solution grid

Hi,

I traversed the neighbours of the SF grid (the solution grids which differ from it by only one UA set), then checked for a grids having known 17's. Result is posted here.

MD
dobrichev
2016 Supporter

Posts: 1642
Joined: 24 May 2010

### Re: Structures of the solution grid

do we have a list of all sudokugrids (upto isomorphism, S-classes) with nontrivial
automorphism-group ?
dukuso

Posts: 479
Joined: 25 June 2005

### Re: Structures of the solution grid

dukuso wrote:do we have a list of all sudokugrids (upto isomorphism, S-classes) with nontrivial
automorphism-group ?

this reminds me that I promised to show you some of the sudz-specific options in my solver
still planning to do that ...

these two data files are posted
300-416.sudz
a2.sudz

300-416.sudz are the essentially different grids from bands 300 through 416 inclusive (2,097,068 grids in lexicographic order)
it was generated by
Code: Select all
`sudoku -gb300,416 -f%#ec > 300-416.sudz`

a2.sudz is the list of all essentially different grids with #automorphisms > 1 (560,151 grids in lexicographic order)
it was generated in a directory containing all .sudz files by
Code: Select all
`sudoku -e '(%#An)>1' -f%#ec *.sudz > a2.sudz`

to list all essentially different grids with #automorphisms > 1 with band-index and #automorphisms comment
Code: Select all
`sudoku -f'%v # %03#Bn %#An' a2.sudz`

as a check, these two commands should produce the same output (5,203 lines)
Code: Select all
`sudoku -f'%v # %03#Bn %#An' -e '(%#An)>1' 300-416.sudzsudoku -f'%v # %03#Bn %#An' a2.sudz | grep '# [34]'`
Last edited by gsf on Thu Jun 03, 2010 9:04 pm, edited 1 time in total.
gsf
2014 Supporter

Posts: 7306
Joined: 21 September 2005
Location: NJ USA

### Re: Structures of the solution grid

OK, thanks. 1.9MB only , now decompress ...(how ?)

and then determine the six 416-gangsters in each and the G-class(es) of each
dukuso

Posts: 479
Joined: 25 June 2005

### Re: Structures of the solution grid

dukuso wrote:OK, thanks. 1.9MB only , now decompress ...(how ?)

and then determine the six 416-gangsters in each and the G-class(es) of each

decompress using my solver
example command in previous post
this command is similar but also lists the sorted band signature
Code: Select all
`sudoku -f'%v # %03#Bn %3#An %#bc' a2.sudz`

use %#Bc for the unsorted signature

don't have G-class code in my solver
gsf
2014 Supporter

Posts: 7306
Joined: 21 September 2005
Location: NJ USA

### Re: Structures of the solution grid

dukuso

Posts: 479
Joined: 25 June 2005

### Re: Structures of the solution grid

how many of the ~5.5e9 S-classes have 6(5,..,1) different 416-gangsters in the 6 chutes ?
(~95% of random G-class members)

how many of the ~5.5e9 S-classes have 6(5,..,1) different 44-gangsters in the 6 chutes ?
(~50% of random G-class members)
Last edited by dukuso on Thu Jun 03, 2010 5:15 pm, edited 2 times in total.
dukuso

Posts: 479
Joined: 25 June 2005

PreviousNext