SEclone basic classes for tagging

 

Tagging is requiring new classes. The main ones are the following:

 

CB1024    the last and the  biggest bit field

 

      2 “class” created specifically for SE clone

 

PATH       describing a path or building a path.

CHAIN     to manage the length issue, storing parameters to act in due time

 

     The basic classes of the tagging process

 

TZPTLN  to store candidates and qualify them toward the tagging process

TZLN       to store and process strong links, also to search chains within a layer

TZF          to store primary weak links and data required to trace back a chain

TDB         the table of “bit field “collecting all weak links in “implication form”

TCHOIX to store all sets to check for set eliminations or derived weak links.

 

        And 2 more also part of the tagging process

 

IPT          a table giving a direct index to locate a candidate in TZPTLN

ZGS        a table storing used pattern of cells in a 81 bits form

 

The infrastructure to trace back AIC’s nets and nested chains that we’ll define later.

 

 

CB1024  bit field to show implications 

 

 

That bit field is slightly different from others

 

It shows for one tag the implications to others  “a” -> “b”

 

The number of tags can be very small (some tens at the end of a game) or very big (about 1000 at the last level in my solver). So the design is done to host the maximum number of tags and a “max size” indicator is set to reduce the processing to the active part of the bit field.

 

Here, the maximum size will be about 2 times the number of candidates. It has been set to

 20 integers = 640 bits. (maximum number of tags  authorized = 318)

 

At the end of the tagging, the “process” dimension is reduced to the minimum.

 

Overloaded operators are the same as for other bit fields. A specific function “Inverse()” produces the set of associated tags.

 

//bitfield 2048 bits used in chains and within a layer

//in the solver, a bit represents normally a tag

//bivalues are using 2 consecutive bits  (low order bit 0,1; same value for other bits)

//for performance reason, the field is processed partially depending of the number of bit used

class CB1024

{UINT f[20];     // the bit field

 static int     io,jo,isize;

 void ij(int v) {io=v>>5;jo=v&31;};

 public:

 CB1024(){Init();}

 static void SetMax(){isize=20;}

 static void SetIsize(int icol){isize=(icol+31)>>5; }

 void Init();  void InitUn();

 int Isch(int v)     {ij(v);return (f[io]&(1<<jo));}

 inline int On(int v)     {ij(v);return (f[io]&(1<<jo));}

 inline int Off(int v)     {ij(v);return ((f[io]&(1<<jo))==0);}

 inline void Set(int v)      {ij(v);f[io]|=(1<<jo);}

 inline void Clear(int v)    {ij(v);if(Isch(v))f[io]^=(1<<jo);}

 void Clear(CB1024 & z2)  ;

 CB1024 Inverse();

 CB1024 operator & (CB1024  z2);

 CB1024 operator | (CB1024  z2);

 CB1024 operator ^ (CB1024  z2);

 CB1024 operator - (CB1024  z2);

 void operator &= (CB1024  z2);

 void operator |= (CB1024  z2);

 void operator ^= (CB1024  z2);

 void operator -= (CB1024  z2);

 int operator == (CB1024  z2);

 CB1024 CB1024::operator ~();

 int NonNul();     int Nul();

 int Count();

 int First();

 void String(USHORT *tr,int &n);

 void ImageMarques(char * lib,int mmd);

 };

 int CB1024::io=0, CB1024::jo=0,CB1024::isize=20;

 

 

//------

void CB1024::ImageMarques(char * lib, int mmd)

{ E$.E(lib);   if(mmd) mms.ev(mmd);E$.E(" : ");

for(int i=0;i<col+2;i++) if(Isch(i)) {mms.ev(i);E$.Esp();} 

E$.Enl();}

//-----

void CB1024::Init(){for(int i=0;i<20;i++) f[i]=0; }

void CB1024::InitUn(){for(int i=0;i<isize;i++) f[i]=-1; }

 

int CB1024::NonNul(){for(int i=0;i<isize;i++) if(f[i])return 1;return 0; }

int CB1024::Nul(){for(int i=0;i<isize;i++) if(f[i])return 0;return 1; }

int CB1024::Count(){int c=0;for(int i=0;i<col+2;i++)if(Isch(i))c++; return c;};

//----

CB1024 CB1024::Inverse()

{CB1024 w;for(int i=0;i<col+2;i++)if(Isch(i))w.Set(i^1);  return w;};

//----

void CB1024::String(USHORT * r, int &n)

{n=0;   for(int i=2;i<col+2;i++)if(Isch(i))r[n++]=(USHORT)i;        }

CB1024 CB1024::operator & (CB1024  z2){CB1024 w;

         for(int i=0;i<isize;i++)w.f[i]=f[i]&z2.f[i]; return w; }

CB1024 CB1024::operator | (CB1024  z2){CB1024 w;

         for(int i=0;i<isize;i++)w.f[i]=f[i]|z2.f[i]; return w; }

CB1024 CB1024::operator ^ (CB1024  z2){CB1024 w;

         for(int i=0;i<isize;i++)w.f[i]=f[i]^z2.f[i]; return w; }

void CB1024::operator &= (CB1024  z2)

         { for(int i=0;i<isize;i++)  f[i]&=z2.f[i]; }

void CB1024::operator |= (CB1024  z2)

        { for(int i=0;i<isize;i++)  f[i]|=z2.f[i];  }

void CB1024::operator ^= (CB1024  z2)

         {for(int i=0;i<isize;i++)  f[i]^=z2.f[i]; }

int CB1024::operator == (CB1024  z2){    for(int i=0;i<isize;i++)

              if(!(f[i]==z2.f[i]))return 0; return 1; }

CB1024 CB1024::operator - (CB1024  z2){CB1024 w;

         for(int i=0;i<isize;i++)w.f[i]=f[i]^(f[i]&z2.f[i]); return w; }

void CB1024::operator -= (CB1024  z2){

         for(int i=0;i<isize;i++)f[i]^=(f[i]&z2.f[i]);  }

 

 

//------

int CB1024::First()

{for(int i=0;i<col+2;i++)if(Isch(i)) return i; return 0;}

 

 

PATH  describing a path

 

 

That class contains basically sequence of tags or candidates describing a path

It is used both in the building phase and to store intermediate results when looking for the shortest path for an identified  nice loop or “chain”. In fact, a class PATH_BLOC has been added  to ease the search of the shortest path within a layer. PATH_BLOC is just a bloc of 50 PATH

 

 

 

class PATH    

{public: USHORT pth[50],ipth;

inline void Init(){ipth=0;}

inline void Set(USHORT i,USHORT x){pth[i]=x;}

inline void Add(USHORT x){if(ipth<50)pth[ipth++]=x;}

void Add(USHORT * pthp,USHORT ipthp)

        {for(int i=0;i<ipthp;i++) Add(pthp[i]);}

void Add(PATH & px){Add(px.pth,px.ipth);}

void Expand(PATH & px){Add(&px.pth[1],px.ipth-1);} // skip first

void ImageMarques();

void PrintPath();

void PrintPath_refus();

inline USHORT GetLast(){if(ipth) return pth[ipth-1];else return 0;}

inline USHORT GetFirst(){if(ipth) return pth[0];else return 0;}

inline USHORT Get(int x){return pth[x];}

inline void Back(){ipth--;}

int IsActiveLoop();

void  CleanLoop(int length) ; // do it

} ; 

 

 

 

/* a bloc of 50 paths to build forward the final path*/

 

class PATH_BLOC

{public: PATH ps[50];  USHORT nps;

inline void Init(){nps=0;}

void Add(PATH x){if(nps<50) ps[nps++]=x;}

inline USHORT GetFirst(USHORT ix){return ps[ix].GetFirst();}

inline USHORT GetLast(USHORT ix){return ps[ix].GetLast();}

void Image(char * lib)

   {E$.Enl(lib);

    for (int i=0;i<nps;i++) ps[i].PrintPath();}

};

 

And now the routines attached to PATHNot shown in the .h file

These are mainly some prints for test purpose, but

It is also the start point to build the list of candidates to eliminate after a chain has been entered successfully in the TCHAN class.

IsActiveLoop is likely obsolete (to be checked)

 

void PATH::ImageMarques()

{if(!o$.ot) return; E$.Echem();

  for(int i=0;i<ipth-2;i++){zpln.ImageM(pth[i]);E$.E(" -> ");} 

 if(pth[0]==pth[ipth-1]){zpln.ImageM(pth[ipth-2]);E$.E(" -> ");

                        zpln.ImageM(pth[ipth-1]); } // it is a loop

 else {zpln.ImageM(pth[ipth-2]);E$.Ewl(); zpln.ImageM(pth[ipth-1]^1); }

 E$.Enl();}

 

 

void PATH::PrintPath() {zpln.PrintPath(pth,ipth);}

 

void PATH::PrintPath_refus() // very special test purpose only

  {se_refus << "Yloop []";

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

        se_refus << t81f[zpln.zp[pth[i]].ig].pt << " ";

   se_refus<<endl;

         zpln.PrintPath(pth,ipth);}

 

int PATH::IsActiveLoop()// yes if potential elimination

{for (int i=0;i<ipth;i++)for (int j=i+1;j<=ipth;j++)

{USHORT m1=pth[i]^1,m2=pth[j]; // the or condition

 if(zcf.h.dp.IsActiveOr( m1, m2) )return 1;

 if(zcf.h.dp.IsActiveOr( m1^1, m2^1) )return 1;

}

return 0;}

 

 

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

/*  an active loop has been found

    open the chain and

       if ok set up eliminations */

void  PATH::CleanLoop(int length)  // do it

{jdk.PointK();

if(!tchain.Chaine(length,pth[0])) return;   

 for (int i=0;i<(ipth-1);i++)for (int j=i+1;j<ipth;j++)

   {zcf.h.dp.CleanOr(pth[i]^1,pth[j]);

     zcf.h.dp.CleanOr(pth[i],pth[j]^1);}

 if(o$.ot)tchain.PrintElims();

}

 

ZGS table of used 81 bit fields

 

 

I am not 100% sure I would have created that table for SE clone alone.

In my solver, many 81 patterns are in use and I found better to have an intermediate table to store them.

 

In that table,

the first 81 positions are the cells in 81 bit field form.

The next 54 positions are the common cels row/box and column/box.

 

Other 81 pattern are enterd and piled sequentially.

 

The table has only one member and nearly no function associated.

 

 

 

#define zgs_lim 10000

class ZGROUPE     // en fixe 81 points 8       puis  54 groupes

 {public: ZINFL z[zgs_lim];

  USHORT iz;

  ZGROUPE();

  void ReInit(){iz=81+54;} // first after compulsory entries

  inline ZINFL getz(int i) {return z[i];};

  USHORT Charge(ZINFL & z);

  }zgs;  

 

 

ZGROUPE::ZGROUPE ()         

{ int i,j;  ZINFL z0,z1; z0.Init(); z1.InitUn();

 for(i=0;i<81;i++)    { z[i]=z0;z[i].Set(i); }  // les z de 81 cases

 int k,n=0,il=81;                    // puis les z de groupe

   for(i=0;i<18;i++) for(j=0;j<3;j++)

  { z[il].Init();

    if(i<9)   for(k=0;k<3;k++) z[il].Set(n++);

    else{int c=i-9; for(k=0;k<3;k++) z[il].Set(c+27*j+9*k);}

    il++; }

 ReInit();

}

 

//------          pour les additions

USHORT ZGROUPE::Charge(ZINFL  &ze)

{if(ze.Nul()){E$.Estop( "zgs groupe nul");return 0;}

 for(int i=0;i<iz;i++) if(z[i]==ze) return i;

 if(iz<zgs_lim) {z[iz++]=ze ;return (iz-1);}

 E$.Elimite( "ZGS");return 0;}