SEclone  BUGs

The search for BUGs is the last step in this forst part of the solving techniques. Next one will use the tagging.

 

My solver had a very limited handling of BUGs, so that code is quite new.

 

I tried here a comprehensive attack of the problem, looking for the simplest process, but it could be that some coherency checking are missing.

 

Using a valid sample file can not detect defaults.

 

As far as I can see, the following process finds all bugs of the sample file.

 

 

BUG’s  process

 

If we go back to the creation of the table of dual cells, One can see that some preparation is done for the Bug processing;

 

void TPAIRES::CreerTable()

{ip=0; ntplus=aigpmax=0; zplus.Init();

 for(int i=0;i<81;i++)

   {int n=T81t[i].v.ncand;

       if(n==2)    {zp[ip].Charge(T81t[i]);  zpt[ip]=zp[ip++];}

    else if(n>2)

     {if(ntplus<8) {tplus[ntplus]=i;//direct access to first plus cells

                        ntplus++;   zplus.Set(i);}

      if(n>aigpmax) aigpmax=n;}

  }

……..

 

A second table of cell having more than 2 candidates id prepared, limited to 10 cells, and the highest number of candidates is stored.

 

The process looks first for bugs type 1 and 2, and then for Bugs type 3 and 4, where extra cells are located in a row; column or box.

 

For the last group, I tested a process where, if  extra cells are in a row or in a column, location of extra digits is made in the opposite direction.

 

If the extra cells are located in a box, and not in a row or column, the process is slightly more complex.

 

The process is limited to 3 cells (I don’t know if SE works with more)

In a first step, cells alone in a row or in column are reduced to 2 digits in that row/col

In a second step, if any, the residual cell is reduced to 2 digits inside the box.

 

It works with the sample file, but it needs more validation.

 

The code is spread in 3 files 

 

#include "c\_04d_  paires_bug.cpp" 

#include "c\_04d_  paires_bug3.cpp" 

#include "c\_04d_  paires_bug4.cpp" 

 

 

//==============================

int TPAIRES::BUG()

{E$.Enl("debut recherche bug");

 if(ntplus>6|| aigpmax>4) return 0;  // maxi a vérifier 6 cases et 4 candidats

// set the parity of digits for bivalue cells in all elements

for(int i=0;i<27;i++) el_par_ch[i].f=0;

for(int i=0;i<ip;i++)

        {P81 p=T81t[zp[i].i8]; 

         el_par_ch[p.f->el]^=p.v.cand;

         el_par_ch[p.f->pl+9]^=p.v.cand;

         el_par_ch[p.f->eb+18]^=p.v.cand;

        }

if(ntplus==1) return Bug1();

if(Bug2()) return 1; // priority to bug 2

 

for(int i=0;i<27;i++)  if( zplus.EstDans(divf.elz81[i]))      

{ntpa=nwp=0;// collect data in that row/col/box

 candp_or.f=candnp_or.f=candp_xor.f=candnp_xor.f=nwp=0;

 for(int j=0;j<9;j++) 

  {int i8=divf.el81[i][j]; P81 p=T81t[i8];

   if(zplus.On(i8)) // wplus has the same order as tplus

        {candnp_or|=p.v.cand;candnp_xor ^=p.v.cand;wplus[nwp++]=p.v.cand;}

   else if(p.v.ncand==2)

         {candp_or|=p.v.cand;candp_xor ^=p.v.cand;tpa[ntpa++]=i8;}

  }

 if (Bug3(i)) return 1;//bug3 and bug4

 continue;//only one row/col/box

}

// other patterns to discover

return 0;}

//===========================

int TPAIRES::Bug1()

{if(aigpmax>3) return 0;

 int i8=zplus.First();

 P81 p=T81t[i8]; CB9CH w=el_par_ch[p.f->el] ^ p.v.cand,w2=w&p.v.cand;

 if(w2.QC()-1) return 0; // a false bug

 if(w.QC()-1) return 0; //must be one as well, but surely is

 T81t[i8].Keep(w2);

 BugMess(" 1");

return 1;}

 

//================================ cells in different objects or one digit

int TPAIRES::Bug2()  // any number of cells, but 6 seems very high

{if(ntplus>6 || aigpmax>3) return 0; 

 CB9CH possible;possible.f=0x1ff;

 ZINFL zw; zw.InitUn();

 for(int i=0;i<ntplus;i++) // analyse all cells

   { P81 p1=T81t[tplus[i]];zw&=p1.f->z;

     CB9CH w1=p1.v.cand-el_par_ch[p1.f->el];

        if(!w1.f) // if nothing comes in row, try the column

          w1=p1.v.cand-el_par_ch[p1.f->pl+9] ;

     possible &= w1;  }

 if(zw.Nul()) return 0;// must have a comon control on some cells

 if(possible.QC()-1) return 0; // must be one common digit

// ok for bug type 2 clear the commonly controled  cells

int ir=0,ch=possible.First();;

for(int i=0;i<81;i++)if(zw.On(i)) ir+=T81t[i].Change(ch);

if(ir){BugMess("2 same digit");o$.SetDif(57);}

return ir;}

//===========================================

void TPAIRES::BugMess(char * lib)

{E$.E("Bug type ");E$.Enl(lib);

T81C->Candidats();}

 

 

//===================  all cells in the same  element(s )(can be type 2)

int TPAIRES::Bug_lock(int el)

{E$.Enl("recherche  bug_lock");

CB9CH clock=candnp_or - candp_or;  // locked candidate

E$.E(" clock=");E$.Enl(clock.String());

 if(!clock.f) return 0;

 

P81 p1=T81t[tplus[0]],p2=T81t[tplus[1]];

int el1=p1.f->el,el2=p2.f->el; // use the row in priority

if(el<9) {el1=p1.f->pl+9; el2=p2.f->pl+9;}  // and col if row is "el"

 CB9CH wc1=(p1.v.cand & el_par_ch[el1]) ,wce1=p1.v.cand-wc1,

          wc2=(p2.v.cand & el_par_ch[el2]) ,wce2=p2.v.cand-wc2 ;

E$.E(p1.f->pt); E$.E(" el=");E$.E(el1+1);

E$.E(" wc1=");E$.Enl(wc1.String());

E$.E(p2.f->pt); E$.E(" el=");E$.E(el2+1);

E$.E(" wc2=");E$.Enl(wc2.String());

 

 

 if( ( wc1.QC()-2)  ||

        ( wc2.QC()-2)  ) return 0;

 

 T81t[tplus[0]].Keep(wce1|clock);

 T81t[tplus[1]].Keep(wce2|clock);

 BugMess("3/4 a digit locked");

 o$.SetDif(57);return 1;

}

 

//============================================

 int TPAIRES::Bug3_4_Nacked(int el)

{E$.Enl("recherche  bug3_4 Nacked");

 

USHORT ctl=ntplus,aig=1; 

P81 *pp;  USHORT elx; CB9CH wcx, welim,annul;

 

for(int i=0;i<ntplus;i++)

{pp = & T81t[tplus[i]];

 elx = pp->f->el;    if(el<9)  elx=pp->f->pl+9;

 wcx = pp->v.cand & el_par_ch[elx]  ;

 annul = pp->v.cand -  wcx;

 //E$.E(t81f[tplus[i]].pt); E$.E(" el=");E$.E(elx+1);

 //E$.E(" wc=");E$.Enl(wcx.String());

 if( (wcx.QC() - 2) ) return 0;

 welim |= annul;

}     

 

return Nacked_Go(welim);

}

 

 

 

//===================  all cells in the same  element(s )(can be type 2)

int TPAIRES::Bug3(int el)

{if((ntplus==2) && Bug_lock(el)) return 1;

 if(el<18)        return  Bug3_4_Nacked(el) ;

E$.Enl("recherche en boite");

 

      // we have now a box and not 2 cells with a digit locked

 

if(ntplus>3) return 0; // would not work with that process

      // look first row and col with only one cell

CB9CH wrow,wcol;  // on cherche parite de row/col

P81 *pp; 

USHORT elx,phx[5];

for(int i=0;i<ntplus;i++) // first look for parity

    {pp = & T81t[tplus[i]]; phx[i]=0;

     CB9CH wr(pp->f->el), wc(pp->f->pl);

     wrow ^= wr; wcol ^= wc; // change parity

     }

 CB9CH wcx, welim,annul,wpar;

 

E$.Enl("recherche en boite phase 1");

 

for(int i=0;i<ntplus;i++)

{pp = & T81t[tplus[i]];

if(wrow.On(pp->f->el) ) elx = pp->f->el;   

 else if(wcol.On(pp->f->pl))  elx=pp->f->pl+9;

 else continue;// not processed the

 phx[i]=1;

 wcx = pp->v.cand & el_par_ch[elx]  ;

 annul = pp->v.cand -  wcx;

 wpar^=wcx;  // to adjust parity for the last if needed

 if( (wcx.QC() - 2) ) return 0;

 welim |= annul;

}     

E$.E("recherche en boite phase 2");

E$.E(" wpar");E$.Enl(wpar.String());

 

 wpar ^=  el_par_ch[el]  ;  // adjust parity in the box

 

// finish the task if one has no row/col free

for(int i=0;i<ntplus;i++)

{if(phx[i] )continue;// done

 pp = & T81t[tplus[i]];

  wcx = pp->v.cand & wpar  ;

 annul = pp->v.cand -  wcx;

 E$.E(t81f[tplus[i]].pt); E$.Esp();

 E$.E(" wpar");E$.E(wpar.String());

 E$.E(" wcx");E$.Enl(wcx.String());

  if( (wcx.QC() - 2) ) return 0;

 welim |= annul;

}     

 

return Nacked_Go(welim);

}

 

 

int TPAIRES::Nacked_Go(CB9CH welim)

{            //we look now for  "naked locked sets"

E$.E("recherche  bug3_4 Nacked ok to go welim= "); E$.Enl(welim.String());

int nelim=welim.QC(); // look for naked in increasing order

if(nelim <2  || nelim>5) return 0;

if(nelim<3) //then search for naked 2

 for(int i=0;i<ntpa;i++) if(T81t[tpa[i]].v.cand.f==welim.f)// we found it

 {int ir=0; for(int j=0;j<ntpa;j++) if(j-i)

                ir+=T81t[tpa[j]].Change(welim);

  if(ir) {BugMess("type 3/4 naked pair");o$.SetDif(58); return 1;}

 }

                 // look for triplet

for(int i1=0;i1<ntpa-1;i1++)for(int i2=i1+1;i2<ntpa;i2++)

  {CB9CH ww=welim | T81t[tpa[i1]].v.cand | T81t[tpa[i2]].v.cand;

   if(ww.QC()-3) continue; // if not we got it

   int ir=0; for(int j=0;j<ntpa;j++) if((j-i1)&&(j-i2))

                ir+=T81t[tpa[j]].Change(ww);

   if(ir) {BugMess("type 3/4 naked triplet"); o$.SetDif(59); return 1;}

  }// end triplet

                  // look for quad

for(int i1=0;i1<ntpa-2;i1++)for(int i2=i1+1;i2<ntpa-1;i2++)for(int i3=i2+1;i3<ntpa;i3++)

  {CB9CH ww=welim | T81t[tpa[i1]].v.cand | T81t[tpa[i2]].v.cand| T81t[tpa[i3]].v.cand;

   if(ww.QC()-4) continue; // if not we got it

   int ir=0; for(int j=0;j<ntpa;j++) if((j-i1)&&(j-i2)&&(j-i3))

                ir+=T81t[tpa[j]].Change(ww);

   if(ir) {BugMess("type 3/4 naked quad"); o$.SetDif(60);return 1;}

  }// end quad

                    // look for (5)

for(int i1=0;i1<ntpa-3;i1++)   for(int i2=i1+1;i2<ntpa-2;i2++)

for(int i3=i2+1;i3<ntpa-1;i3++)for(int i4=i3+1;i4<ntpa;i4++)

  {CB9CH ww=welim | T81t[tpa[i1]].v.cand | T81t[tpa[i2]].v.cand

                  | T81t[tpa[i3]].v.cand | T81t[tpa[i4]].v.cand ;

   if(ww.QC()-5) continue; // if not we got it

   int ir=0; for(int j=0;j<ntpa;j++) if((j-i1)&&(j-i2)&&(j-i3)&&(j-i4))

                ir+=T81t[tpa[j]].Change(ww);

   if(ir) {BugMess("type 3/4 naked (5)");o$.SetDif(61); return 1;}

  }// end (5)

return 0;}