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

Postby JPF » Fri Oct 31, 2014 10:59 pm

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

AddaFile.JPG
AddaFile.JPG (43.71 KiB) Viewed 360 times


JPF
JPF
2017 Supporter
 
Posts: 3752
Joined: 06 December 2005
Location: Paris, France

Re: minimum number of clues per band/stack

Postby blue » Fri Oct 31, 2014 11:44 pm

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: 573
Joined: 11 March 2013

Re: minimum number of clues per band/stack

Postby dobrichev » Sat Nov 01, 2014 3:02 am

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

Re: minimum number of clues per band/stack

Postby champagne » Sat Nov 01, 2014 10:15 am

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: 5653
Joined: 02 August 2007
Location: France Brittany

Re: minimum number of clues per band/stack

Postby champagne » Sun Nov 02, 2014 11:50 am

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: 5653
Joined: 02 August 2007
Location: France Brittany

Re: minimum number of clues per band/stack

Postby champagne » Mon Nov 03, 2014 7:25 am

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: 5653
Joined: 02 August 2007
Location: France Brittany

Re: minimum number of clues per band/stack

Postby coloin » Mon Nov 03, 2014 11:27 am

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: 1633
Joined: 05 May 2005

Re: minimum number of clues per band/stack

Postby champagne » Mon Nov 03, 2014 12:01 pm

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: 5653
Joined: 02 August 2007
Location: France Brittany

Re: minimum number of clues per band/stack

Postby coloin » Mon Nov 03, 2014 12:18 pm

dukuso published it here..... but it is displayed rather confusingly.....
later on in that thread
gsf helpfully gave us
sudoku -gB44
which generates
Code: Select all
c:\Suxx>sudoku-64 -gB44
01 123456789456789123789123456
02 123456789456789123789123465
03 123456789456789123789123564
04 123456789456789123789132465
05 123456789456789123789132546
06 123456789456789123789132564
07 123456789456789123789231564
08 123456789456789123789231645
09 123456789456789123798132546
10 123456789456789123798213564
11 123456789456789123798213654
12 123456789456789123798231564
13 123456789456789123798231645
14 123456789456789123897231564
15 123456789456789132789123546
16 123456789456789132789213456
17 123456789456789132789213645
18 123456789456789132789213654
19 123456789456789132789231546
20 123456789456789231789123645
21 123456789456789231789312456
22 123456789457189236689273145
23 123456789457189236689273154
24 123456789457189236689273514
25 123456789457189236689372145
26 123456789457189236689372154
27 123456789457189236698237514
28 123456789457189236698723145
29 123456789457189236698732145
30 123456789457189236869372145
31 123456789457189263689273154
32 123456789457189263689723154
33 123456789457189263689732154
34 123456789457189263968327145
35 123456789457189263968327514
36 123456789457189263968372145
37 123456789457189263986327145
38 123456789457189263986327154
39 123456789457189623689723145
40 123456789457189623689723154
41 123456789457189623689723514
42 123456789457189632698732514
43 123456789457189632896372154
44 123456789457289631896137254

C
coloin
 
Posts: 1633
Joined: 05 May 2005

Re: minimum number of clues per band/stack

Postby champagne » Mon Nov 03, 2014 12:44 pm

Now I see your point.

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: 5653
Joined: 02 August 2007
Location: France Brittany

Re: minimum number of clues per band/stack

Postby coloin » Mon Nov 03, 2014 1:19 pm

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: 1633
Joined: 05 May 2005

Re: minimum number of clues per band/stack

Postby champagne » Mon Nov 03, 2014 2:16 pm

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: 5653
Joined: 02 August 2007
Location: France Brittany

Re: minimum number of clues per band/stack

Postby coloin » Mon Nov 03, 2014 3:20 pm

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: 1633
Joined: 05 May 2005

Re: minimum number of clues per band/stack

Postby champagne » Mon Nov 03, 2014 3:49 pm

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: 5653
Joined: 02 August 2007
Location: France Brittany

Re: minimum number of clues per band/stack

Postby coloin » Wed Nov 05, 2014 6:26 pm

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: 1633
Joined: 05 May 2005

PreviousNext

Return to General