Structures of the solution grid

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

Re: Structures of the solution grid

Postby dukuso » Tue Jun 01, 2010 1:29 pm

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

Postby gsf » Tue Jun 01, 2010 1:42 pm

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

Postby eleven » Tue Jun 01, 2010 4:03 pm

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: 1535
Joined: 10 February 2008

Re: Structures of the solution grid

Postby gsf » Tue Jun 01, 2010 4:14 pm

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

Postby eleven » Tue Jun 01, 2010 4:26 pm

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: 1535
Joined: 10 February 2008

Re: Structures of the solution grid

Postby RW » Wed Jun 02, 2010 7:44 am

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

Postby eleven » Wed Jun 02, 2010 11:13 am

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: 1535
Joined: 10 February 2008

Re: Structures of the solution grid

Postby RW » Wed Jun 02, 2010 2:53 pm

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

Postby dobrichev » Thu Jun 03, 2010 12:33 am

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: 1311
Joined: 24 May 2010

Re: Structures of the solution grid

Postby dukuso » Thu Jun 03, 2010 10:05 am

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

Postby gsf » Thu Jun 03, 2010 1:31 pm

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.sudz
sudoku -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

Postby dukuso » Thu Jun 03, 2010 3:46 pm

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

Postby gsf » Thu Jun 03, 2010 4:31 pm

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

Postby dukuso » Thu Jun 03, 2010 4:38 pm

sudoku: %O3#Bn: cannot read
sudoku: %3#An: cannot read
sudoku: %#bc': cannot read
dukuso
 
Posts: 479
Joined: 25 June 2005

Re: Structures of the solution grid

Postby dukuso » Thu Jun 03, 2010 4:46 pm

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

Return to General