## 3.77us Solver(2.8G CPU, TestCase:17Sodoku)

Programs which generate, solve, and analyze Sudoku puzzles

### Re: 12us Solver(2.8G CPU, TestCase:17Sodoku)

OK,,, Uniq Palace to Uniq Row is accomplished.
zhouyundong_2012

Posts: 144
Joined: 10 February 2012

### Re: 12us Solver(2.8G CPU, TestCase:17Sodoku)

zhouyundong_2012

Posts: 144
Joined: 10 February 2012

### Re: 12us Solver(2.8G CPU, TestCase:17Sodoku)

A Google search quickly shows it is still available at http://magictour.free.fr/top1465 . Note this list of hardest puzzles was assembled circa 2006. Things have changed considerably since then.
ronk
2012 Supporter

Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

### Re: 12us Solver(2.8G CPU, TestCase:17Sodoku)

I have been slowly working my way through the source code. zhouyundong_2012 uses an array of int where each element holds one chute (three rows) of basically pencil marks for a single digit. I say "basically pencil marks" because I think placed digits are also set. The solver appears to use locked candidates (perhaps incompletely) and hidden singles. I haven't seen anything that appears to be doing naked singles, and I can't quite figure out if it really does column-block locked candidates, or only does row-block locked candidates. The row-block locked candidates code is very very short and fast, quite entertaining reading for bit twiddling wonks like me.

zhouyundong_2012, your AN(v,n) macro negates n each time. Since AN() is always called eight times in a row with the same n, it would be more efficient to negate n outside of AN(). Of course some compilers can figure this out for you, but not all.

JasonLion
2017 Supporter

Posts: 641
Joined: 25 October 2007
Location: Silver Spring, MD, USA

### Re: 12us Solver(2.8G CPU, TestCase:17Sodoku)

I did not do column-block locked canididate. I think column-block can't work well.
Thank you for your comment for this code.
zhouyundong_2012

Posts: 144
Joined: 10 February 2012

### Re: 12us Solver(2.8G CPU, TestCase:17Sodoku)

Of course some compilers can figure this out for you, but not all.

Thank you!
zhouyundong_2012

Posts: 144
Joined: 10 February 2012

### Re: 12us Solver(2.8G CPU, TestCase:17Sodoku)

Code: Select all
`#ifndef __sd_h__#define __sd_h__#define TotalBoard          50000 //Total Games//Answer Attribute#define NoAnswer          0#define UniqAnswer          1#define MoreAnswer          2//High, Middle, Low 9 bit of a 27-bit number#define HIGH_9_BIT(v)       ((v) >> 18)#define MID_9_BIT(v)       (((v) >> 9) & 0x1FF)#define LOW_9_BIT(v)       ((v) & 0x1FF)#define HML_9_BIT(v, l)       ((v) >> TblMult9[l] & 0x1FF)#define FULL_TO_COLUMN(v)    (((v) | ((v) >> 9) | ((v) >> 18)) & 0x1FF) //Full Mask(27-bit) to 9 bit#define FULL_TO_SHRINK(v)    (TblShrinkHigh[(v) >> 18] | TblShrinkMid[((v) >> 9) & 0x1FF] | TblShrinkLow[(v) & 0x1FF]) //000 to 0, else to 1#define BIT_SET_27          0x07FFFFFF#define AN(v, n)          (v) &= (n)struct CGame {  public:   int             F[27]; //27-bit Full Mask   int             U[27]; //3-bit Unique in Row   int             Block; //The Block Number of guess [0, 27)   int             Line; //The Line Number of guess [0, 3)   int             Mask; //The 9-bit Mask of guess   int             Left; //The 9-bit Left Mask of guess};//Common Tableextern int             TblMult3[81];extern int             TblDivide3[81];extern int             TblRmder3[81];extern int             TblMult9[9];//Basis Tableextern int             TblCombineMask[512];extern int             TblTailZero[512];extern int             TblNumberOne[512];extern int             TblAnother1[27];extern int             TblAnother2[27];extern int             TblShiftLeft[27];//Table of Decompose Boardextern int             TblBoard_Block[81];extern int             TblBoard_BlockMask[81];extern int             TblBoard_GridUniq[81];//Table of Initialextern int             TblSelfMask[81];extern int             TblOtherMask[81];//Complex Friend Methodextern int             TblMaskSingle[512];extern int             TblMaskDouble[512];//Other Tableextern int             TblColumnMask[8];extern bool             TblUniqFlag[8];//Shrink Maskextern int             TblShrinkLow[512];extern int             TblShrinkMid[512];extern int             TblShrinkHigh[512];//Complex Methodextern int             TblComplexMask[512];extern int             TblColumnSingle[512];extern int             TblShrinkSingle[512];extern void             CreateTable();#endif`
zhouyundong_2012

Posts: 144
Joined: 10 February 2012

### Re: 12us Solver(2.8G CPU, TestCase:17Sodoku)

Code: Select all
`#include <string.h>#include "sd.h"//Common Tableint                   TblMult3[81];int                   TblDivide3[81];int                   TblRmder3[81];int                   TblMult9[9];//Basis Tableint                   TblCombineMask[512];int                   TblTailZero[512];int                   TblNumberOne[512];int                   TblAnother1[27];int                   TblAnother2[27];int                   TblShiftLeft[27];//Table of Decompose Boardint                   TblBoard_Block[81];int                   TblBoard_BlockMask[81];int                   TblBoard_GridUniq[81];//Table of Initialint                   TblSelfMask[81];int                   TblOtherMask[81];//Complex Friend Methodint                   TblMaskSingle[512];int                   TblMaskDouble[512];//Other Tableint                   TblColumnMask[8];bool                TblUniqFlag[8];//Shrink Maskint                   TblShrinkLow[512];int                   TblShrinkMid[512];int                   TblShrinkHigh[512];//Complex Methodint                   TblComplexMask[512];int                   TblColumnSingle[512];int                   TblShrinkSingle[512];void CreateTblCommon(){   for (int i = 0; i < 81; i++)   {      TblMult3[i] = i * 3;      TblDivide3[i] = i / 3;      TblRmder3[i] = i % 3;   }   for (int i = 0; i < 9; i++)   {      TblMult9[i] = i * 9;   }}void CreateTblCombineMask(){   for (int i = 0; i < 512; i++)   {      TblCombineMask[i] = (i | (i << 9) | (i << 18)) ^ BIT_SET_27;   }}void CreateTblAnother(){   for (int i = 0; i < 27; i++)   {      switch (i % 3)      {      case 0: //At Top         TblAnother1[i] = i + 1;         TblAnother2[i] = i + 2;         break;      case 1: //At Middle         TblAnother1[i] = i - 1;         TblAnother2[i] = i + 1;         break;      case 2: //At Bottom         TblAnother1[i] = i - 2;         TblAnother2[i] = i - 1;         break;      }   }}void CreateTblTailZero(){   memset(TblTailZero, 0, sizeof(TblTailZero));   for (int i = 0; i < 512; i++)   {      for (int j = 0; j < 9; j++)      {         if (i & (1 << j))            break;         TblTailZero[i]++;      }   }}void CreateTblNumberOne(){   memset(TblNumberOne, 0, sizeof(TblNumberOne));   for (int i = 0; i < 512; i++)   {      for (int j = 0; j < 9; j++)      {         if (i & (1 << j))            TblNumberOne[i]++;      }   }}void CreateTblShiftLeft(){   for (int i = 0; i < 27; i++)   {      TblShiftLeft[i] = 1 << i;   }}void CreateTblBasis(){   CreateTblCombineMask();   CreateTblAnother();   CreateTblTailZero();   CreateTblNumberOne();   CreateTblShiftLeft();}void CreateTblBoard(){   for (int i = 0; i < 81; i++)   {      TblBoard_Block[i] = i / 27;      TblBoard_BlockMask[i] = 1 << i % 27;      TblBoard_GridUniq[i] = 1 << i % 27 / 9;   }}void CreateTblSelfMask(){   int Mask[3] = { 0x7E3F1F8, 0x71F8FC7, 0x0FC7E3F };   int Row[3] = { 0x7FFFE00, 0x7FC01FF, 0x3FFFF };   for (int i = 0; i < 81; i++)   {      int Palace = i % 9 / 3;      TblSelfMask[i] = Mask[Palace] & Row[i % 27 / 9] | TblBoard_BlockMask[i];   }}void CreateTblOtherMask(){   for (int i = 0; i < 81; i++)   {      TblOtherMask[i] = TblCombineMask[1 << i % 9];   }}void CreateTblMaskSingle(){   for (int i = 0; i < 512; i++)   {      TblMaskSingle[i] = i;      int v = i >> 6; //High 3 bit      if (v != 4 && v != 2 && v != 1)         TblMaskSingle[i] &= 0x3F;      v = i >> 3 & 0x7; //Middle 3 bit      if (v != 4 && v != 2 && v != 1)         TblMaskSingle[i] &= 0x1C7;      v = i & 0x7; //Low 3 bit      if (v != 4 && v != 2 && v != 1)         TblMaskSingle[i] &= 0x1F8;      TblMaskSingle[i] = TblCombineMask[TblMaskSingle[i]];   }}void CreateTblMaskDouble(){   for (int i = 0; i < 512; i++)   {      TblMaskDouble[i] = i;      int v = i >> 6; //High 3 bit      if (v != 6 && v != 5 && v != 3)         TblMaskDouble[i] &= 0x3F;      v = i >> 3 & 0x7; //Middle 3 bit      if (v != 6 && v != 5 && v != 3)         TblMaskDouble[i] &= 0x1C7;      v = i & 0x7; //Low 3 bit      if (v != 6 && v != 5 && v != 3)         TblMaskDouble[i] &= 0x1F8;      TblMaskDouble[i] = TblCombineMask[TblMaskDouble[i]];   }}void CreateTblColumnMask(){   memset(TblColumnMask, 0, sizeof(TblColumnMask));   for (int i = 0; i < 8; i++)   {      for (int j = 0; j < 3; j++)      {         if (i & (1 << j))            TblColumnMask[i] |= 0x1FF << TblMult9[j];      }   }}void CreateTblUniqFlag(){   memset(TblUniqFlag, 0, sizeof(TblUniqFlag));   for (int i = 0; i < 8; i++)   {      if (TblNumberOne[i] >= 2)         TblUniqFlag[i] = true;   }}void CreateShrinkMask(){   memset(TblShrinkLow, 0, sizeof(TblShrinkLow));   for (int i = 0; i < 512; i++)   {      TblShrinkLow[i] |= i & 0x1C0 ? 4 : 0;      TblShrinkLow[i] |= i & 0x38 ? 2 : 0;      TblShrinkLow[i] |= i & 0x7 ? 1 : 0;   }   for (int i = 0; i < 512; i++)   {      TblShrinkMid[i] = TblShrinkLow[i] << 3;      TblShrinkHigh[i] = TblShrinkLow[i] << 6;   }}void CreateComplexMask(){   int MaskH[9] = { 0x7FFFE07, 0x7FFFE38, 0x7FFFFC0, 0x7FC0FFF, 0x7FC71FF, 0x7FF81FF, 0x1FFFFF, 0xE3FFFF, 0x703FFFF }; //A B C   int MaskV[9] = { 0x7E3F1FF, 0x71F8FFF, 0xFC7FFF, 0x7E3FFF8, 0x71FFFC7, 0xFFFE3F, 0x7FFF1F8, 0x7FF8FC7, 0x7FC7E3F }; //A 0 0   int index;   for (int i = 0; i < 512; i++)   {      if (!(i & 0x7) || !(i & 0x38) || !(i & 0x1C0) || !(i & 0x124) || !(i & 0x92) || !(i & 0x49))      {         TblComplexMask[i] = 0;         continue;      }      TblComplexMask[i] = BIT_SET_27;      //Like Locked Candidate      for (int j = 0; j < 3; j++)      {         for (int k = 0; k < 3; k++)         {            index = TblMult3[k] + j;            if ((i & (1 << index)) && !(i & (1 << (TblMult3[TblAnother1[k]] + j))) && !(i & (1 << (TblMult3[TblAnother2[k]] + j))))               TblComplexMask[i] &= MaskH[index]; //Horizontal            index = TblMult3[j] + k;            if ((i & (1 << index)) && !(i & (1 << TblAnother1[index])) && !(i & (1 << TblAnother2[index])))               TblComplexMask[i] &= MaskV[index]; //Vertical         }      }   }   for (int i = 0; i < 512; i++)   {      if ((i & FULL_TO_SHRINK(TblComplexMask[i])) == 0)         TblComplexMask[i] = 0;      else if ((i & FULL_TO_SHRINK(TblComplexMask[i])) == i)         TblComplexMask[i] = BIT_SET_27;   }}void CreateTblColumnSingle(){   memset(TblColumnSingle, 0, sizeof(TblColumnSingle));   for (int i = 0; i < 512; i++)   {      if (TblNumberOne[i & 0x7] == 0 || TblNumberOne[i & 0x38] == 0 || TblNumberOne[i & 0x1C0] == 0)         continue;      if (TblNumberOne[i & 0x7] == 1) //Low 3 bit         TblColumnSingle[i] |= 0x49;      if (TblNumberOne[i & 0x38] == 1) //Middle 3 bit         TblColumnSingle[i] |= 0x92;      if (TblNumberOne[i & 0x1C0] == 1) //High 3 bit         TblColumnSingle[i] |= 0x124;   }}void CreateTblShrinkSingle(){   for (int i = 0; i < 512; i++)   {      int j = i & FULL_TO_SHRINK(TblComplexMask[i]);      TblShrinkSingle[i] = j;      if (TblNumberOne[j & 0x7] != 1) //Low 3 bit         TblShrinkSingle[i] &= 0x1F8;      if (TblNumberOne[j & 0x38] != 1) //Middle 3 bit         TblShrinkSingle[i] &= 0x1C7;      if (TblNumberOne[j & 0x1C0] != 1) //High 3 bit         TblShrinkSingle[i] &= 0x3F;   }}void CreateTable(){   CreateTblCommon();   CreateTblBasis();   CreateTblBoard();   CreateTblSelfMask();   CreateTblOtherMask();   CreateTblMaskSingle();   CreateTblMaskDouble();   CreateTblColumnMask();   CreateTblUniqFlag();   CreateShrinkMask();   CreateComplexMask();   CreateTblColumnSingle();   CreateTblShrinkSingle();}`
zhouyundong_2012

Posts: 144
Joined: 10 February 2012

### Re: 12us Solver(2.8G CPU, TestCase:17Sodoku)

Code: Select all
`#include <windows.h>#include <stdio.h>#include "sd.h"/* * First Step : Compile this project with __ProgramWritter used and Run it * Second Step: Replace the function Update in the bottom of this file with all contents of Update.c created by First Step in current directory * Third Step : Recompile this project without __ProgramWritter and Run it * *           Warning: Can NOT comment __ProgramWritter until finish 3 steps! * * Good Luck! Shanghai China 2012/3/14 Zhou Yun Dong */#define __ProgramWritterbyte                Board[81]; //BoardCGame                G[50]; //Guess Boardint                   Index; //Guess Indexint                   BlockMask[27]; //Blockint                   BlockMaskSum[3]; //Sum of BlockMaskint                   F[27]; //27-bit Full Maskint                   U[27]; //3-bit Unique in Rowint                   CompF[27]; //Use for Comparebyte                AllBoard[TotalBoard][81]; //All Boardsint                   TestCaseNumber; //Actual Number of Test Casebool                Update();void                Guess();bool                Rollback();byte                Calculate();void InitSodoku(){   Index = 1;   BlockMaskSum[0] = BlockMaskSum[1] = BlockMaskSum[2] = 0;   for (int B = 0; B < 27; B++)   {      BlockMask[B] = U[B] = 0;      CompF[B] = F[B] = BIT_SET_27;   }   //Get Full Mask   for (int i = 0; i < 81; i++)   {      if (Board[i] == '0')         continue;      int B = TblMult3[Board[i] - '1'] + TblBoard_Block[i];      //Get BlockMask and Sum of BlockMask      BlockMaskSum[TblBoard_Block[i]] |= TblBoard_BlockMask[i];      BlockMask[B] |= TblBoard_BlockMask[i];      //Get Full Mask      F[B] &= TblSelfMask[i];      F[TblAnother1[B]] &= TblOtherMask[i];      F[TblAnother2[B]] &= TblOtherMask[i];      U[B] |= TblBoard_GridUniq[i];   }   for (int B = 0; B < 27; B++)      F[B] &= BlockMaskSum[TblRmder3[B]] ^ BlockMask[B] ^ BIT_SET_27;   memcpy(G[0].F, F, sizeof(F));}void Guess(){   int Least = 9;   for (int i = 0; i < 27; i++)   {      if (TblUniqFlag[U[i]])         continue;      G[Index].Block = i;      if (TblNumberOne[LOW_9_BIT(F[i])] == 2)      {         G[Index].Line = 0;         goto FoundLeast;      }      if (TblNumberOne[MID_9_BIT(F[i])] == 2)      {         G[Index].Line = 1;         goto FoundLeast;      }      if (TblNumberOne[HIGH_9_BIT(F[i])] == 2)      {         G[Index].Line = 2;         goto FoundLeast;      }   }   Least = 9;   for (int i = 0; i < 27; i++)   {      for (int j = 0; j < 3; j++)      {         if (U[i] & TblShiftLeft[j])            continue;         int NumberOne = TblNumberOne[HML_9_BIT(F[i], j)];         if (Least > NumberOne)         {            G[Index].Block = i;            G[Index].Line = j;            if ((Least = NumberOne) == 2)               goto FoundLeast;         }      }   }FoundLeast:   int Left = HML_9_BIT(F[G[Index].Block], G[Index].Line);   int Mask = Left & -Left;   //Save Data   G[Index].Mask = Mask;   G[Index].Left = Left;   for (int B = 0; B < 27; B++)   {      G[Index].F[B] = CompF[B] = F[B];      G[Index].U[B] = U[B];   }   F[G[Index].Block] &= TblSelfMask[TblTailZero[Mask] + TblMult9[G[Index].Line]];   Index++;}bool Rollback(){   if (Index-- == 1)      return false;   //Restore Data   int Block = G[Index].Block;   int Line = G[Index].Line;   for (int B = 0; B < 27; B++)   {      CompF[B] = F[B] = G[Index].F[B];      U[B] = G[Index].U[B];   }   G[Index].Left ^= G[Index].Mask;   G[Index].Mask = G[Index].Left & -G[Index].Left;   F[Block] &= TblSelfMask[TblTailZero[G[Index].Mask] + TblMult9[Line]];   //Whether The Last Guess   Index += TblNumberOne[G[Index].Left] != 1;   return true;}byte Calculate(){   bool FoundAnswer = false;   while (true)   {      if (Update())      {         if (U[0] + U[1] + U[2] != 21 || U[3] + U[4] + U[5] != 21 || U[6] + U[7] + U[8] != 21             || U[9] + U[10] + U[11] != 21 || U[12] + U[13] + U[14] != 21 || U[15] + U[16] + U[17] != 21             || U[18] + U[19] + U[20] != 21 || U[21] + U[22] + U[23] != 21 || U[24] + U[25] + U[26] != 21)         {            Guess();            continue;         }         if (FoundAnswer) //Find Answer            return MoreAnswer;         FoundAnswer = true;      }      if (!Rollback()) //Backtrack Over         return FoundAnswer ? UniqAnswer : NoAnswer;   }}#ifdef __ProgramWrittervoid ProgramWritter(){   char str[256];   FILE *fp = fopen("Update.c", "w+");   fputs("bool Update()\n", fp);   fputs("{\n", fp);   fputs("\tint Shrink = ~0;\n", fp);   fputs("\twhile (Shrink)\n", fp);   fputs("\t{\n", fp);   fputs("\t\tShrink = 0;\n", fp);   for (int i = 0; i < 27; i++)   {      sprintf(str, "\t\tif (CompF[%d] != F[%d])\n", i, i);      fputs(str, fp);      fputs("\t\t{\n", fp);      //Complex Self Method      sprintf(str, "\t\t\tShrink = FULL_TO_SHRINK(F[%d]);\n", i);      fputs(str, fp);      sprintf(str, "\t\t\tif ((F[%d] &= TblComplexMask[Shrink]) == 0)\n", i);      fputs(str, fp);      fputs("\t\t\t\treturn false;\n", fp);      sprintf(str, "\t\t\tCompF[%d] = F[%d];\n", i, i);      fputs(str, fp);      //Complex Friend Method      sprintf(str, "\t\t\tint Column = FULL_TO_COLUMN(F[%d]);\n", i);      fputs(str, fp);      sprintf(str, "\t\t\tint C1 = Column | FULL_TO_COLUMN(F[%d]);\n", TblAnother1[i]);      fputs(str, fp);      sprintf(str, "\t\t\tint C2 = Column | FULL_TO_COLUMN(F[%d]);\n", TblAnother2[i]);      fputs(str, fp);      sprintf(str, "\t\t\tF[%d] &= TblMaskSingle[Column] & TblMaskDouble[C2];\n", TblAnother1[i]);      fputs(str, fp);      sprintf(str, "\t\t\tF[%d] &= TblMaskSingle[Column] & TblMaskDouble[C1];\n", TblAnother2[i]);      fputs(str, fp);      //Single Grid Method      sprintf(str, "\t\t\tif (TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]] != U[%d])\n", i);      fputs(str, fp);      fputs("\t\t\t{\n", fp);      sprintf(str, "\t\t\t\tU[%d] |= TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]];\n", i);      fputs(str, fp);      //Friend Block      sprintf(str, "\t\t\t\tint S = ~(F[%d] & TblColumnMask[U[%d]]);\n", i, i);      fputs(str, fp);      fputs("\t\t\t\t", fp);      for (int j = TblRmder3[i]; j < 27; j += 3)      {         if (j != i)         {            sprintf(str, "AN(F[%d], S); ", j);            fputs(str, fp);         }      }      fputs("\n", fp);      fputs("\t\t\t}\n", fp);      fputs("\t\t}\n", fp);   }   fputs("\t}\n", fp);   fputs("\treturn true;\n", fp);   fputs("}", fp);   fclose(fp);}#endifbool ReadFile(){   FILE *file = fopen("TestCase.txt", "r");   if (!file)   {      printf("Can not open TestCase.txt in current directory");      getchar();      return false;   }   TestCaseNumber = 0;   while (fgets((char *)AllBoard[TestCaseNumber], 1024, file))   {      if (++TestCaseNumber == TotalBoard)         break;   }   fclose(file);   return true;}bool main(){   CreateTable();#ifdef __ProgramWritter   ProgramWritter();   return true;#endif   if (!ReadFile())      return false;   printf("Press Enter to Slove ...");   getchar();   //Set Highest Priority   DWORD dwOldProcessP = GetPriorityClass(GetCurrentProcess());   DWORD dwOldThreadP  = GetThreadPriority(GetCurrentThread());   SetPriorityClass(GetCurrentProcess(), REALTIME_PRIORITY_CLASS);   SetThreadPriority(GetCurrentThread(), THREAD_PRIORITY_TIME_CRITICAL);   //Get Frequency   LARGE_INTEGER Frequency;   ::QueryPerformanceFrequency(&Frequency);   //Get Start Time   LARGE_INTEGER start;   ::QueryPerformanceCounter(&start);   int Answer = 0;   //Procedure of Calculate   for (int i = 0; i < TestCaseNumber; i++)   {      memcpy(Board, AllBoard[i], 81);      InitSodoku();      if ((Answer = Calculate()) != UniqAnswer)         break;   }   //Get Stop Time   LARGE_INTEGER stop;   ::QueryPerformanceCounter(&stop);   double spend = (double)(stop.QuadPart - start.QuadPart) / (double)Frequency.QuadPart;   printf("Spend   = %f us\n", spend * 1000 * 1000);   printf("Total   = %d\n", TestCaseNumber);   printf("Average = %f us\n", spend * 1000 * 1000 / TestCaseNumber);   if (Answer != UniqAnswer)      printf("***************Result: %d   ***************\n", Answer);   //Restore Priority   SetThreadPriority(GetCurrentThread(), dwOldThreadP);   SetPriorityClass(GetCurrentProcess(), dwOldProcessP);   return true;}#ifdef __ProgramWritterbool Update(){   return true;}#else//open Update.c and copy to here#endif`
zhouyundong_2012

Posts: 144
Joined: 10 February 2012

### Re: 12us Solver(2.8G CPU, TestCase:17Sodoku)

This is the last version.

What can do next to improve the speed? I think that will be Guess(). How to guess effeciently, that is the question.

Sorry,Afmob. I will write a new, vast, complex, interesting web game Disaster Empire.
I think a lot lot of people will play it.

So,Afmob, you can use my code, and change everything freedom.

Anybody have the interest to write Disaster Empire with me?

For anyone, you can use this code.
zhouyundong_2012

Posts: 144
Joined: 10 February 2012

### Re: 12us Solver(2.8G CPU, TestCase:17Sodoku)

Code: Select all
`bool Update(){   int Shrink = ~0;   while (Shrink)   {      Shrink = 0;      if (CompF[0] != F[0])      {         Shrink = FULL_TO_SHRINK(F[0]);         if ((F[0] &= TblComplexMask[Shrink]) == 0)            return false;         CompF[0] = F[0];         int Column = FULL_TO_COLUMN(F[0]);         int C1 = Column | FULL_TO_COLUMN(F[1]);         int C2 = Column | FULL_TO_COLUMN(F[2]);         F[1] &= TblMaskSingle[Column] & TblMaskDouble[C2];         F[2] &= TblMaskSingle[Column] & TblMaskDouble[C1];         if (TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]] != U[0])         {            U[0] |= TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]];            int S = ~(F[0] & TblColumnMask[U[0]]);            AN(F[3], S); AN(F[6], S); AN(F[9], S); AN(F[12], S); AN(F[15], S); AN(F[18], S); AN(F[21], S); AN(F[24], S);          }      }      if (CompF[1] != F[1])      {         Shrink = FULL_TO_SHRINK(F[1]);         if ((F[1] &= TblComplexMask[Shrink]) == 0)            return false;         CompF[1] = F[1];         int Column = FULL_TO_COLUMN(F[1]);         int C1 = Column | FULL_TO_COLUMN(F[0]);         int C2 = Column | FULL_TO_COLUMN(F[2]);         F[0] &= TblMaskSingle[Column] & TblMaskDouble[C2];         F[2] &= TblMaskSingle[Column] & TblMaskDouble[C1];         if (TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]] != U[1])         {            U[1] |= TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]];            int S = ~(F[1] & TblColumnMask[U[1]]);            AN(F[4], S); AN(F[7], S); AN(F[10], S); AN(F[13], S); AN(F[16], S); AN(F[19], S); AN(F[22], S); AN(F[25], S);          }      }      if (CompF[2] != F[2])      {         Shrink = FULL_TO_SHRINK(F[2]);         if ((F[2] &= TblComplexMask[Shrink]) == 0)            return false;         CompF[2] = F[2];         int Column = FULL_TO_COLUMN(F[2]);         int C1 = Column | FULL_TO_COLUMN(F[0]);         int C2 = Column | FULL_TO_COLUMN(F[1]);         F[0] &= TblMaskSingle[Column] & TblMaskDouble[C2];         F[1] &= TblMaskSingle[Column] & TblMaskDouble[C1];         if (TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]] != U[2])         {            U[2] |= TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]];            int S = ~(F[2] & TblColumnMask[U[2]]);            AN(F[5], S); AN(F[8], S); AN(F[11], S); AN(F[14], S); AN(F[17], S); AN(F[20], S); AN(F[23], S); AN(F[26], S);          }      }      if (CompF[3] != F[3])      {         Shrink = FULL_TO_SHRINK(F[3]);         if ((F[3] &= TblComplexMask[Shrink]) == 0)            return false;         CompF[3] = F[3];         int Column = FULL_TO_COLUMN(F[3]);         int C1 = Column | FULL_TO_COLUMN(F[4]);         int C2 = Column | FULL_TO_COLUMN(F[5]);         F[4] &= TblMaskSingle[Column] & TblMaskDouble[C2];         F[5] &= TblMaskSingle[Column] & TblMaskDouble[C1];         if (TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]] != U[3])         {            U[3] |= TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]];            int S = ~(F[3] & TblColumnMask[U[3]]);            AN(F[0], S); AN(F[6], S); AN(F[9], S); AN(F[12], S); AN(F[15], S); AN(F[18], S); AN(F[21], S); AN(F[24], S);          }      }      if (CompF[4] != F[4])      {         Shrink = FULL_TO_SHRINK(F[4]);         if ((F[4] &= TblComplexMask[Shrink]) == 0)            return false;         CompF[4] = F[4];         int Column = FULL_TO_COLUMN(F[4]);         int C1 = Column | FULL_TO_COLUMN(F[3]);         int C2 = Column | FULL_TO_COLUMN(F[5]);         F[3] &= TblMaskSingle[Column] & TblMaskDouble[C2];         F[5] &= TblMaskSingle[Column] & TblMaskDouble[C1];         if (TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]] != U[4])         {            U[4] |= TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]];            int S = ~(F[4] & TblColumnMask[U[4]]);            AN(F[1], S); AN(F[7], S); AN(F[10], S); AN(F[13], S); AN(F[16], S); AN(F[19], S); AN(F[22], S); AN(F[25], S);          }      }      if (CompF[5] != F[5])      {         Shrink = FULL_TO_SHRINK(F[5]);         if ((F[5] &= TblComplexMask[Shrink]) == 0)            return false;         CompF[5] = F[5];         int Column = FULL_TO_COLUMN(F[5]);         int C1 = Column | FULL_TO_COLUMN(F[3]);         int C2 = Column | FULL_TO_COLUMN(F[4]);         F[3] &= TblMaskSingle[Column] & TblMaskDouble[C2];         F[4] &= TblMaskSingle[Column] & TblMaskDouble[C1];         if (TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]] != U[5])         {            U[5] |= TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]];            int S = ~(F[5] & TblColumnMask[U[5]]);            AN(F[2], S); AN(F[8], S); AN(F[11], S); AN(F[14], S); AN(F[17], S); AN(F[20], S); AN(F[23], S); AN(F[26], S);          }      }      if (CompF[6] != F[6])      {         Shrink = FULL_TO_SHRINK(F[6]);         if ((F[6] &= TblComplexMask[Shrink]) == 0)            return false;         CompF[6] = F[6];         int Column = FULL_TO_COLUMN(F[6]);         int C1 = Column | FULL_TO_COLUMN(F[7]);         int C2 = Column | FULL_TO_COLUMN(F[8]);         F[7] &= TblMaskSingle[Column] & TblMaskDouble[C2];         F[8] &= TblMaskSingle[Column] & TblMaskDouble[C1];         if (TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]] != U[6])         {            U[6] |= TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]];            int S = ~(F[6] & TblColumnMask[U[6]]);            AN(F[0], S); AN(F[3], S); AN(F[9], S); AN(F[12], S); AN(F[15], S); AN(F[18], S); AN(F[21], S); AN(F[24], S);          }      }      if (CompF[7] != F[7])      {         Shrink = FULL_TO_SHRINK(F[7]);         if ((F[7] &= TblComplexMask[Shrink]) == 0)            return false;         CompF[7] = F[7];         int Column = FULL_TO_COLUMN(F[7]);         int C1 = Column | FULL_TO_COLUMN(F[6]);         int C2 = Column | FULL_TO_COLUMN(F[8]);         F[6] &= TblMaskSingle[Column] & TblMaskDouble[C2];         F[8] &= TblMaskSingle[Column] & TblMaskDouble[C1];         if (TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]] != U[7])         {            U[7] |= TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]];            int S = ~(F[7] & TblColumnMask[U[7]]);            AN(F[1], S); AN(F[4], S); AN(F[10], S); AN(F[13], S); AN(F[16], S); AN(F[19], S); AN(F[22], S); AN(F[25], S);          }      }      if (CompF[8] != F[8])      {         Shrink = FULL_TO_SHRINK(F[8]);         if ((F[8] &= TblComplexMask[Shrink]) == 0)            return false;         CompF[8] = F[8];         int Column = FULL_TO_COLUMN(F[8]);         int C1 = Column | FULL_TO_COLUMN(F[6]);         int C2 = Column | FULL_TO_COLUMN(F[7]);         F[6] &= TblMaskSingle[Column] & TblMaskDouble[C2];         F[7] &= TblMaskSingle[Column] & TblMaskDouble[C1];         if (TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]] != U[8])         {            U[8] |= TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]];            int S = ~(F[8] & TblColumnMask[U[8]]);            AN(F[2], S); AN(F[5], S); AN(F[11], S); AN(F[14], S); AN(F[17], S); AN(F[20], S); AN(F[23], S); AN(F[26], S);          }      }      if (CompF[9] != F[9])      {         Shrink = FULL_TO_SHRINK(F[9]);         if ((F[9] &= TblComplexMask[Shrink]) == 0)            return false;         CompF[9] = F[9];         int Column = FULL_TO_COLUMN(F[9]);         int C1 = Column | FULL_TO_COLUMN(F[10]);         int C2 = Column | FULL_TO_COLUMN(F[11]);         F[10] &= TblMaskSingle[Column] & TblMaskDouble[C2];         F[11] &= TblMaskSingle[Column] & TblMaskDouble[C1];         if (TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]] != U[9])         {            U[9] |= TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]];            int S = ~(F[9] & TblColumnMask[U[9]]);            AN(F[0], S); AN(F[3], S); AN(F[6], S); AN(F[12], S); AN(F[15], S); AN(F[18], S); AN(F[21], S); AN(F[24], S);          }      }      if (CompF[10] != F[10])      {         Shrink = FULL_TO_SHRINK(F[10]);         if ((F[10] &= TblComplexMask[Shrink]) == 0)            return false;         CompF[10] = F[10];         int Column = FULL_TO_COLUMN(F[10]);         int C1 = Column | FULL_TO_COLUMN(F[9]);         int C2 = Column | FULL_TO_COLUMN(F[11]);         F[9] &= TblMaskSingle[Column] & TblMaskDouble[C2];         F[11] &= TblMaskSingle[Column] & TblMaskDouble[C1];         if (TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]] != U[10])         {            U[10] |= TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]];            int S = ~(F[10] & TblColumnMask[U[10]]);            AN(F[1], S); AN(F[4], S); AN(F[7], S); AN(F[13], S); AN(F[16], S); AN(F[19], S); AN(F[22], S); AN(F[25], S);          }      }      if (CompF[11] != F[11])      {         Shrink = FULL_TO_SHRINK(F[11]);         if ((F[11] &= TblComplexMask[Shrink]) == 0)            return false;         CompF[11] = F[11];         int Column = FULL_TO_COLUMN(F[11]);         int C1 = Column | FULL_TO_COLUMN(F[9]);         int C2 = Column | FULL_TO_COLUMN(F[10]);         F[9] &= TblMaskSingle[Column] & TblMaskDouble[C2];         F[10] &= TblMaskSingle[Column] & TblMaskDouble[C1];         if (TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]] != U[11])         {            U[11] |= TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]];            int S = ~(F[11] & TblColumnMask[U[11]]);            AN(F[2], S); AN(F[5], S); AN(F[8], S); AN(F[14], S); AN(F[17], S); AN(F[20], S); AN(F[23], S); AN(F[26], S);          }      }      if (CompF[12] != F[12])      {         Shrink = FULL_TO_SHRINK(F[12]);         if ((F[12] &= TblComplexMask[Shrink]) == 0)            return false;         CompF[12] = F[12];         int Column = FULL_TO_COLUMN(F[12]);         int C1 = Column | FULL_TO_COLUMN(F[13]);         int C2 = Column | FULL_TO_COLUMN(F[14]);         F[13] &= TblMaskSingle[Column] & TblMaskDouble[C2];         F[14] &= TblMaskSingle[Column] & TblMaskDouble[C1];         if (TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]] != U[12])         {            U[12] |= TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]];            int S = ~(F[12] & TblColumnMask[U[12]]);            AN(F[0], S); AN(F[3], S); AN(F[6], S); AN(F[9], S); AN(F[15], S); AN(F[18], S); AN(F[21], S); AN(F[24], S);          }      }      if (CompF[13] != F[13])      {         Shrink = FULL_TO_SHRINK(F[13]);         if ((F[13] &= TblComplexMask[Shrink]) == 0)            return false;         CompF[13] = F[13];         int Column = FULL_TO_COLUMN(F[13]);         int C1 = Column | FULL_TO_COLUMN(F[12]);         int C2 = Column | FULL_TO_COLUMN(F[14]);         F[12] &= TblMaskSingle[Column] & TblMaskDouble[C2];         F[14] &= TblMaskSingle[Column] & TblMaskDouble[C1];         if (TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]] != U[13])         {            U[13] |= TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]];            int S = ~(F[13] & TblColumnMask[U[13]]);            AN(F[1], S); AN(F[4], S); AN(F[7], S); AN(F[10], S); AN(F[16], S); AN(F[19], S); AN(F[22], S); AN(F[25], S);          }      }      if (CompF[14] != F[14])      {         Shrink = FULL_TO_SHRINK(F[14]);         if ((F[14] &= TblComplexMask[Shrink]) == 0)            return false;         CompF[14] = F[14];         int Column = FULL_TO_COLUMN(F[14]);         int C1 = Column | FULL_TO_COLUMN(F[12]);         int C2 = Column | FULL_TO_COLUMN(F[13]);         F[12] &= TblMaskSingle[Column] & TblMaskDouble[C2];         F[13] &= TblMaskSingle[Column] & TblMaskDouble[C1];         if (TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]] != U[14])         {            U[14] |= TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]];            int S = ~(F[14] & TblColumnMask[U[14]]);            AN(F[2], S); AN(F[5], S); AN(F[8], S); AN(F[11], S); AN(F[17], S); AN(F[20], S); AN(F[23], S); AN(F[26], S);          }      }      if (CompF[15] != F[15])      {         Shrink = FULL_TO_SHRINK(F[15]);         if ((F[15] &= TblComplexMask[Shrink]) == 0)            return false;         CompF[15] = F[15];         int Column = FULL_TO_COLUMN(F[15]);         int C1 = Column | FULL_TO_COLUMN(F[16]);         int C2 = Column | FULL_TO_COLUMN(F[17]);         F[16] &= TblMaskSingle[Column] & TblMaskDouble[C2];         F[17] &= TblMaskSingle[Column] & TblMaskDouble[C1];         if (TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]] != U[15])         {            U[15] |= TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]];            int S = ~(F[15] & TblColumnMask[U[15]]);            AN(F[0], S); AN(F[3], S); AN(F[6], S); AN(F[9], S); AN(F[12], S); AN(F[18], S); AN(F[21], S); AN(F[24], S);          }      }      if (CompF[16] != F[16])      {         Shrink = FULL_TO_SHRINK(F[16]);         if ((F[16] &= TblComplexMask[Shrink]) == 0)            return false;         CompF[16] = F[16];         int Column = FULL_TO_COLUMN(F[16]);         int C1 = Column | FULL_TO_COLUMN(F[15]);         int C2 = Column | FULL_TO_COLUMN(F[17]);         F[15] &= TblMaskSingle[Column] & TblMaskDouble[C2];         F[17] &= TblMaskSingle[Column] & TblMaskDouble[C1];         if (TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]] != U[16])         {            U[16] |= TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]];            int S = ~(F[16] & TblColumnMask[U[16]]);            AN(F[1], S); AN(F[4], S); AN(F[7], S); AN(F[10], S); AN(F[13], S); AN(F[19], S); AN(F[22], S); AN(F[25], S);          }      }      if (CompF[17] != F[17])      {         Shrink = FULL_TO_SHRINK(F[17]);         if ((F[17] &= TblComplexMask[Shrink]) == 0)            return false;         CompF[17] = F[17];         int Column = FULL_TO_COLUMN(F[17]);         int C1 = Column | FULL_TO_COLUMN(F[15]);         int C2 = Column | FULL_TO_COLUMN(F[16]);         F[15] &= TblMaskSingle[Column] & TblMaskDouble[C2];         F[16] &= TblMaskSingle[Column] & TblMaskDouble[C1];         if (TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]] != U[17])         {            U[17] |= TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]];            int S = ~(F[17] & TblColumnMask[U[17]]);            AN(F[2], S); AN(F[5], S); AN(F[8], S); AN(F[11], S); AN(F[14], S); AN(F[20], S); AN(F[23], S); AN(F[26], S);          }      }      if (CompF[18] != F[18])      {         Shrink = FULL_TO_SHRINK(F[18]);         if ((F[18] &= TblComplexMask[Shrink]) == 0)            return false;         CompF[18] = F[18];         int Column = FULL_TO_COLUMN(F[18]);         int C1 = Column | FULL_TO_COLUMN(F[19]);         int C2 = Column | FULL_TO_COLUMN(F[20]);         F[19] &= TblMaskSingle[Column] & TblMaskDouble[C2];         F[20] &= TblMaskSingle[Column] & TblMaskDouble[C1];         if (TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]] != U[18])         {            U[18] |= TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]];            int S = ~(F[18] & TblColumnMask[U[18]]);            AN(F[0], S); AN(F[3], S); AN(F[6], S); AN(F[9], S); AN(F[12], S); AN(F[15], S); AN(F[21], S); AN(F[24], S);          }      }      if (CompF[19] != F[19])      {         Shrink = FULL_TO_SHRINK(F[19]);         if ((F[19] &= TblComplexMask[Shrink]) == 0)            return false;         CompF[19] = F[19];         int Column = FULL_TO_COLUMN(F[19]);         int C1 = Column | FULL_TO_COLUMN(F[18]);         int C2 = Column | FULL_TO_COLUMN(F[20]);         F[18] &= TblMaskSingle[Column] & TblMaskDouble[C2];         F[20] &= TblMaskSingle[Column] & TblMaskDouble[C1];         if (TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]] != U[19])         {            U[19] |= TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]];            int S = ~(F[19] & TblColumnMask[U[19]]);            AN(F[1], S); AN(F[4], S); AN(F[7], S); AN(F[10], S); AN(F[13], S); AN(F[16], S); AN(F[22], S); AN(F[25], S);          }      }      if (CompF[20] != F[20])      {         Shrink = FULL_TO_SHRINK(F[20]);         if ((F[20] &= TblComplexMask[Shrink]) == 0)            return false;         CompF[20] = F[20];         int Column = FULL_TO_COLUMN(F[20]);         int C1 = Column | FULL_TO_COLUMN(F[18]);         int C2 = Column | FULL_TO_COLUMN(F[19]);         F[18] &= TblMaskSingle[Column] & TblMaskDouble[C2];         F[19] &= TblMaskSingle[Column] & TblMaskDouble[C1];         if (TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]] != U[20])         {            U[20] |= TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]];            int S = ~(F[20] & TblColumnMask[U[20]]);            AN(F[2], S); AN(F[5], S); AN(F[8], S); AN(F[11], S); AN(F[14], S); AN(F[17], S); AN(F[23], S); AN(F[26], S);          }      }      if (CompF[21] != F[21])      {         Shrink = FULL_TO_SHRINK(F[21]);         if ((F[21] &= TblComplexMask[Shrink]) == 0)            return false;         CompF[21] = F[21];         int Column = FULL_TO_COLUMN(F[21]);         int C1 = Column | FULL_TO_COLUMN(F[22]);         int C2 = Column | FULL_TO_COLUMN(F[23]);         F[22] &= TblMaskSingle[Column] & TblMaskDouble[C2];         F[23] &= TblMaskSingle[Column] & TblMaskDouble[C1];         if (TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]] != U[21])         {            U[21] |= TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]];            int S = ~(F[21] & TblColumnMask[U[21]]);            AN(F[0], S); AN(F[3], S); AN(F[6], S); AN(F[9], S); AN(F[12], S); AN(F[15], S); AN(F[18], S); AN(F[24], S);          }      }      if (CompF[22] != F[22])      {         Shrink = FULL_TO_SHRINK(F[22]);         if ((F[22] &= TblComplexMask[Shrink]) == 0)            return false;         CompF[22] = F[22];         int Column = FULL_TO_COLUMN(F[22]);         int C1 = Column | FULL_TO_COLUMN(F[21]);         int C2 = Column | FULL_TO_COLUMN(F[23]);         F[21] &= TblMaskSingle[Column] & TblMaskDouble[C2];         F[23] &= TblMaskSingle[Column] & TblMaskDouble[C1];         if (TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]] != U[22])         {            U[22] |= TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]];            int S = ~(F[22] & TblColumnMask[U[22]]);            AN(F[1], S); AN(F[4], S); AN(F[7], S); AN(F[10], S); AN(F[13], S); AN(F[16], S); AN(F[19], S); AN(F[25], S);          }      }      if (CompF[23] != F[23])      {         Shrink = FULL_TO_SHRINK(F[23]);         if ((F[23] &= TblComplexMask[Shrink]) == 0)            return false;         CompF[23] = F[23];         int Column = FULL_TO_COLUMN(F[23]);         int C1 = Column | FULL_TO_COLUMN(F[21]);         int C2 = Column | FULL_TO_COLUMN(F[22]);         F[21] &= TblMaskSingle[Column] & TblMaskDouble[C2];         F[22] &= TblMaskSingle[Column] & TblMaskDouble[C1];         if (TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]] != U[23])         {            U[23] |= TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]];            int S = ~(F[23] & TblColumnMask[U[23]]);            AN(F[2], S); AN(F[5], S); AN(F[8], S); AN(F[11], S); AN(F[14], S); AN(F[17], S); AN(F[20], S); AN(F[26], S);          }      }      if (CompF[24] != F[24])      {         Shrink = FULL_TO_SHRINK(F[24]);         if ((F[24] &= TblComplexMask[Shrink]) == 0)            return false;         CompF[24] = F[24];         int Column = FULL_TO_COLUMN(F[24]);         int C1 = Column | FULL_TO_COLUMN(F[25]);         int C2 = Column | FULL_TO_COLUMN(F[26]);         F[25] &= TblMaskSingle[Column] & TblMaskDouble[C2];         F[26] &= TblMaskSingle[Column] & TblMaskDouble[C1];         if (TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]] != U[24])         {            U[24] |= TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]];            int S = ~(F[24] & TblColumnMask[U[24]]);            AN(F[0], S); AN(F[3], S); AN(F[6], S); AN(F[9], S); AN(F[12], S); AN(F[15], S); AN(F[18], S); AN(F[21], S);          }      }      if (CompF[25] != F[25])      {         Shrink = FULL_TO_SHRINK(F[25]);         if ((F[25] &= TblComplexMask[Shrink]) == 0)            return false;         CompF[25] = F[25];         int Column = FULL_TO_COLUMN(F[25]);         int C1 = Column | FULL_TO_COLUMN(F[24]);         int C2 = Column | FULL_TO_COLUMN(F[26]);         F[24] &= TblMaskSingle[Column] & TblMaskDouble[C2];         F[26] &= TblMaskSingle[Column] & TblMaskDouble[C1];         if (TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]] != U[25])         {            U[25] |= TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]];            int S = ~(F[25] & TblColumnMask[U[25]]);            AN(F[1], S); AN(F[4], S); AN(F[7], S); AN(F[10], S); AN(F[13], S); AN(F[16], S); AN(F[19], S); AN(F[22], S);          }      }      if (CompF[26] != F[26])      {         Shrink = FULL_TO_SHRINK(F[26]);         if ((F[26] &= TblComplexMask[Shrink]) == 0)            return false;         CompF[26] = F[26];         int Column = FULL_TO_COLUMN(F[26]);         int C1 = Column | FULL_TO_COLUMN(F[24]);         int C2 = Column | FULL_TO_COLUMN(F[25]);         F[24] &= TblMaskSingle[Column] & TblMaskDouble[C2];         F[25] &= TblMaskSingle[Column] & TblMaskDouble[C1];         if (TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]] != U[26])         {            U[26] |= TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]];            int S = ~(F[26] & TblColumnMask[U[26]]);            AN(F[2], S); AN(F[5], S); AN(F[8], S); AN(F[11], S); AN(F[14], S); AN(F[17], S); AN(F[20], S); AN(F[23], S);          }      }   }   return true;}`
zhouyundong_2012

Posts: 144
Joined: 10 February 2012

### Re: 12us Solver(2.8G CPU, TestCase:17Sodoku)

Code: Select all
`void                GenerateSixteenClues();int PalaceGrid[9][9] = {   {0, 1, 2, 9, 10, 11, 18, 19, 20 },   {3, 4, 5, 12, 13, 14, 21, 22, 23 },   {6, 7, 8, 15, 16, 17, 24, 25, 26 },   {27, 28, 29, 36, 37, 38, 45, 46, 47 },   {30, 31, 32, 39, 40, 41, 48, 49, 50 },   {33, 34, 35, 42, 43, 44, 51, 52, 53 },   {54, 55, 56, 63, 64, 65, 72, 73, 74 },   {57, 58, 59, 66, 67, 68, 75, 76, 77 },   {60, 61, 62, 69, 70, 71, 78, 79, 80 },};void WriteFile(){   char str[1024] = { '\0' };   FILE *fp = fopen("16.txt", "w+");   for (int i = 0; i < 81; i++)      sprintf(str, "%s%c", str, Board[i]);   fputs(str, fp);   fclose(fp);}void GenerateSixteenClues(){   memset(Board, '0', sizeof(Board));   for (int X0 = 0; X0 < 9; X0++)   {      Board[PalaceGrid[0][X0]] = '1';      for (int X1 = 3; X1 < 9; X1++)      {         Board[PalaceGrid[1][X1]] = '2';         for (int X2 = 6; X2 < 9; X2++)         {            Board[PalaceGrid[2][X2]] = '3';            for (int X3 = 0; X3 < 9; X3++)            {               printf("X3 = %d\n", X3);               Board[PalaceGrid[3][X3]] = '4';               for (int X4 = 0; X4 < 9; X4++)               {                  printf("X4 = %d\n", X4);                  Board[PalaceGrid[4][X4]] = '5';                  for (int X5 = 0; X5 < 9; X5++)                  {                     printf("X5 = %d\n", X5);                     Board[PalaceGrid[5][X5]] = '6';                     for (int X6 = 0; X6 < 9; X6++)                     {                        printf("X6 = %d\n", X6);                        Board[PalaceGrid[6][X6]] = '7';                        for (int X7 = 0; X7 < 9; X7++)                        {                           printf("X7 = %d\n", X7);                           Board[PalaceGrid[7][X7]] = '8';                           for (int X8 = 0; X8 < 9; X8++)                           {                              printf("X8 = %d\n", X8);                              Board[PalaceGrid[8][X8]] = '9';                              for (int Y0 = 0; Y0 < 9; Y0++)                              {                                 if (Board[PalaceGrid[4][Y0]] != '0')                                    continue;                                 Board[PalaceGrid[4][Y0]] = '1';                                 for (int Y1 = 0; Y1 < 9; Y1++)                                 {                                    if (Board[PalaceGrid[5][Y1]] != '0')                                       continue;                                    Board[PalaceGrid[5][Y1]] = '2';                                    for (int Y2 = 0; Y2 < 9; Y2++)                                    {                                       if (Board[PalaceGrid[3][Y2]] != '0')                                          continue;                                       Board[PalaceGrid[3][Y2]] = '3';                                       for (int Y3 = 0; Y3 < 9; Y3++)                                       {                                          if (Board[PalaceGrid[7][Y3]] != '0')                                             continue;                                          Board[PalaceGrid[7][Y3]] = '4';                                          for (int Y4 = 0; Y4 < 9; Y4++)                                          {                                             if (Board[PalaceGrid[8][Y4]] != '0')                                                continue;                                             Board[PalaceGrid[8][Y4]] = '5';                                             for (int Y5 = 0; Y5 < 9; Y5++)                                             {                                                if (Board[PalaceGrid[8][Y5]] != '0')                                                   continue;                                                Board[PalaceGrid[8][Y5]] = '1';                                                for (int Y6 = 0; Y6 < 9; Y6++)                                                {                                                   if (Board[PalaceGrid[6][Y6]] != '0')                                                      continue;                                                   Board[PalaceGrid[6][Y6]] = '2';                                                   InitSodoku();                                                   if (Calculate() == UniqAnswer)                                                   {                                                      WriteFile();                                                      return;                                                   }                                                   Board[PalaceGrid[6][Y6]] = '0';                                                }                                                Board[PalaceGrid[8][Y5]] = '0';                                             }                                             Board[PalaceGrid[8][Y4]] = '0';                                          }                                          Board[PalaceGrid[7][Y3]] = '0';                                       }                                       Board[PalaceGrid[3][Y2]] = '0';                                    }                                    Board[PalaceGrid[5][Y1]] = '0';                                 }                                 Board[PalaceGrid[4][Y0]] = '0';                              }                              Board[PalaceGrid[8][X8]] = '0';                           }                           Board[PalaceGrid[7][X7]] = '0';                        }                        Board[PalaceGrid[6][X6]] = '0';                     }                     Board[PalaceGrid[5][X5]] = '0';                  }                  Board[PalaceGrid[4][X4]] = '0';               }               Board[PalaceGrid[3][X3]] = '0';            }            Board[PalaceGrid[2][X2]] = '0';         }         Board[PalaceGrid[1][X1]] = '0';      }      Board[PalaceGrid[0][X0]] = '0';   }}`
zhouyundong_2012

Posts: 144
Joined: 10 February 2012

### Re: 12us Solver(2.8G CPU, TestCase:17Sodoku)

I have found a 16-Clues sudoku.
zhouyundong_2012

Posts: 144
Joined: 10 February 2012

### Re: 12us Solver(2.8G CPU, TestCase:17Sodoku)

zhouyundong_2012 wrote:I have found a 16-Clues sudoku.

April fool ... not!
ronk
2012 Supporter

Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

### Re: 12us Solver(2.8G CPU, TestCase:17Sodoku)

Update in April 8: It seems nothing to speed up except initialize and guess. 5% improved(17 sudoku). So it works in 2.8G CPU: 3.97us average 17sudoku.
Code: Select all
`#ifndef __sd_h__#define __sd_h__typedef unsigned char        byte;#define TotalBoard          50000 //Total Games//Answer Attribute#define NoAnswer          0#define UniqAnswer          1#define MoreAnswer          2//High, Middle, Low 9 bit of a 27-bit number#define HIGH_9_BIT(v)       ((v) >> 18)#define MID_9_BIT(v)       (((v) >> 9) & 0x1FF)#define LOW_9_BIT(v)       ((v) & 0x1FF)#define HML_9_BIT(v, l)       ((v) >> TblMult9[l] & 0x1FF)#define FULL_TO_COLUMN(v)    (((v) | ((v) >> 9) | ((v) >> 18)) & 0x1FF) //Full Mask(27-bit) to 9 bit#define FULL_TO_SHRINK(v)    ((TblShrinkMask[(v) >> 15] << 5) | TblShrinkMask[(v) & 0x7FFF]) //000 to 0, else to 1#define BIT_SET_27          0x07FFFFFF#define AN(v, n)          (v) &= (n)struct CGame {  public:   int             F[27]; //27-bit Full Mask   int             U[27]; //3-bit Unique in Row   int             Block; //The Block Number of guess [0, 27)   int             Line; //The Line Number of guess [0, 3)   int             Mask; //The 9-bit Mask of guess   int             Left; //The 9-bit Left Mask of guess};//Common Tableextern int             TblMult3[81];extern int             TblDivide3[81];extern int             TblRmder3[81];extern int             TblMult9[9];//Basis Tableextern int             TblCombineMask[512];extern int             TblTailZero[512];extern int             TblNumberOne[512];extern int             TblAnother1[27];extern int             TblAnother2[27];extern int             TblShiftLeft[27];//Table of Decompose Boardextern int             TblBoard_Block[81];extern int             TblBoard_BlockMask[81];extern int             TblBoard_GridUniq[81];//Table of Initialextern int             TblSelfMask[81];extern int             TblOtherMask[81];//Complex Friend Methodextern int             TblMaskSingle[512];extern int             TblMaskDouble[512];//Other Tableextern int             TblColumnMask[8];extern bool             TblUniqFlag[8];//Complex Methodextern byte             TblShrinkMask[32768];extern int             TblComplexMask[512];extern int             TblColumnSingle[512];extern int             TblShrinkSingle[512];extern void             CreateTable();#endif`
zhouyundong_2012

Posts: 144
Joined: 10 February 2012

PreviousNext