SEclone  checking uniqueness

 

Any new puzzle is first checked for a unique solution.

This is done thru the process I use in puzzle generation. It has nearly no link to the rest of the code, so it can be skipped.

 

The result of that task (solution) is kept with 2 identified targets:

 

Early detection of any bug in the program leading to a false elimination (then aigstop is set to 1 and the program is halted as soon as possible)

 

In the nested part of the chains (nothing done so far), to speed up the process, start from a non valid candidate.

 

The corresponding code is located in 2 classes

 

 

#include "h\_01f_  unpas.h"                     // class to handle recursive mainly in puzzle generation

                                         // but also in brute force solving (checking validity)

#include "h\_01g_  unjeu.h"                     // class start/end for tasks using class unpas

 

And the .cpp file

 

#include "c\_01f_  unpas.cpp"

 

 

 

The first class is UN_JEU, reduced to what is necessary to check uniqueness

 

ggf is the place where the result (assuming  one solution only) is stored

 

 

// that class is designed in my solver to handle recursive tasks as

//  . puzzles generators

//  . brute force solving ...

// here it is reduced to what is necessary to check uniqueness using existing code

 

 

class UN_JEU{public:

   UNPAS dep;   GG gg ,ggf; char *gn;

   UN_JEU(){gn=gg.pg;}

 

   long Analyse(GG & ge)

          {gg.Copie(ge);dep.Init(gg);

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

            {char c=gg.pg[i]; if(c>'0' && c<='9') dep.Fixer(i,c-'1'); }

             dep.NsolPas(); return dep.nsol;}

   int  Unicite(GG & ge) {return(Analyse(ge)==1);}

 

}un_jeu;

 

The second class is UNPAS, again reduced to what is necessary to check uniqueness

 

That class uses a table of the “variable part of a cell”  UNP defined earlier.

The main function NsomPas() is recursive.

 

class UNPAS {public:   static ULONG nsol,cptlx;    static UINT cp1,cp2;

   UNP tu[81];   GG gg;  char * gr;

   ZINFL libres;  USHORT nlibres,nactif,iactif,maxlibres;

   CB9CH candactif;

 

   UNPAS() {gr=gg.pg;}

   UNPAS(UNPAS * old){*this=*old;gr=gg.pg;}

   void Init(GG ge)

        {libres.InitUn();nlibres=81;nsol=0;tu[0].Init();

         gg.Copie(ge);    for(int i=1;i<81;i++)tu[i]=tu[0];}

 

   void Fixer(int i,USHORT  ch )

        {if(libres.Off(i)) return;  libres.Clear(i); nlibres--;

        tu[i].Fixer(ch); Clear(i,ch);gr[i]=ch+'1';}

 

   void Clear(int i8,USHORT  ch );

   int Avance(); // tout ce que l'on peut faire

   void NsolPas(); //id et lct pas suivant

   ZINFL GetZ(){ZINFL zw;for(int i=0;i<81;i++) if(gr[i]-'0') zw.Set(i);

                return zw;}

 

  };

ULONG UNPAS::nsol, UNPAS::cptlx;   

UINT UNPAS::cp1, UNPAS::cp2;

 

 

And now the functions located in the .cpp file

 

Avance() 

solves as much as possible using the very basic rule.

Priority is given to cell, easier to solve

If nothing comes out of a cell, an attempt is made in rows/col/boxes

 

NsolPas() 

Recursive search assigning one unassigned cell

The first cell with 2 candidates is taken

If not a cell the lowest number fo candidates

 

 

void UNPAS::Clear(int i8,USHORT  ch )

       {P81F *wf=&t81f[i8];for(int i=0;i<20;i++)

            {USHORT j=wf->pi[i];  if(libres.On(j))tu[j].Clear(ch);}}

 

int UNPAS::Avance()

{USHORT ib=1; while(ib&&nlibres)

   {ib=0;for (USHORT i=0;i<81;i++)

        {if(tu[i].ncand==0)return 1;

         if( libres.On(i)&&(tu[i].ncand==1))

          {ib=1;Fixer(i,tu[i].GetCand()); }  } // fixer pour compte

    if(ib) continue;   // priorité aux cases  sinon caché

    for (USHORT ie=0; ie<27;ie++)  // sera "relativement rare"

      { USHORT * pel=divf.el81[ie];

        CB9CH or,deux;

        for(USHORT p=0;p<9;p++)

          { USHORT i81=pel[p];

            if(libres.Off(i81)) or|=tu[i81].cand;    //force double

           CB9CH w=tu[i81].cand &or; deux |=w;

           or|=tu[i81].cand;}

        if(or.f-0x1ff) return 1; // blocage

        or -=deux; if(!or.f)continue; // pas de fixation

        for(USHORT  ich=0;ich<9;ich++) if(or.On(ich) )

        for(USHORT p=0;p<9;p++)  if(tu[pel[p]].cand.On(ich))

              {ib=1;Fixer(pel[p],ich);break;}

         } }    //end ie while

return 0;}

 

void UNPAS::NsolPas()

{if(Avance())return; // blocage

if(!nlibres) {nsol++;if(nsol==1)  un_jeu.ggf.Copie(gg); return;  }

USHORT max=10,iw; for(int i=0;i<81;i++)  // on lance le pas suivant

  { if(libres.Off(i)) continue;     iw=tu[i].ncand;if(iw<2)continue;

   if(iw<max){max=iw;iactif=i;if(max<3) break;}}    //premier deux cand

candactif=tu[iactif].cand;

for(int i=0;i<9;i++) if(candactif.On(i))

  {UNPAS pn(this);  pn.Fixer(iactif,i);  pn.NsolPas();

   if((nsol>1)) return ;    }

}