## minimum number of clues per band/stack

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

### Re: minimum number of clues per band/stack

champagne wrote:to JPF, I did not see how you attach a file, but this is a side point.

AddaFile.JPG (43.71 KiB) Viewed 562 times

JPF
JPF
2017 Supporter

Posts: 4022
Joined: 06 December 2005
Location: Paris, France

### Re: minimum number of clues per band/stack

coloin wrote:However if you fix the band - to search a single pattern one would have to search many of the 6^4 ways of ordering the band ....... or i am wrong !

No, this is true, basically.
It's better in this case, to keep the band fixed, and permute the columns in the 3+4 part of the pattern.

[ Not every column permutation changes the 3+4 pattern, and sometimes the change can be reversed by a row permutation. ]

Automorphisms for the fixed band, can be exploited too.

coloin wrote:If you fix the band - it is possible to use the 44 ed bands instead of the 416 - the ordering of the vertical 3 clues in the band doesnt matter.

I think the bottom line is that using ganster classes will reduce the problem by a factor of about 20 (maybe 30), and that a 32-core machine would be able to handle it in under a week (3-4 days, maybe less).

For champagne,

To explain the "6^4" factor, You need to think about this: Suppose someone handed you a valid 3+4+27 puzzle. Suppose the 3+4 part didn't match one of the ED forms, and suppose the full band wasn't in any kind of canonical form. How could you show that your code would find the puzzzle, or one of its equivalents.

[ Note: For later, if gangster classes come into play, "equivalent" doesn't mean "isomorphic", but "isomorphic" does imply "equivalent" ]
Last edited by blue on Sat Nov 01, 2014 5:01 am, edited 1 time in total.
blue

Posts: 894
Joined: 11 March 2013

### Re: minimum number of clues per band/stack

coloin wrote:But the 416 -> 44 reduction at least is in our favour.

Right, 44 is sufficient. I mixed 27+4+3 patterns_with_valid_puzzles with valid_puzzles and further with puzzles_with_minimized_clues_in_the_third_band.
dobrichev
2016 Supporter

Posts: 1779
Joined: 24 May 2010

### Re: minimum number of clues per band/stack

blue wrote:For champagne,

To explain the "6^4" factor, You need to think about this: Suppose someone handed you a valid 3+4+27 puzzle. Suppose the 3+4 part didn't match one of the ED forms, and suppose the full band wasn't in any kind of canonical form. How could you show that your code would find the puzzzle, or one of its equivalents.

I like that start and here is my understanding.

We have a ED pattern corresponding to that valid puzzle (we generated all ED patterns). Morph the proposed puzzle to that ED pattern.

Take one box in the 27 clues band having the highest number of column occupied. Relabel rows 1 and 2 in that box to have 12345 in cells 1 to 5
if you are lucky, you can continue relabelling to have 123456789 in row 1, if it does not work, you have to exchange columns (and may be stacks 2 and 3) to come to the sequence 1234456789, the only one you have studied through the 401 minlex starts

I assume that the 44 reduction given by coloin is the worst case.
champagne
2017 Supporter

Posts: 7138
Joined: 02 August 2007
Location: France Brittany

### Re: minimum number of clues per band/stack

I tried to apply the above process to the 1871 ED 3+4+27 patterns having a chance to give puzzles.

I got 66186 patterns, an average 35 pattern per original 1871 ( starting form 72 permutations per original 1871).

I'll test now how long it takes in average to check such a pattern.
champagne
2017 Supporter

Posts: 7138
Joined: 02 August 2007
Location: France Brittany

### Re: minimum number of clues per band/stack

my first test (400 patterns) to check whether a 3+4+27 puzzle exists shows an average speed of 10 puzzles per hour and per core with a 2.8 Ghz computer.

this is 240 patterns per day_core, requiring 276 day_core in total.

If the extrapolation is valid, assuming 10 cores dedicated tot that task, it is one month of computer work.
Something I can try giving up for a while the search of potential hardest and the generation of the 17 clues catalog.
champagne
2017 Supporter

Posts: 7138
Joined: 02 August 2007
Location: France Brittany

### Re: minimum number of clues per band/stack

champagne wrote:I assume that the 44 reduction given by coloin is the worst case.

No this is best case !
One only need to search a representative of each of the 44 [ instead of the 416]
But before you go ahead .....
I still think that the 4+3 pattern has to be represented up to the 6^3 ways - although not for the canonical gangster band - this could be searched significantly more than 4+3 - my initial look showed !
Code: Select all
`+---+---+---+|...|...|...||...|...|...||...|...|...|+---+---+---+|...|...|...||...|...|...||...|...|...|+---+---+---+|147|369|258||258|147|369||369|258|147|+---+---+---+`

Some of the other 44 band representatives will have similar reductions - but I am not sure how many.
The 6^4 is reduced to 6^3 as you can always ? vertical band swop/column swap/relabel
Maybe it is reduced to the extent you have found....
C
coloin

Posts: 1877
Joined: 05 May 2005

### Re: minimum number of clues per band/stack

coloin wrote:
champagne wrote:I assume that the 44 reduction given by coloin is the worst case.

No this is best case !
One only need to search a representative of each of the 44 [ instead of the 416]
But before you go ahead .....
I still think that the 4+3 pattern has to be represented up to the 6^3 ways - although not for the canonical gangster band - this could be searched significantly more than 4+3 - my initial look showed !
Code: Select all
`+---+---+---+|...|...|...||...|...|...||...|...|...|+---+---+---+|...|...|...||...|...|...||...|...|...|+---+---+---+|147|369|258||258|147|369||369|258|147|+---+---+---+`

Some of the other 44 band representatives will have similar reductions - but I am not sure how many.
The 6^4 is reduced to 6^3 as you can always ? vertical band swop/column swap/relabel
Maybe it is reduced to the extent you have found....
C

Hi coloin,

I still have no clear understanding of what is behind your "44". Blue' comment allows in my view a "72" reduction, but with equivalent permutations, to come to my final count with an average of 35 per entry.

Anyway if the list is not exhaustive, missing patterns can be added later.

It would be good to have the final list of the 1871 x 44 (cleaned from "equivalent patterns" )
champagne
2017 Supporter

Posts: 7138
Joined: 02 August 2007
Location: France Brittany

### Re: minimum number of clues per band/stack

dukuso published it here..... but it is displayed rather confusingly.....
sudoku -gB44
which generates
Code: Select all
`c:\Suxx>sudoku-64 -gB4401 12345678945678912378912345602 12345678945678912378912346503 12345678945678912378912356404 12345678945678912378913246505 12345678945678912378913254606 12345678945678912378913256407 12345678945678912378923156408 12345678945678912378923164509 12345678945678912379813254610 12345678945678912379821356411 12345678945678912379821365412 12345678945678912379823156413 12345678945678912379823164514 12345678945678912389723156415 12345678945678913278912354616 12345678945678913278921345617 12345678945678913278921364518 12345678945678913278921365419 12345678945678913278923154620 12345678945678923178912364521 12345678945678923178931245622 12345678945718923668927314523 12345678945718923668927315424 12345678945718923668927351425 12345678945718923668937214526 12345678945718923668937215427 12345678945718923669823751428 12345678945718923669872314529 12345678945718923669873214530 12345678945718923686937214531 12345678945718926368927315432 12345678945718926368972315433 12345678945718926368973215434 12345678945718926396832714535 12345678945718926396832751436 12345678945718926396837214537 12345678945718926398632714538 12345678945718926398632715439 12345678945718962368972314540 12345678945718962368972315441 12345678945718962368972351442 12345678945718963269873251443 12345678945718963289637215444 123456789457289631896137254`

C
coloin

Posts: 1877
Joined: 05 May 2005

### Re: minimum number of clues per band/stack

My first reaction (but I have to take more time to think about it) is that we have here another issue that the point raised by blue.
If my understanding is correct, I have to quickly replace in the search the 401 minlex patterns of the 27 clues band by the 44 gangster patterns, which would speed up significantly the process.
champagne
2017 Supporter

Posts: 7138
Joined: 02 August 2007
Location: France Brittany

### Re: minimum number of clues per band/stack

A quick check confirms why i was confused
taking the 44 bands and adding one clue to each gives 1565 ED {27 + 1}
the most canonical [#1] has one way ... and some have 54 ways to add one clue
here are #1 to #7
Code: Select all
`1234567894567891237891234562.....................................................                                                                                 123456789456789123789123465.......1..............................................123456789456789123789123465.......3..............................................123456789456789123789123465.......4..............................................123456789456789123789123465.......5..............................................123456789456789123789123465......2...............................................123456789456789123789123465......5...............................................123456789456789123789123465.1....................................................123456789456789123789123465.3....................................................123456789456789123789123465.4....................................................123456789456789123789123465.6....................................................123456789456789123789123465.7....................................................123456789456789123789123465.9....................................................1234567894567891237891234652.....................................................1234567894567891237891234655.....................................................1234567894567891237891234658.....................................................                                                                                 123456789456789123789123564......2...............................................123456789456789123789123564......3...............................................123456789456789123789123564......4...............................................123456789456789123789123564......6...............................................1234567894567891237891235642.....................................................1234567894567891237891235643.....................................................1234567894567891237891235645.....................................................1234567894567891237891235646.....................................................1234567894567891237891235648.....................................................1234567894567891237891235649.....................................................                                                                                 123456789456789123789132465.1....................................................123456789456789123789132465.3....................................................123456789456789123789132465.7....................................................123456789456789123789132465.9....................................................1234567894567891237891324652.....................................................1234567894567891237891324658.....................................................                                                                                 123456789456789123789132546.....1................................................123456789456789123789132546.....3................................................123456789456789123789132546.....4................................................123456789456789123789132546.....5................................................123456789456789123789132546.....7................................................123456789456789123789132546.....8................................................123456789456789123789132546....1.................................................123456789456789123789132546....2.................................................123456789456789123789132546....4.................................................123456789456789123789132546....6.................................................123456789456789123789132546....7.................................................123456789456789123789132546....9.................................................123456789456789123789132546...2..................................................123456789456789123789132546...3..................................................123456789456789123789132546...5..................................................123456789456789123789132546...6..................................................123456789456789123789132546...8..................................................123456789456789123789132546...9..................................................123456789456789123789132546.1....................................................123456789456789123789132546.3....................................................123456789456789123789132546.7....................................................1234567894567891237891325462.....................................................1234567894567891237891325463.....................................................1234567894567891237891325465.....................................................1234567894567891237891325466.....................................................1234567894567891237891325468.....................................................1234567894567891237891325469.....................................................                                                                                 123456789456789123789132564........1.............................................123456789456789123789132564........2.............................................123456789456789123789132564........5.............................................123456789456789123789132564........6.............................................123456789456789123789132564........7.............................................123456789456789123789132564........8.............................................123456789456789123789132564.......1..............................................123456789456789123789132564.......3..............................................123456789456789123789132564.......4..............................................123456789456789123789132564.......5..............................................123456789456789123789132564.......7..............................................123456789456789123789132564.......9..............................................123456789456789123789132564......2...............................................123456789456789123789132564......3...............................................123456789456789123789132564......4...............................................123456789456789123789132564......6...............................................123456789456789123789132564......8...............................................123456789456789123789132564......9...............................................123456789456789123789132564.....1................................................123456789456789123789132564.....3................................................123456789456789123789132564.....4................................................123456789456789123789132564.....5................................................123456789456789123789132564.....7................................................123456789456789123789132564.....8................................................123456789456789123789132564....1.................................................123456789456789123789132564....2.................................................123456789456789123789132564....4.................................................123456789456789123789132564....6.................................................123456789456789123789132564....7.................................................123456789456789123789132564....9.................................................123456789456789123789132564...2..................................................123456789456789123789132564...3..................................................123456789456789123789132564...5..................................................123456789456789123789132564...6..................................................123456789456789123789132564...8..................................................123456789456789123789132564...9..................................................123456789456789123789132564..1...................................................123456789456789123789132564..2...................................................123456789456789123789132564..4...................................................123456789456789123789132564..5...................................................123456789456789123789132564..7...................................................123456789456789123789132564..8...................................................123456789456789123789132564.1....................................................123456789456789123789132564.3....................................................123456789456789123789132564.4....................................................123456789456789123789132564.6....................................................123456789456789123789132564.7....................................................123456789456789123789132564.9....................................................1234567894567891237891325642.....................................................1234567894567891237891325643.....................................................1234567894567891237891325645.....................................................1234567894567891237891325646.....................................................1234567894567891237891325648.....................................................1234567894567891237891325649.....................................................123456789456789123789231564...1..................................................123456789456789123789231564...3..................................................123456789456789123789231564...5..................................................123456789456789123789231564...6..................................................123456789456789123789231564...8..................................................123456789456789123789231564...9..................................................1234567894567891237892315642.....................................................1234567894567891237892315643.....................................................1234567894567891237892315648.....................................................1234567894567891237892315649.....................................................`

This gives us an idea of the automorphisms of the bands
But the average is 36.1- which agrees with yours !

Maybe some representative gangsters are more automorphic ? Is this possible ?
C
coloin

Posts: 1877
Joined: 05 May 2005

### Re: minimum number of clues per band/stack

Another point is that the 401 list of starts given by gsf for the catalog of solutions is already a minlex form of the band.

To go from the 401 to the 44 gangsters, you have mainly to consider, if I am right, columns exchanges within a stack and stacks permutations , what I would not do here, So for the time being, I see at the end small chances to reduce the count through the gangster view.I am comparing both lists to be sure to catch all the potential for a reduction of the count
champagne
2017 Supporter

Posts: 7138
Joined: 02 August 2007
Location: France Brittany

### Re: minimum number of clues per band/stack

champagne wrote:Another point is that the 401 list of starts given by gsf for the catalog of solutions ...........

gsf wrote:the bands with 0 elements are { 395 397 398 400 402 403 404 406 408 409 410 412 413 414 415 } .....

doesn't this just mean there arn't any grid solutions with minlex start offs - I don't think it can mean that it can't have a puzzle !! ??

If you have 2 completed bands e.g
Code: Select all
`+---+---+---+|123|456|789||945|178|623||786|239|154|+---+---+---+|698|327|415||231|945|867||457|681|932|+---+---+---+|...|...|...||...|...|...||...|...|...|+---+---+---+`

the grid solution count is 264 solutions, of which at least x6 will be isomorphic
Band 3 will all be the same gangster , but may well be a different band of the ED 416.

Take all these 3rd band / solutions .... in isolation
- they will have identical total grid solution counts.
- if you add clues to the other 2 bands to form a valid puzzle - these same added clues will give a valid puzzle when combined with the another of the 3rd bands.
- all these 3rd bands have the same tuple of 3 clues in the vertical minirow. There are the same 6 clue options in all the cells in the empty bands.
C
coloin

Posts: 1877
Joined: 05 May 2005

### Re: minimum number of clues per band/stack

coloin wrote:
champagne wrote:Another point is that the 401 list of starts given by gsf for the catalog of solutions ...........

gsf wrote:the bands with 0 elements are { 395 397 398 400 402 403 404 406 408 409 410 412 413 414 415 } .....

doesn't this just mean there arn't any grid solutions with minlex start offs - I don't think it can mean that it can't have a puzzle !! ??

It means that you have no solution grid with that start (if I remember properly, another one has only one solution).

But if you have no solution grid , how can you build a valid puzzle in a x+y+27 using that start?
A valid puzzle has a solution. if the 27 are given, they are part of the solution.
champagne
2017 Supporter

Posts: 7138
Joined: 02 August 2007
Location: France Brittany

### Re: minimum number of clues per band/stack

No. gsf is definitely saying that there are no min lex grids starting with those 15 bands.
All bands have around 100 M gridsolutions.
It looks like some gangsters will be a lot easier to search than others......
C
coloin

Posts: 1877
Joined: 05 May 2005

PreviousNext