fast search of a 17 clues puzzle in a X+Y+27 valid puzzle

Programs which generate, solve, and analyze Sudoku puzzles

fast search of a 17 clues puzzle in a X+Y+27 valid puzzle

Postby champagne » Sat Jul 04, 2015 7:38 pm

Less than one millisecond to tell whether a X+Y+27 puzzle contains a 17 clues puzzle.
If you don't believe it, you can have a look to the next posts

This is a problem we faced trying to see whether we are missing 17 clues puzzles in the 49157 known 17 clues puzzles.

There is no easy way to solve that problem. One feasible partial answer to reduce the problem has been to scan all solutions in a X+Y+27 pattern.

The negative answer for X+Y<8 came quickly. The X+Y=8 case is already much more difficult.

The "best known process" is split in four steps :

a) find ED patterns X+Y+27. This is a relatively short step
b) Generate valid puzzles against "gangsters", the minlex form of band1 possible starts with a given set of 3 digits in each column
c) expand these puzzles to any valid permutation within the columns
d) find in each of these puzzles the valid 17.

we consider here exclusively the last step. To give an idea of the "size", in the 4+4+27 case, we have 13 745 722 puzzles at the end of the step c).

Available programs at that time could find the 17 with a run time leading to a very long d) step, so we tried ("Blue" and me), to use the specificity of that case to have a faster process.

We have been lucky and arrived to a step d) processing the 13 millions puzzles in about half an hour (9500 puzzles per second)

The process applied introduce nearly no new idea, except one, the search of UAs of size 2;3.
The resulting code is very simple and summarize in a nice way some published concepts.

The reader is supposed to have a good understanding of the following :

Unavoidable sets and search of puzzles of size "n" in a solution grid
The oldest reference I know is the gridchecker program reworked by mladen Dobrichev gridchecker

The second and key reference it the work done by the Gary McGuire's team to prove that there is no 16 clues puzzle. Gary McGuire's article

The key concepts described in these references are supposed known by the reader.
champagne
2017 Supporter
 
Posts: 5638
Joined: 02 August 2007
Location: France Brittany

Re: fast search of a 17 clues puzzle in a X+Y+27 valid puzzl

Postby champagne » Sat Jul 04, 2015 7:38 pm

The basic process.

We intend here to use more or less the same process as Gary McGuire.

In our case, X+Y=8, so 8 clues are given in bands 2 and 3, and we have to find a set of 9 clues in band 1 to come to a 17 clues puzzle.
If that puzzle is valid, we have a 17 clues solution.

Having 8 given, the first idea would be to generate all unavoidable set using the solution (the puzzle is valid, the solution is unique) and the print given by McGuire (UAs size 12 and less).

That list can be reduced erasing all puzzles hit by the 8 given. As the puzzle is valid, no UA can be found having no cell within the band 1.

And the corresponding UA's can be limited to the band 1 cells.This is not bad, but a much simpler idea appeared to be very efficient.

Most UA's if not all of them have somewhere in a box cells grouped in a mini line. Here, we can have a chance to have some UA's not yet hit by the known clues in bands 2;3 located in a mini row in band 1.

Such UAs are very easy to detect. To check if a mini row contains one or more of them, you just test a brute force on given clues omitting the corresponding 3 clues.

Testing that idea, we had the amazing surprise to see that the number of such UA' was high enough to kill in most cases any possibility to have a 17 clues puzzle.

In our file of 13 million puzzles, only 238 468 have still to be investigated after all mini rows have been tested for UAs size 2 or 3.

On top of it, if we use all tools described in the McGuire article, we could add UA' of bigger size, but nearly all branches are already quickly "'dead".

In our example, out of the 238 468 puzzles,

Code: Select all
only 1 141 589 branches end with 17 clues (others are killed before)
13 179 branches had to use more clues leading to 198 257 puzzles to test.


This means that the average number of additional call to brute force after UA'a size 2;3 have been searched is far below 1 per puzzle. No reason in that situation to look for more UA's.

Note : I did not test a search of UA's size 2;3 starting by the test of the full mini row, but the result should not be very different.

Mini row status versus UAs size 2;3 and minimum number of clues needed

Within a mini row, we can end with five different interesting status
1) no UA
2)1 UA size 2
3) 2 UA's size 2
4) 3 UA's size 2
5) no UA size 2, but one UA size 3.

mini-rows and disjoints UAs

Use of UAs hitting to find puzzles makes many references to "disjoints UAs" and "UA's of higher degree. (see mcGuire article)

by definition, each mini row is disjoint to any other mini row.
within a mini row,
Code: Select all
no Ua is disjoint to another one
in the case 4) (3 UA's size 2)  we need a minimum of 2 clues to hit the 3 UAs (in fact, exactly 2 clues)

the minimum number of clues needed to hit the UAs of the mini-row is one in cases 2;4;5 and 2 in the case 3.

Summing the needed in each mini row gives the total minimum of clues needed.

If we have 8 clues in bands 2;3 (X+Y=8), the puzzle contains no valid 17 clues if the total minimum needed is >= 10 (10+8>17)

The amazing fact is that this happens in most of the cases.
Last edited by champagne on Sat Jul 04, 2015 7:50 pm, edited 1 time in total.
champagne
2017 Supporter
 
Posts: 5638
Joined: 02 August 2007
Location: France Brittany

Re: fast search of a 17 clues puzzle in a X+Y+27 valid puzzl

Postby champagne » Sat Jul 04, 2015 7:39 pm

Exploring and sorting UAs size 2;3

All the coding shown here uses the infrastructure described recently in the brute force thread brute_force

The code is very simple. Apart from the calls to the brute force, the main specificity is the use of an integer to store different things.
Code: Select all
typedef union __declspec(intrin_type) _CRT_ALIGN(4) GINT_t {
    unsigned __int8    u8[4];
    unsigned __int16   u16[2];
    unsigned __int32   u32;
} GINT;


in that code, a given (digit + cell) is stored as 2 bytes in an integer.


the code will be described using 4+4+27 valid puzzles containing one or more 17 clues puzzle.
we just describe here the code included in a loop processing 81text lines where non given are '.'


Primary filter; counting the minimum number of clues needed
Code: Select all
GINT tgint[81],tgminir[9],tgb1[30];
int ntgint=0,ntgb1=0,ntgbs=0;
//find and  count the clues in band 2 / 3
for(int i=27;i<81;i++)    if(zpuz[i]>'0' && zpuz[i]<= '9')
   tgint[ntgint++].u32=i+((zpuz[i]-'1')<<8);
int nr=ntgint,maxforced=17-nr, cumuah=0;
//========= try all pairs in minilines band1 as UAs
int permmr[9][3][2]={
{{0,1},{0,2},{1,2}},   {{3,4},{3,5},{4,5}},   {{6,7},{6,8},{7,8}},
{{9,10},{9,11},{10,11}},   {{12,13},{12,14},{13,14}},   {{15,16},{15,17},{16,17}},
{{18,19},{18,20},{19,20}},   {{21,22},{21,23},{22,23}},   {{24,25},{24,26},{25,26}}};
for(int imr=0;imr<9;imr++) {// 9 minrows to search
   tgminir[imr].u32=imr;
   int px=0;
   for(int p=0;p<3;p++){
      int* pp=permmr[imr][p];
      ntgint=nr; // load after bands2 3
      for(int k=0;k<27;k++) if((k-pp[0]) && (k-pp[1]))
         tgint[ntgint++].u32=k+((zpuz[k]-'1')<<8);
      if(zhou[0].StatusValid(tgint,ntgint,4)-1) {// UA if not unique
         tgb1[ntgb1++].u32=imr+(p<<8);// just store it
         px|=(1<<p);
      }
   }
   if(px){// some UA2 have been seen
      cumuah++;
      int nx=BitCount[px],w=(nx<2)? 1:2;
      if(nx==3){ stored in the miniline status
         cumuah++;
         tgminir[imr].u8[1]=1;
      } 
   }
   else{// see if  triplet is UA
      ntgint=nr; // load after bands2 3
      for(int k=0;k<27;k++) if((k/3) - imr)
         tgint[ntgint++].u32=k+((zpuz[k]-'1')<<8);
      if(zhou[0].StatusValid(tgint,ntgint,4)-1) {// UA if not unique
         tgb1[ntgb1++].u32=imr+(3<<8);// just store it 
         px |=8;
         cumuah++;
      }
   }
   tgminir[imr].u8[2]=BitCount[px];// store final UAs count of the minirow
}
if(cumuah>maxforced)continue; // can't be a 17 


here the 32 bits int (GINT) is used to store

tgint the list of given sent to the brute force (cell + digit)
tgminir the mini-row status (mini_row+{1 if 3 pairs} + UAs count}
tgb1 one entry per UA found (mini_row + {pairnumber 0-2 or 3 if triplet} )

Only the first table is needed for that filter. The 2 other tables are for the next steps.

As said earlier, in a huge majority of the cases, the search is cancelled with

if(cumuah>maxforced)continue; // can't be a 17

At that point, a minimum of 3x9 calls to the brute force have been done, but with 25+8= 33 given, the brute force goes very fast.

The brute force call is very close to standard knowing that the puzzle has 1 or more solutions.
The call uses the InitSudoku() variant using a list of given. The return code is 0 if the puzzle is not valid(never here); 1 is the puzzle has one solution; 2 if the puzzle has more than one solution.

Next step is to process puzzles passing the first filter.
Last edited by champagne on Sat Jul 04, 2015 7:55 pm, edited 1 time in total.
champagne
2017 Supporter
 
Posts: 5638
Joined: 02 August 2007
Location: France Brittany

Re: fast search of a 17 clues puzzle in a X+Y+27 valid puzzl

Postby champagne » Sat Jul 04, 2015 7:39 pm

Preparing the puzzle expansion

Using as sample the puzzles containing some 17 clues, we don't have the case where a mini row has no UA of size 2, but a UA of size 3. As this is not a key point, I did not look for such a puzzle.

The first 4+4+27 containing a 17 clues is the following.

Code: Select all
 9538214766429738511876543293.6...........5.4...........2.....9....3.8............


the search for UAs2 produces the following set

Code: Select all
minir=0 perm0 9r1c1 5r1c2
minir=0 perm2 5r1c2 3r1c3
minir=1 perm0 8r1c4 2r1c5
minir=1 perm2 2r1c5 1r1c6
minir=2 perm1 4r1c7 6r1c9
minir=2 perm2 7r1c8 6r1c9
minir=3 perm0 6r2c1 4r2c2
minir=5 perm0 6r3c4 4r3c6
minir=5 perm1 3r3c7 2r3c8
minir=5 perm2 3r3c7 9r3c9
minir=7 perm0 6r3c4 5r3c5
minir=7 perm1 6r3c4 4r3c6
minir=8 perm0 3r3c7 2r3c8
minir=8 perm1 3r3c7 9r3c9


to hit all UAs we need

Code: Select all
1 or 2 clues in mini-rows 0;1;2;7;8
1 clue in mini-row 3
2 clues in mini-row 5


the minimum number of clues is 8, missing by 2 the first filter (8+8=16 < 18)

Any solution hitting more than 2 mini-rows in the group 0;1;2;7;8 with 2 clues will pass the filter.

This is another way to express what is described as "early stop in a branch using UAs of higher degree in the McGuire article.

Here Higher degree UAs can have a trivial expression. If we order the UAs mini row per mini row, hitting top down the mini rows; the Highest remaining degree is the sum of minimum clues in the untouched mini-rows.

We should reach the best efficiency sorting the mini-rows with at the top all mini rows having to UAs size 2

This is done in the program building the table tuab1. Here is the print of the corresponding table.


Code: Select all
tuab1 i=0  uahsize=7 nval=2 9r1c1 5r1c2
tuab1 i=1  uahsize=7 nval=2 5r1c2 3r1c3
tuab1 i=2  uahsize=6 nval=2 8r1c4 2r1c5
tuab1 i=3  uahsize=6 nval=2 2r1c5 1r1c6
tuab1 i=4  uahsize=5 nval=2 4r1c7 6r1c9
tuab1 i=5  uahsize=5 nval=2 7r1c8 6r1c9
tuab1 i=6  uahsize=4 nval=2 6r3c4 5r3c5
tuab1 i=7  uahsize=4 nval=2 6r3c4 4r3c6
tuab1 i=8  uahsize=3 nval=2 3r3c7 2r3c8
tuab1 i=9  uahsize=3 nval=2 3r3c7 9r3c9
tuab1 i=10  uahsize=2 nval=2 6r2c1 4r2c2
tuab1 i=11  uahsize=0 nval=2 8r2c7 5r2c8
tuab1 i=12  uahsize=0 nval=2 8r2c7 1r2c9
tuab1 i=13  uahsize=0 nval=2 5r2c8 1r2c9


Now, the mini-rows order is 0;1;2;7;8;3;5 in any of the groups {0;1;2;7;8}; {3;5}, the sequence can be changed without any effect on the result. Reversely, changing the order of the cells within a UA would affect the performance (optimizing the "dead" effect).

In each entry of the table, we have (uahsize) the sum of the minimum number of clues in the other mini-rows.

One could object that this is not optimal, and this is true, but it is simple and efficient enough in the expansion process.

In the hitting sequence, if at any moment the sum of hits done + pending minimum High degree UA pass 17, the branch can be stopped.
Last edited by champagne on Sat Jul 04, 2015 8:02 pm, edited 1 time in total.
champagne
2017 Supporter
 
Posts: 5638
Joined: 02 August 2007
Location: France Brittany

Re: fast search of a 17 clues puzzle in a X+Y+27 valid puzzl

Postby champagne » Sat Jul 04, 2015 7:39 pm

Dead cells

In the code, the redundancy control through "dead cells" as explained in McGary's article is used.

Dead cells are skipped in the UA's expansion process
Dead cells are excluded from the remaining cells when no more UA size 2;3 is available.

what to do when the UA size 2;3 file is exhausted.

The strategy here is somehow depending on the frequency of that event.
In the McGuire process, when the file of UAs size 1-12 is exhausted, additional clues are searched in the remaining cells.

Here, we could first look in UAs size 1-12 having in the " band 1" a cells set not belonging to a mini row.
The price to pay to collects such UAs is far from nil. the experience of the 4+4+27 field does not push in that direction.

In our first example, only six branches are not closed with the last UA. As the minimum number of hits is 8, we start with 8+8=16 known clues and this can happen only if each mini-row having 1 or 2 clues has the hit corresponding to one clue, that is

5r1c2; 2r1c5;6r1c9;6r3c4;3r3c7.
we have then one clue out of {6r2c1;4r2c2}
and 2 clues out of {8r2c7;5r2c8;1r2c9}
giving the 6 cases


Code: Select all
.5..2...66.....85....6..3..3.6...........5.4...........2.....9....3.8
11.11.1.11.....11....1..1..

.5..2...66.....8.1...6..3..3.6...........5.4...........2.....9....3.8
11.11.1.11.....111...1..1..

.5..2...66......51...6..3..3.6...........5.4...........2.....9....3.8
11.11.1.11.....111...1..1..

.5..2...6.4....85....6..3..3.6...........5.4...........2.....9....3.8
11.11.1.111....11....1..1..

.5..2...6.4....8.1...6..3..3.6...........5.4...........2.....9....3.8
11.11.1.111....111...1..1..

.5..2...6.4.....51...6..3..3.6...........5.4...........2.....9....3.8
11.11.1.111....111...1..1.
.

here the second line shows the dead clues when we enter the complementary search.
Although the count of assigned clues is 8, the dead count is between 11 and 13. An optimized process would likely give in that case 13 dead in each branch.

As a consequence, the complementary search has to take one clue out of 14-16 (27- 13/11)to test for a valid puzzle

No chance in that position to have a better process looking for more UAs.

With 2 missing clues, we can expect about 14*13/2 cases to test, still far from the cost of the search of UAs.

Here our worst case (see below) is 2 missing clues. My forecast would be that the current process remains better even with 4-5 missing clues.

Code: Select all
9576243816839514274217389655........2...7..........6....8..6........9...........2

tuab1 i=0  uahsize=6 nval=2 9r1c1 7r1c3
tuab1 i=1  uahsize=6 nval=2 5r1c2 7r1c3
tuab1 i=2  uahsize=5 nval=2 6r1c4 2r1c5
tuab1 i=3  uahsize=5 nval=2 2r1c5 4r1c6
tuab1 i=4  uahsize=4 nval=2 6r2c1 8r2c2
tuab1 i=5  uahsize=4 nval=2 6r2c1 3r2c3
tuab1 i=6  uahsize=3 nval=2 9r2c4 5r2c5
tuab1 i=7  uahsize=3 nval=2 5r2c5 1r2c6
tuab1 i=8  uahsize=2 nval=2 4r2c7 2r2c8
tuab1 i=9  uahsize=2 nval=2 4r2c7 7r2c9
tuab1 i=10  uahsize=1 nval=2 9r3c7 5r3c9
tuab1 i=11  uahsize=1 nval=2 6r3c8 5r3c9
tuab1 i=12  uahsize=0 nval=2 2r3c2 1r3c3


here most entries with a lack of UAs are with one of the mini-rows {0;1;3;4;5;8} having 2 clues, but after the sequence
7r1r1c3;2r1c5;6r2c1;5r2c5;4r2c7;5r3c9
any of {2r3c2;1r3c3} ends with 8+7=15clues
2 clues must be added. With the non optimal sequence above, we have respectively 12/13 dead cells giving less than 100 pairs to test.
Last edited by champagne on Sat Jul 04, 2015 8:10 pm, edited 1 time in total.
champagne
2017 Supporter
 
Posts: 5638
Joined: 02 August 2007
Location: France Brittany

Re: fast search of a 17 clues puzzle in a X+Y+27 valid puzzl

Postby champagne » Sat Jul 04, 2015 7:40 pm

the code following the filter is the following

Hidden Text: Show
Code: Select all
zhou[0].SetPat(zpuz,zsol,zout);// we need the solution for expansion
if(!( zhou[1].CheckValidityQuick(zpuz,0)==1)) // build the full solution
   return;// could have been checked earlier but we need the solution here
zhou[0].glb.zsol=0;// protect the solution, later we just need "valid" or not
//----------------> sorting UAs and building UABX ready to expand
struct UAB1{
   GINT tval[3];
   int nval,bf,uahsize;
   void Build(GINT & gg,char * zsol,int permmr[9][3][2],int cumuah){// gg imr+perm
      uahsize=cumuah;
      int imr=gg.u8[0],p=gg.u8[1];
      if(p<3){// ua size 2
         int* pp=permmr[imr][p];
         bf=(1<<pp[0])+(1<<pp[1]);
         nval=2;
         tval[0].u32=pp[0]+((zsol[pp[0]]-'1')<<8);
         tval[1].u32=pp[1]+((zsol[pp[1]]-'1')<<8);
      }
      else { //UA size 3 full miniline
         int p1=3*imr,p2=p1+1,p3=p2+1;
         bf=(1<<p1)+(1<<p2)+(1<<p3);
         nval=3;
         tval[0].u32=p1+((zsol[p1]-'1')<<8);
         tval[1].u32=p2+((zsol[p2]-'1')<<8);
         tval[2].u32=p3+((zsol[p3]-'1')<<8);
      }
   }
}tuab1[30];

int ntuab1=0;
for(int imr=0;imr<9;imr++) if(tgminir[imr].u8[2]==2){// load first 2UAs in the miniline
   cumuah-=(1+tgminir[imr].u8[1]); // min UAHigh degree remainning size
   for(int i=0;i<ntgb1;i++)   if(tgb1[i].u8[0]==imr)
      tuab1[ntuab1++].Build(tgb1[i],zsol,permmr,cumuah);
}
for(int imr=0;imr<9;imr++) {
   int cc=tgminir[imr].u8[2];
   if(cc==1 || cc==3){// then others
      cumuah-=(1+tgminir[imr].u8[1]); // min UAHigh degree remainning size
      for(int i=0;i<ntgb1;i++)   if(tgb1[i].u8[0]==imr)
         tuab1[ntuab1++].Build(tgb1[i],zsol,permmr,cumuah);
   }
}

struct SPOTS{
   int cell,cell_old,cumdead,ival,iua ; //cumdead is a 27 bits field
   UAB1 * myua;
   inline int NextVal(){return (++ival>=myua->nval);}
   inline GINT GetVal(){ return myua->tval[ival];}
}spots[15],*s ,*sp;

int ispot=0, cell,limspot=17-nr-1;
GINT * tgsolplus=&tgint[nr],wgint;
s=spots;
s->cumdead=s->iua=0;
s->myua=tuab1;
s->ival=-1;
goto nextval;
nextspot:
if(ispot == limspot){// check if it is a valid 17
   if(zhou[0].StatusValid(tgint,17,4)-1) goto nextval;
   cout <<CoutGintPuzzle(tgint,17,zout)<< " valid 17"<<endl;// print the valid 17
   goto nextval;
}
ispot++;  sp=s++;// find next UA
int iua=sp->iua;
s->iua=0;
while (++iua<ntuab1){// new minirow or untouched UA in the minirow
   if(tuab1[iua].bf & (1<<sp->cell))continue; // only reason to skip
   s->iua=iua;
   break;
}
if(s->iua){// we have a "next UA" in the table
   if(ispot+tuab1[s->iua].uahsize >limspot)goto backtrack; // passing 17
   s->ival=-1;
   s->myua=&tuab1[s->iua];
   s->cumdead=sp->cumdead;
   goto nextval;
}
//no more UAs in the table try all "not dead" remaining cells in band1
{      //Build the table of undead
   int ispot2=0,n2=0,cd=sp->cumdead,ispot0=nr+ispot-1,lim2=15-ispot0;
   int tispot2[10]={-1}; // current index for the corresponding value of ispot2
   GINT t2[26];
   for(int i=0;i<27;i++){
      if(cd & (1<<i)) continue;
      t2[n2++].u32=i+((zsol[i]-'1')<<8);
   }
  nextval2:{
   int ind=++tispot2[ispot2];
   if(ind>=n2){// bactrack2
      if(ispot2){ispot2--;goto nextval2;}
      goto backtrack;
   }
   if(ispot2==lim2){// test that 17 clues case
      for(int j=0;j<=ispot2;j++)
         tgint[ispot0+j]=t2[tispot2[j]];
      if(zhou[0].StatusValid(tgint,17,4)-1) goto nextval2;
      cout <<CoutGintPuzzle(tgint,17,zout)<< "valid 17"<<endl;// print valid 17
      goto nextval2;
   }
   else{
      ispot2++;
      tispot2[ispot2]=ind;
      goto nextval2;
   }
   cerr <<"invalid status in step2"<<endl; // can not be this is a bug
   return;
  }
}
goto backtrack; // should never be used
nextval:
{   if(s->NextVal()) goto backtrack;
   ispot=s-spots; // be sure to have the correct value
   tgsolplus[ispot]=wgint=s->GetVal();
   s->cell=cell=wgint.u8[0];
   if(s->cumdead & (1<<cell) ) goto nextval;
   s->cumdead |= (1<<cell);
   goto nextspot;
}
backtrack:
   if(--ispot>=0) { s--; goto nextval;}


I see nothing difficult in that, so comments will come on request
champagne
2017 Supporter
 
Posts: 5638
Joined: 02 August 2007
Location: France Brittany

Re: fast search of a 17 clues puzzle in a X+Y+27 valid puzzl

Postby champagne » Sun Jul 05, 2015 8:46 am

a side remark on that process.

The main finding, the search of UAs size 2 was done late 2014.
I spent much time to see if similar ideas could be developed in the search of 17 clues puzzles directly in the catalog of solutions. I failed.
So far, the layout of McGuire remains the best. Marginal improvements are possible, but no breakthrough.

That process could offer 2 or 3 new ideas. The simplest would be to change the priority in the UA's processing.

But what is very simple (sorting the mini rows and reordering the cells to optimize the "dead cell" effect) is more complex in the general case.

If my brain is still in good form, I'll restart the thinking late this year.
champagne
2017 Supporter
 
Posts: 5638
Joined: 02 August 2007
Location: France Brittany

Re: fast search of a 17 clues puzzle in a X+Y+27 valid puzzl

Postby dobrichev » Sun Jul 05, 2015 9:49 am

Hi champagne, I have 2 questions.
1) What UA of size 2 and 3 are?
2) What exactly are the input and output of the explained process?
dobrichev
2016 Supporter
 
Posts: 1311
Joined: 24 May 2010

Re: fast search of a 17 clues puzzle in a X+Y+27 valid puzzl

Postby champagne » Sun Jul 05, 2015 10:10 am

dobrichev wrote:Hi champagne, I have 2 questions.
1) What UA of size 2 and 3 are?
2) What exactly are the input and output of the explained process?


Hi Mladen,

lets start with point 2)

input is a valid X+Y+27 puzzle. Normally, it has been produced expanding and ED X+Y+27 pattern, but it can be any valid X+Y+27 puzzle.
the band1 is filled, band2 and 3 contain the X and Y given.
output is made of 17 clue puzzles found in the input
i

Now point 1)

when you consider all UAs (in theory).
Most of them are hit by the X;Y given. Just consider other UAs
These UAs can not be hit outside of the band 1, all missing given must be in band 1

All these UAs have part of the cells in band 1 (if not, the puzzle would not be valid). We can reduce them to the cells in band 1.

UAs of size 2 are such UAs having only 2 cells in band 1. As noticed blue, such cells must be in a mini row.

In that process, UAs of size 3 are such UAs touching the band 1 with 3 cells of the same mini-row. I did not check it, but I think that it is the only possible pattern for a UA of size 3. In fact, here we don't have to answer to the question.
champagne
2017 Supporter
 
Posts: 5638
Joined: 02 August 2007
Location: France Brittany

Re: fast search of a 17 clues puzzle in a X+Y+27 valid puzzl

Postby dobrichev » Sun Jul 05, 2015 12:09 pm

Thank you.

So, if you take a valid 17-given puzzle and apply your process, it will be equivalent of 6 steps, where in each step you are clearing the givens from a particular stack/band, and generating all possible 17-given puzzles having the same uncleared givens. You are not fixing the solution grid.

UA set is property of the solution grid. If you work with gangsters of 44, then you use some generalization of UA set. That confused me. BTW gridchecker has pretty fast code for U4 and U6 which you can simplify and reuse for your case with U2 and U3 respectively.

You found that for the evaluated cases hitting the inter-band short UA dominates hitting the intra-band UA, which isn't surprise. Congratulations for making it working!

With currently implemented optimizations, do you have estimation how long the processing of all known 17-givens will take?

Do you manage to process firstly the known 17s and later the rest of the valid 27+X puzzles?
dobrichev
2016 Supporter
 
Posts: 1311
Joined: 24 May 2010

Re: fast search of a 17 clues puzzle in a X+Y+27 valid puzzl

Postby champagne » Sun Jul 05, 2015 2:14 pm

dobrichev wrote:Thank you.

So, if you take a valid 17-given puzzle and apply your process, it will be equivalent of 6 steps, where in each step you are clearing the givens from a particular stack/band, and generating all possible 17-given puzzles having the same uncleared givens. You are not fixing the solution grid.


I think this is not correct.

We start from a puzzle having one solution.
Here, a UA2 is defined as a puzzle loosing that property if none of 2 cells is given. So the solution grid is unique.


BTW gridchecker has pretty fast code for U4 and U6 which you can simplify and reuse for your case with U2 and U3 respectively.


Yes, but in that process, i suspect that many UA2 are reductions of much bigger one (even exceeding the size 12, the limit of the prints prepared by McGuire).


With currently implemented optimizations, do you have estimation how long the processing of all known 17-givens will take?


With the above remarks, I have some difficulties to answer to that question. I don't see clearly what process you have in mind.
What is for sure is that finding the 4+4+27 has been more than 5 year*core of generation.
champagne
2017 Supporter
 
Posts: 5638
Joined: 02 August 2007
Location: France Brittany

Re: fast search of a 17 clues puzzle in a X+Y+27 valid puzzl

Postby champagne » Mon Jul 06, 2015 3:58 am

dobrichev wrote:With currently implemented optimizations, do you have estimation how long the processing of all known 17-givens will take?
Do you manage to process firstly the known 17s and later the rest of the valid 27+X puzzles?


I thought a little more about that.

I see one possibility to apply that process with success in competition with the McGary's one.

Take any solution grid.

search all band2+band3 UAs
build all "minimal" 27+X
apply that process to each of them.

Looking for a minimal 27+X, it could be that one or 2 more clues in bands2-3 have to be added. With band1 filled, there is not so many possibilities.

If we need more clues at the end
a) we can use standard UAs specific to band1 (collected in the first phase)
b) the additional clues can be anywhere in the 81 cells

It will be necessary to draft the code to evaluate the process
In that case (2 bands), a 64 bits platform would be a plus. AFAIK, the free Microsoft visual C++ is limited to the generation of the 32 bits code.
Looking for new 17clues, we can immediately skip all cases with less than 9 clues in bands23 (no new 17 for 8 and less)
champagne
2017 Supporter
 
Posts: 5638
Joined: 02 August 2007
Location: France Brittany


Return to Software