The New Sudoku Players' Forum

by **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 (43.71 KiB) Viewed 1300 times

JPF

by **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" ]

by **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.

by **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.

by **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.

by **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.

by **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

by **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" )

by **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

by **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.

by **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

by **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

by **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

by **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.

by **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

The New Sudoku Players' Forum

minimum number of clues per band/stack

Re: minimum number of clues per band/stack

Re: minimum number of clues per band/stack

Re: minimum number of clues per band/stack

Re: minimum number of clues per band/stack

Re: minimum number of clues per band/stack

Re: minimum number of clues per band/stack

Re: minimum number of clues per band/stack

Re: minimum number of clues per band/stack

Re: minimum number of clues per band/stack

Re: minimum number of clues per band/stack

Re: minimum number of clues per band/stack

Re: minimum number of clues per band/stack

Re: minimum number of clues per band/stack

Re: minimum number of clues per band/stack

Re: minimum number of clues per band/stack