The New Sudoku Players' Forum

[champagne]

Hello,

recently, we had to face a similar issue :

is there a 17 clues in a X + Y + 27 valid puzzle.

Several processes have been tested and the average speed to answer that question appeared to be in a range 1 to several thousands.
The best answer came in less than one millisecond in average using one of the classical available cores (say 3Ghz).

My questions are:

what is the best known process to answer to the same question on a solution grid?
does anybody have clues to find a better process?
What would be to-day the guess for the "best process" average speed?

I have some ideas and I'll come later with my own results, but knowing what has already been achieved can help.

In fact, the answer would be of interest if a throughput of several hundreds of puzzles per second can be reached;
ambitious, but who knows.

[dobrichev]

This is the last estimation from here

... and was able to get the time per grid down to ~22 seconds -vs- 2.8 for 16's.

[champagne]

This is the last estimation from here

... and was able to get the time per grid down to ~22 seconds -vs- 2.8 for 16's.

Hi mladen,

Thanks for that "last estimation". I hope to beat that.

May be one clue derived from a remark (in pm) made by blue writing more or less

" 17 clues solution grids don't behave as the average population of X+Y +27 "

My question on a point very easy to check :

How many disjointed UR threats can appear in a 17 clues solution grid.

I am preparing statistics on that point, but as a first impression, to produce a 17 clues puzzle out of a solution grid, you must have mainly, in the disjointed UAs group, some UAs with many cells.

[dobrichev]

The typical number of mutually disjoint UA sets in a grid with 17s is between 7 and 12. A grid with 18 dj sets is known to exist.
You can scan a grid with "gridchecker --scan --verbose --numclues 14 ..." to list the dj sets. Don't try it on the most canonical grid unless you are extremely patient. For others it works just fine.

[champagne]

The typical number of mutually disjoint UA sets in a grid with 17s is between 7 and 12. A grid with 18 dj sets is known to exist.
You can scan a grid with "gridchecker --scan --verbose --numclues 14 ..." to list the dj sets. Don't try it on the most canonical grid unless you are extremely patient. For others it works just fine.

Hi mladen,

I don't think that the possible breakthrough is directly in the DJ count. (but indirectly yes)

What is for sure is that a solution grid with 18 dj can not produce a 17 clues puzzle, but this has small chances as you say to appear directly.

My point was more that , as far as I can see, a 17 clue solution grid has a very small number (if any) of URs, the smallest UA (4 cells).

In my view, this makes sense. a UR has a small solving power when it receives a given. Reversely, if I am right, when you have a UA with more cells, very often, It contributes generally to solve all cells of the UA. ( a counter example is in UAs of size 18 made of 2 rows or 2 columns of the same band / stack. Such UAs usually having a smaller subset have in fact a small solving power)

[dobrichev]

Take one solution grid.
Compare it to ALL other solution grids and find the differences. You have a collection of 6,670,903,752,021,072,936,959 UA sets, most of them non-minimal.
Compare UA to each other and remove those having other UA as a subset. You have all minimal UA sets for this grid. Their count is in many orders of magnitude less, but it is still huge. Their size is between 4 and 62 and guess how are they distributed.
Find all combinations of mutually disjoint sets, and one with the largest number of UA give you an absolute minimum of the clues you need. It is first order approximation. If you start combining only the small UA then you have a chance to find some large enough combination in reasonable time. You will find about 10 disjoint UA covering almost entire grid.
Find the composite UA sets that require M clues to be hit but include N UA (M<N). For the 27-cell area containing [1,2,3] N=3 and M=2. Shorter similar areas exist. Combinations for N=M are found in the previous step.
Finally, find M for this composite UA81, consisting of all UA, and you are done. Unfortunately in practice this can be done only by trial and error, reducing the search space by using very very limited amount of the above structures.

Increased appetite to the smaller UA is obvious.
In 2010 I counted the UA4 and UA6 for all grids. These with less number of small UA have almost 1000 times more chance to have 17-clue puzzle compared to these with much UA, and about 100 times compared to an average grid.


There are more details here in tables and here in pictures. The discussion was lost in the programmers forum.

[champagne]

Hi mladen,

This has surely be a huge task. However, It's not so easy give a possible use of your complex ratio.

Unfortunately in practice this can be done only by trial and error, reducing the search space by using very very limited amount of the above structures.
Increased appetite to the smaller UA is obvious.
In 2010 I counted the UA4 and UA6 for all grids. These with less number of small UA have almost 1000 times more chance to have 17-clue puzzle compared to these with much UA, and about 100 times compared to an average grid.

These are key sentences. A breakthrough should avoid the trial and error. Even with smallest disjoint UA, you have a huge number of tests.

I made a count of UR's in the known 17 solution grids. I got an average of 7 UR per grid and a maximum of 19, both higher than I expected.

EDIT changed the count of UA_6
I extracted the 6 cells UA's from Gary McGuire's tables and I find only 4 of them (clearing some redundancy part from the original tables and part from some transposed tables I added), which is very low.

I'l study what can be done using as start only UA_4 and UA_6 (I have in mind a possible way to skip the trial and error, but with doubts that it can work)

Code: Select all

{2,{{2,{0,12}},{2,{3,9}}}},    UR         


{3,{{2,{0,12}},{2,{3,18}},{2,{9,21}}}},   
a . .   b   
c . .   a   
b . .   c   

{3,{{2,{0,12}},{2,{3,15}},{2,{6,9}}}},
a  .  .  b  .  .  c
c  .  .  a  .  .  b

{2,{{3,{0,12,24}},{3,{6,9,21}}}},
a  .  .  .  .  . b
b  .  .  a
.  .  .  b  .  . a


{2,{{3,{0,12,29}},{3,{3,11,27}}}},

a  .  .  b  .  .  .
.  .  b  a
.  .  .
b  .  a

[coloin]

The typical number of mutually disjoint UA sets in a grid with 17s is between 7 and 12. A grid with 18 dj sets is known to exist.....
.

I thought that the largest MCN was 16 ......
Although the MC grid has all bands which require 6 clues. [or 3 UA which all require 2 clues] [The MCN is 12]
C

[champagne]

The typical number of mutually disjoint UA sets in a grid with 17s is between 7 and 12. A grid with 18 dj sets is known to exist.....
.

I thought that the largest MCN was 16 ......
Although the MC grid has all bands which require 6 clues. [or 3 UA which all require 2 clues] [The MCN is 12]
C

In the X+T+27 case, the "quick answer" came from UA's of size 2 that appear in a partially solved puzzle.

To have a chance to find a similar process starting from a solution grid, the MCN is surely not the right way, that's why I am concentrating on UA4 UA6.
As a preliminary step, I am working at building a fast way to extract such UAs. (reduced number of permutations ....)

Next step should be to try to work on a partial solutions based on a set of the smallest disjoints UA's to see if UA's of size 2 are coming.

[dobrichev]

I thought that the largest MCN was 16 ......

Maybe you are right, that was from memory...

There is sufficiently efficient code for UA4 and all types of UA6 in gridchecker. With this code I counted these UA for all ED grids for less than 3 hours.

P.S. Look at unavoid.cpp in http://sites.google.com/site/dobrichev/sudokugrids/sudoku_statistics_1.1.zip.

[coloin]

Certainly the higher the max clique number of disjoint UAs the quicker [ usually] it is/was for checker and gridchecker to scan a grid .....
So yes ..... utilizing the u4 and u6 in a solution grid is an initial option ..... though it doesnt preclude 2 clues from the unavoidable set as part of the resultant puzzle.......

well in the x+t+27 case the 4 ED double bands were solvable with 7 clues - so MCN of the double band was </= 7
certainly some double bands will need 12 clues or more
probably most bands will need around 9 or 10 clues ..
taking 6 small UAs and adding 3 or 4 clues to solve was something gridchecker did experimentally some time back.

C

[coloin]

Yes it is 16 - there is hardly room for more than 16 disjoint U4s !!!! never mind a few U6s ....

[champagne]

Yes it is 16 - there is hardly room for more than 16 disjoint U4s !!!! never mind a few U6s ....

A MCN of size 16 gives an average size of 5 for the UA's belonging to the clique.

Knowing that the smallest UA is of size 4 and the next ones of size 6, it is difficult to imagine that such MCN are made of more than just UA4 and UA6 UAs.

Anyway, if what I have in mind can have a chance to work, I need a smaller start, may be just a set of disjoint UR's

[champagne]

There is sufficiently efficient code for UA4 and all types of UA6 in gridchecker. With this code I counted these UA for all ED grids for less than 3 hours.

Hi mladen,

I see that you also wrote a specific code for that UA4 UA 6 issue.

Meantime, I have covered the need, in a different way , but as your code seems easy to use in stand alone mode, I'll try to benchmark both processes.
My priority now will be to try use some of them to look for UA's of size 2

Thanks for the link

Edit just for information, the code I use.
That code in more in line with gridchecker unav12 search.
The main changed are
. permutation limited to what is necessary to find UA2 and UA4
. transposed UAs searched in the same loop as "direct" UAs
. blue prints hard coded

Hidden Text: Show

Code: Select all

   // locate all pairs 81 cells in pos 0 13  (+ transpose) in a 2x2 boxes permutation
    for(int ibr=0;ibr<3;ibr++)   for(int ipr1=0;ipr1<6;ipr1++) for(int ipr2=0;ipr2<3;ipr2++)
   for(int ibc=0;ibc<3;ibc++)  for(int ipc1=0;ipc1<6;ipc1++) for(int ipc2=0;ipc2<3;ipc2++){
      rows=tp_3_6_3_3[54*ibr+9*ipr1+3*ipr2];
      cols=tp_3_6_3_3[54*ibc+9*ipc1+3*ipc2];
      int a=  9*rows[0] + cols[0] , b=  9*rows[0] + cols[3],
         c=  9*rows[1] + cols[0] , d=  9*rows[1] + cols[3] ,
         b1= 9*rows[3] + cols[0] ,
         c1= 9*rows[0] + cols[1] , d1= 9*rows[3] + cols[1];

      if(puz[a] == puz[d] ){
         if(puz[c] ==puz[ b ]){// this is a UR, load it and check for redundancy
            tua46.AddUA4(a,b,c,d );
         }

         else{// try a 6 cells UA
            //a . .   b     
            //c . .   a     
            //b . .   c
            int  e=9*rows[2] + cols[0] , f=  9*rows[2] + cols[3];
            if(puz[e]==puz[b] && puz[c]== puz[f]){
               if(tua46.AddUA6(a,b,c,d,e,f ))
                  cout << "UA type2 rows "
                  << (int) rows[0] << " " << (int) rows[1]<< (int) rows[2] << " "
                  << " cols  "   << (int) cols[0] << " " << (int) cols[3] << " "
                  <<puz[a ]<<puz[b ]<< puz[e]<<endl;
            }
            else{ // try that one in all columns box 3
               //a  .  .  b  .  .  c   
               //c  .  .  a  .  .  b
                e= 9*rows[0] + cols[6] ;
                f= 9*rows[1] + cols[6];
                if(puz[e]==puz[c] && puz[b]== puz[f]){
                   if(tua46.AddUA6(a,b,c,d,e,f ))
                     cout << "UA type2 rows "
                        << (int) rows[0] << " " << (int) rows[1]<< (int) rows[2] << " "
                         << " cols  "   << (int) cols[0] << " " << (int) cols[3] << " "
                         << (int) cols[6] << " "
                        <<puz[a ]<<puz[b ]<< puz[e]<<endl;
                }
                else if(puz[e+1]==puz[c] && puz[b]== puz[f+1]){
                   tua46.AddUA6(a,b,c,d,e+1,f+1 );
                }
                else if(puz[e+2]==puz[c] && puz[b]== puz[f+2]){
                   tua46.AddUA6(a,b,c,d,e+2,f+2 );
                }
                else {
                   //a  .  .  .  .  . b
                   //b  .  .  a
                   //.  .  .  b  .  . a
                    f= 9*rows[2] + cols[6];
                   int g=9*rows[2] + cols[3];
                   if(puz[a]==puz[f] && puz[c]== puz[g] && puz[c]== puz[e])
                      tua46.AddUA6(a,c,d,e,f,g );
                   else if (puz[a]==puz[f+1] && puz[c]== puz[g] && puz[c]== puz[e+1])
                      tua46.AddUA6(a,c,d,e+1,f+1,g );
                   else if (puz[a]==puz[f+2] && puz[c]== puz[g] && puz[c]== puz[e+2])
                      tua46.AddUA6(a,c,d,e+2,f+2,g );
                   else{
                   //a  .  .  b       
                   //.  .  b  a       
                   //.  .  .
                   //b  .  a
                      e=9*rows[3] + cols[0];
                      f=9*rows[3] + cols[2];
                      g=9*rows[1] + cols[2];
                      if (puz[a]==puz[f] && puz[b]== puz[g] && puz[b]== puz[e])
                      tua46.AddUA6(a,b,d,e,f,g );
                   }
                }
            }
         }
      }// end direct
      
      if( puz[a] == puz[d1]) {
         if( puz[c1] == puz[b1]){// transposed UR
            tua46.AddUA4(a, b1,c1,d1);
         }
         else {// try a 6 cells  transposed UA
            //a . .   b     acb        a   c1
            //c . .   a     ...
            //b . .   c     bac        b1  d1
            int  e=9*rows[0] + cols[2] , f=  9*rows[3] + cols[2];
            if(puz[e]==puz[b1] && puz[c1]== puz[f]){
               if(tua46.AddUA6(a,b1,c1,d1,e,f ))
                  cout << "UA type2 rows "
                  << (int) rows[0] << " " << (int) rows[3]
                  << " cols  "   << (int) cols[0] << " " << (int) cols[1] << " "<< (int) cols[2] << " "
                  <<puz[a ]<<puz[b ]<< puz[e]<<endl;
            }
            else{ // try that one in all columns box 3
               //a  .  .  b  .  .  c       a  b1  e
               //c  .  .  a  .  .  b       c1 d1  f
                e= 9*rows[6] + cols[0] ;
                f= 9*rows[6] + cols[1];
                if(puz[e]==puz[c1] && puz[b1]== puz[f]){
                   tua46.AddUA6(a,b1,c1,d1,e,f );
                }
                else if(puz[e+9]==puz[c1] && puz[b1]== puz[f+9]){
                   tua46.AddUA6(a,b1,c1,d1,e+9,f+9 );
                }
                else if(puz[e+18]==puz[c1] && puz[b1]== puz[f+18]){
                   tua46.AddUA6(a,b1,c1,d1,e+18,f+18 );
                }
                else {
                   //a  .  .  .  .  . b         a    b1   e
                   //b  .  .  a                 c1   d1 
                   //.  .  .  b  .  . a              g    f
                    f= 9*rows[6] + cols[2];
                   int g=9*rows[3] + cols[2];
                   if(puz[a]==puz[f] && puz[c1]== puz[g] && puz[c1]== puz[e])
                      tua46.AddUA6(a,c1,d1,e,f,g );
                   else if (puz[a]==puz[f+9] && puz[c1]== puz[g] && puz[c1]== puz[e+9])
                      tua46.AddUA6(a,c1,d1,e+9,f+9,g );
                   else if (puz[a]==puz[f+18] && puz[c1]== puz[g] && puz[c1]== puz[e+18])
                      tua46.AddUA6(a,c1,d1,e+18,f+18,g );
                   else{
                   //a  .  .  b             a        e
                   //.  .  b  a                    g d1     
                   //.  .  .
                   //b  .  a                b1     f   
                      e=9*rows[0] + cols[3];
                      f=9*rows[2] + cols[3];
                      g=9*rows[2] + cols[1];
                      if (puz[a]==puz[f] && puz[b1]== puz[g] && puz[b1]== puz[e])
                      tua46.AddUA6(a,b1,d1,e,f,g );
                   }
                }
            }
         }
      }// end transpose


[champagne]

I doubt the 17s exhaustive search would take only 10x resources compared to 16s without further algorithm improvements. I have some points in mind.

This is true. The code to generate the puzzles, takes ~8 times as long for 17's, but the number of puzzles that it produces, goes up by a factor ~150, and the fraction of time spent in the solver, becomes significant (but not unreasonable). I tried something along the lines of what I suggested at the bottom of this post, but without "feedback", and was able to get the time per grid down to ~22 seconds -vs- 2.8 for 16's.

Hi blue and Mladen,

Happy new year to you and all some hours ahead of time (for me).

I tested many ideas without any success so far.

I'll continue later in January, but 22 seconds seems not bad at all (unhappily).

Blue, I tried to go to your link, "this post", but the page is not any more available. If you still have the text, it would be great to have it posted again somewhere in that forum.

mladen, did you have any success with one of the points you had in mind