The New Sudoku Players' Forum

[champagne]

this can be redundant wit an old thread, but I needed some fresh view on it.

the general context is
given a grid filled for the 2 first bands, how can you fill the third one quickly.

Any such band 3 to fill starts with one the the 44 gangsters, so the first step can be to see what happens for each of them in their min lexical form.

I made a first investigation using a template approach and got this (to check)

Hidden Text: Show

Code: Select all

minlex gangster; number of ED valid bands

123456789123456789123456789;288
123456789123456789123457689;96
123456789123456789124357689;32
123456789123456789124378569;32
123456789123456789147258369;16
123456789123457689123458679;96
123456789123457689123468579;144
123456789123457689124356789;32
123456789123457689124358679;32
123456789123457689124367589;32
123456789123457689124368579;48
123456789123457689124389567;32
123456789123457689126345789;32
123456789123457689126347589;32
123456789123457689126348579;48
123456789123457689145267389;16
123456789123457689145268379;24
123456789123457689146258379;28
123456789123457689148259367;24
123456789124357689125348679;32
123456789124357689125367489;24
123456789124357689125368479;28
123456789124357689125378469;44
123456789124357689126358479;24
123456789124357689126378459;28
123456789124357689126389457;24
123456789124357689128345679;32
123456789124357689128356479;28
123456789124357689128359467;20
123456789124357689134258679;32
123456789124357689134268579;48
123456789124357689135268479;38
123456789124357689135278469;46
123456789124357689136258479;28
123456789124357689136278459;30
123456789124357689137268459;36
123456789124357689138259467;26
123456789124357689138269457;38
123456789124357689158267349;20
123456789124378569129356478;16
123456789124378569135279468;32
123456789124378569137245689;86
123456789124378569157268349;28
123456789147258369159267348;20

The table shows a maximum of 288 valid fills. I knew from blue's exchanges that the maximum was below 256 and I have seen in the 17 clues search the 288, so the table could be correct.

My template filling process is relatively basic

Lock the column one,
try each of the 6 permutations in column 2
the try each of the 6 permutations in column 3

for each of the nine cells of the box 1, the 2 valid patterns in boxes 2 and 3 are compared to the valid patterns of the previous cell assigned.
The 288 of the first gangster is easily explained in this sequence.
In the first pattern, each set of three digit appears in three columns, one per box. The templates of 2 different columns in box 1 are disjoints.
for one permutation in one column, we have 2 possible pattern (as soon as 2 boxes are assigned for the first digit, the three digits are fully assigned).

The first column has 2 possible fills
for the columns 2 and 3 we have 6 permutations of the digits, each with 2 fills

2x(6x2)x(6x2)= 288 possible fills.


And this appears to be by far the highest count per gangster if my table is correct

[coloin]

Historically, there was confusion as to the classification of the gangsters....as dukuso and gsf and other programs differed.
Please could you confirm what is the accepted representation of each gangster / double gangster.

Those gang of 44 which you posted arnt valid bands and are not easy interpreted !

[champagne]

Historically, there was confusion as to the classification of the gangsters....as dukuso and gsf and other programs differed.
Please could you confirm what is the accepted representation of each gangster / double gangster.

Those gang of 44 which you posted arnt valid bands and are not easy interpreted !

As far as I remember, the above list has the same design as what I got years ago from blue.
Each gangster is shown as 9 triplets in increasing order within the triplet.

So the first one can be shown as 9 columns having the digits

Code: Select all

123 456 789  123 456 789  123 456 789


with one example of 2 fills

Code: Select all

147 369 258
258 147 369
369 258 147

147 258 369
258 369 147
369 147 258 

[coloin]

a few mins searching ... I did it with gsfs program
sudoku-64 -gB44 from here , which points to the slight confusion

Hidden Text: Show

Code: Select all

123456789456789123789123456...................................................... ## 01
123456789456789123789123465...................................................... ## 02
123456789456789123789123564...................................................... ## 03
123456789456789123789132465...................................................... ## 04
123456789456789123789132546...................................................... ## 05
123456789456789123789132564...................................................... ## 06
123456789456789123789231564...................................................... ## 07
123456789456789123789231645...................................................... ## 08
123456789456789123798132546...................................................... ## 09
123456789456789123798213564...................................................... ## 10
123456789456789123798213654...................................................... ## 11
123456789456789123798231564...................................................... ## 12
123456789456789123798231645...................................................... ## 13
123456789456789123897231564...................................................... ## 14
123456789456789132789123546...................................................... ## 15
123456789456789132789213456...................................................... ## 16
123456789456789132789213645...................................................... ## 17
123456789456789132789213654...................................................... ## 18
123456789456789132789231546...................................................... ## 19
123456789456789231789123645...................................................... ## 20
123456789456789231789312456...................................................... ## 21
123456789457189236689273145...................................................... ## 22
123456789457189236689273154...................................................... ## 23
123456789457189236689273514...................................................... ## 24
123456789457189236689372145...................................................... ## 25
123456789457189236689372154...................................................... ## 26
123456789457189236698237514...................................................... ## 27
123456789457189236698723145...................................................... ## 28
123456789457189236698732145...................................................... ## 29
123456789457189236869372145...................................................... ## 30
123456789457189263689273154...................................................... ## 31
123456789457189263689723154...................................................... ## 32
123456789457189263689732154...................................................... ## 33
123456789457189263968327145...................................................... ## 34
123456789457189263968327514...................................................... ## 35
123456789457189263968372145...................................................... ## 36
123456789457189263986327145...................................................... ## 37
123456789457189263986327154...................................................... ## 38
123456789457189623689723145...................................................... ## 39
123456789457189623689723154...................................................... ## 40
123456789457189623689723514...................................................... ## 41
123456789457189632698732514...................................................... ## 42
123456789457189632896372154...................................................... ## 43
123456789457289631896137254...................................................... ## 44


They are in minlex order it seems ....is this the version which you are using ?

If so we need the min lex version of the 44 { [983,959,110 ED double bands - blue] ] double bands

[champagne]

a few mins searching ... I did it with gsfs program

They are in minlex order it seems ....is this the version which you are using ?

your list is in minlex order of the smallest fill I assume. I am using the list that I posted above.
As I have doubt that the ranks are the same in the 2 lists, this can be a source of trouble in the communication.

The list that I use is more in line with what I have to do. I picked it somewhere in the forum.

[coloin]

Here is the DB from the #0001 grid in the catalogue which had 288x6=1728 solutions

Code: Select all

+---+---+---+
|123|456|789|
|456|789|123|
|789|123|456|
+---+---+---+
|214|365|897|
|365|897|214|
|897|214|365|
+---+---+---+
|...|...|...|
|...|...|...|
|...|...|...|
+---+---+---+

123456789456789123789123456214365897365897214897214365........................... #1

So this would be Ganster DB 1 [of 44] which is pertinant to your first post.....
But i guess a representative of each would be good to define

[dobrichev]

Hi Gerard,

...
Any such band 3 to fill starts with one the the 44 gangsters, so the first step can be to see what happens for each of them in their min lexical form.

Could you please specify exactly what are you min-lexing?
If you min-lex any band 3, the result is one of the 416 bands, and all solutions of a grid with fixed bands 1 and 2 will result in a band that maps to the same gangster.
Then your table must sum up to 416 (now the sum is 1892 which could be a programming error if my assumption is correct).
If you solve only bands 1,2 that minlex grids statrs with, then not all 44 gangsters or all 416 bands are expected to appear.

Gangsters, unlike bands, take into account only row positions of the cells and ignore column positions. A band corresponds to exactly one gangster.

The above quote could be transformed to

Any such band to fill starts with represents one of the 44 gangsters, so the first step can be to see what happens for each of them in their min lexical form how many gangsters actually exist for band 3 in minlex grid catalog.

[champagne]

Hi mladen,

Could you please specify exactly what are you min-lexing?

I continue to study how this could improve my catalog builder, so the min lexical form refers to the final sequence of the solution grids filled out of a given bands 1+2. The count made in the opening post was not created with the same sequence.

If you min-lex any band 3, the result is one of the 416 bands, and all solutions of a grid with fixed bands 1 and 2 will result in a band that maps to the same gangster.
Then your table must sum up to 416 (now the sum is 1892 which could be a programming error if my assumption is correct).

A said above, we don't try to "min lex" the band 3, but the whole solution grid.
Each gangster must be seen alone, but the sum is interesting just because it is a relatively low number. In place of the template expansion, we have the possibility to recognize the gangster of the band 3 and to morph the known gangster solutions.

Gangsters, unlike bands, take into account only row positions of the cells and ignore column positions. A band corresponds to exactly one gangster.

???
for me the write wording is
Gangsters, unlike bands, take into account only columns positions of the cells and ignore rows positions.
And yes, a band belongs to one gangster class.

[champagne]

Hi coloin,

Here is the DB from the #0001 grid in the catalogue which had 288x6=1728 solutions

123456789456789123789123456214365897365897214897214365........................... #1

So this would be Ganster DB 1 [of 44] which is pertinant to your first post.....
But i guess a representative of each would be good to define

I assume that your 1728 solutions ignore the constraint to have the column one sorted.
And yes, it will be good to have all the ED fills shown, what I intend to do in the next step.

[dobrichev]

OK, I meant cell positions within the row are accounted and cell positions within the column aren't.
Now I am confused what are you counting.

[champagne]

Now I am confused what are you counting.

What is counted is the ED number of ways to fill a gangster. As asked coloin, the list of the fills will help. So far, my draft just gives the count.

To have ED fills, it is enough to lock digits in cells in the first column. Then, the sudoku constraints produce ED fills.
In my draft, to count ,I apply more or less your templates view.

Each cell assignment for a digit in the first box has 2 possible patterns in the other boxes.
The start is done using the 3 cells assignments (locked)in the first column. All possible {3 disjoints patterns} are searched (2 to 8 possibilities)
Then, the six remaining cells in columns 2 and 3 are assigned and the tables of disjoints pattern is updated with a growing number of cells assigned in the boxes 2 and 3.

The final table contains all possible fills expressed as patterns. Is missing in the current code the digits assignments corresponding to the pattern.

[coloin]

I maybe understand what you are proposing... you have chosen the worst case scenario with #1

Having added 2 rows to a band1 plus row4 ....You are trying to optimize the generation of the last 3 rows in the catalogue.... which is already quite fast !
We can easily generate the solution count for a representative of all 44 ganster DoubleBands [six rows].
However there would be a morphing issue to tally it up to a specific DoubleBand[DB]

Each DoubleBand will have a gangster completion of 3 boxes of 3 ordered tuples of 3 clues,
With no fixed clues, there would be 84 possibilities for col1, 20 for col2 and 1 for col3. and similarly for the other 2 boxes .... which is too many options

Sorting / fixing column 1 in band 3 reduces the solution count by a factor of six.

Sorting column 1 in band 3, is 3 of 356789 , 10 of the 20 options depend on the clue at r3c1 ,..
In col1 there may be vertical tuples of 356,357,358,359,367,368,369,378,379,389,567,568,569,578,579,589,678,679,689,789. [ maybe some wont be there]

Perhaps to reduce things to a more manageable size
For a specific band 1 there would be much reduced options for each band 3 mini column ... so that would be possible to generate all the possible tuples in band 3 and attribute a solution count ...
col1 10 tuple options
coll 2 1-20 options depending on col1
col3 1 option
col4 20 options
col5 1-20 options depending on col4
col6 1 option
col7 20 options
col8 1-20 options depending on col7
col9 1 option

and some options possibly wont occur in the catalogue

[champagne]

Hi coloin,
You have a goo idea of what I try to do . More precisely,

I don't change the code till the DB (double band) generation and validity check.
At this point,
I am left with the gangster in band3 , one of the 44 but not the minlex form
And the column 1 is locked, the three digit must be in increasing order.
Here I have three options to get the valid fills

a) as now, continue to expand cell by cell
b) expand using the template approach, and sort the solutions when it is necessary to stay in the minlex order of the solutions for the whole grid
c) Get the parameters to morph the band 3 to the appropriate 44 and use the tables describing the valid solutions

If my results in the opening post are correct, the option c) could be very efficient.
In most cases, the number of possible fills is in the range 20-50.
For each fill, the band 3 index is known. This reduce the number of possible fills knowing that this index must be lower than the band 1 index.

My priority in the next days will be to see how I can detect quickly the necessary morphing and how to design the tables to apply the c)
But in any case, we need the list of fills, not only the count, so this is part of the todo list.

[coloin]

I see now and the first post makes sense now !
You want the solutions to band 3 but you want to collect only those which are in the min lex catalogue ... ahh that would be option b.

perhaps looking at the 416/416/416 last entry

Code: Select all

123456789457893612986217354274538196531964827698721435342685971715349268869172543 #5472730538

it has 144 sols but only one in the catalogue !

Code: Select all

1234567894578936129862173542745381965319648276987214353........7........8........ 

+---+---+---+
|123|456|789|
|457|893|612|
|986|217|354|
+---+---+---+
|274|538|196|
|531|964|827|
|698|721|435|
+---+---+---+
|3..|...|...|
|7..|...|...|
|8..|...|...|
+---+---+---+   144 sols  {DB gangster#?]

possible 3 tupels

Code: Select all

3 1 2    1 4 2    2 4 1
7 4 5    6 7 5    5 6 3
8 6 9    3 8 9    9 7 8


Code: Select all

Adding the 3 template  [ 2 ways]                                                       
+---+---+---+                                     +---+---+---+               
|123|456|789|                                     |123|456|789|               
|457|893|612|                                     |457|893|612|               
|986|217|354|                                     |986|217|354|               
+---+---+---+                                     +---+---+---+               
|274|538|196|                                     |274|538|196|               
|531|964|827|                                     |531|964|827|               
|698|721|435|                                     |698|721|435|               
+---+---+---+                                     +---+---+---+               
|3..|...|...|                                     |3..|...|...|               
|7..|3..|...|                                     |7..|...|..3|               
|8..|...|..3|                                     |8..|3..|...|               
+---+---+---+                                     +---+---+---+               
                                                                               
Adding the 7 template  [ 2 x 2 ways]                                             
                                                                               
+---+---+---+                    +---+---+---+    +---+---+---+   +---+---+---+
|123|456|789|                    |123|456|789|    |123|456|789|   |123|456|789|
|457|893|612|                    |457|893|612|    |457|893|612|   |457|893|612|
|986|217|354|                    |986|217|354|    |986|217|354|   |986|217|354|
+---+---+---+                    +---+---+---+    +---+---+---+   +---+---+---+
|274|538|196|                    |274|538|196|    |274|538|196|   |274|538|196|
|531|964|827|                    |531|964|827|    |531|964|827|   |531|964|827|
|698|721|435|                    |698|721|435|    |698|721|435|   |698|721|435|
+---+---+---+                    +---+---+---+    +---+---+---+   +---+---+---+
|3..|...|.7.|                    |3..|.7.|...|    |3..|.7.|...|   |3..|...|.7.|
|7..|3..|...|                    |7..|3..|...|    |7..|...|..3|   |7..|...|..3|
|8..|.7.|..3|                    |8..|...|.73|    |8..|3..|.7.|   |8..|37.|...|
+---+---+---+                    +---+---+---+    +---+---+---+   +---+---+---+
                                                                               
Adding the 8 template                                                         
                                                                               
+---+---+---+   +---+---+---+    +---+---+---+    +---+---+---+   +---+---+---+
|123|456|789|   |123|456|789|    |123|456|789|    |123|456|789|   |123|456|789|
|457|893|612|   |457|893|612|    |457|893|612|    |457|893|612|   |457|893|612|
|986|217|354|   |986|217|354|    |986|217|354|    |986|217|354|   |986|217|354|
+---+---+---+   +---+---+---+    +---+---+---+    +---+---+---+   +---+---+---+
|274|538|196|   |274|538|196|    |274|538|196|    |274|538|196|   |274|538|196|
|531|964|827|   |531|964|827|    |531|964|827|    |531|964|827|   |531|964|827|
|698|721|435|   |698|721|435|    |698|721|435|    |698|721|435|   |698|721|435|
+---+---+---+   +---+---+---+    +---+---+---+    +---+---+---+   +---+---+---+
|3..|.8.|.7.|   |3..|...|.78|    |3..|.7.|..8|    |3..|.7.|..8|   |3..|...|.78|
|7..|3..|..8|   |7..|38.|...|    |7..|38.|...|    |7..|.8.|..3|   |7..|.8.|..3|
|8..|.7.|..3|   |8..|.7.|..3|    |8..|...|.73|    |8..|3..|.7.|   |8..|37.|...|
+---+---+---+   +---+---+---+    +---+---+---+    +---+---+---+   +---+---+---+
      |                                                                       
      V                                                                       
+---+---+---+                                                                 
|123|456|789|                                                                 
|457|893|612|                                                                 
|986|217|354|                                                                 
+---+---+---+                                                                 
|274|538|196|                                                                 
|531|964|827|                                                                 
|698|721|435|                                                                 
+---+---+---+                                                                 
|34.|68.|.71|                                                                 
|71.|34.|.68|                                                                 
|86.|17.|.43|                                                                 
+---+---+---+   .........................

The solution band which might be in the catalogue needs to be band 416 ..but it might have some vertical bands with a higher order ?
I dont see how option c can do this minlex check either.
Brute forcing, by any method, all the possible solutions followed by min lexing and taking the lower order grids seems to be quite fast.

[champagne]

Hi coloin,

As I am more thinking of a c) implementation, I wanted first to have on example of a full implementation.

I tested the draft on the gangster 5 (index 4 of 0-43) of my opening post.

Code: Select all

123456789123456789147258369

this gangster fits with 2 of the 416 band and 16 fills have been found here.
here is the list

fill;gangster index,count within the gangster,band index 0_415

Code: Select all

148269753259347186367158429;4;1,403
148359726259167483367248159;4;2,403
149268753257349186368157429;4;3,403
149358726257169483368247159;4;4,403
157269483268347159349158726;4;5,403
157368429268149753349257186;4;6,403
158367429269148753347259186;4;7,403
158349726269157483347268159;4;8,403
159348726267159483348267159;4;9,26
159267483267348159348159726;4;10,26
167259483248367159359148726;4;11,403
167358429248169753359247186;4;12,403
168357429249168753357249186;4;13,26
168249753249357186357168429;4;14,26
169248753247359186358167429;4;15,403
169257483247368159358149726;4;16,403

We have here the 2 expected bands 1, index 26 and index 403.

Looking for a minlex solution grid,
If the band 1 index (known in the process) is higher than 26, the list of possible fills is reduced to 12,
and we have no valid fill if the band1 index is higher than 403.
I'll post to-day or to-morrow the entire file of possible fills.

Not shown here, we have the mapping to do to reach the canonical morph of the relevant band.
I'll be busy this week, but I could find enough time to see if the code is better using the c) approach.