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

Programs which generate, solve, and analyze Sudoku puzzles

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

thanks, Afmob,
Two bugs have been fixed.
000000000000000000000000000000000000000000000000000000000000000000000000000000000
111111111111111111111111111111111111111111111111111111111111111111111111111111111
zhouyundong_2012

Posts: 144
Joined: 10 February 2012

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

After bugfix: I hope it is the last version. it doesn't affect speed. just G[33] to G[50] and CompF should be initialized to -1
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 Palace    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_Palace[81];extern 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             TblPalaceMask[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_Palace[81];int                   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                   TblPalaceMask[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_Palace[i] = TblMult3[i / 27] + TblDivide3[i % 9];      TblBoard_Block[i] = i / 27;      TblBoard_BlockMask[i] = 1 << i % 27;      TblBoard_GridUniq[i] = 1 << TblBoard_Palace[i] % 3;   }}void CreateTblSelfMask(){   int Mask[3] = { 0x7E3F1F8, 0x71F8FC7, 0x0FC7E3F };   int Row[3] = { 0x7FFFE00, 0x7FC01FF, 0x3FFFF };   for (int i = 0; i < 81; i++)   {      int Palace = TblBoard_Palace[i % 27];      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 CreateTblPalaceMask(){   memset(TblPalaceMask, 0, sizeof(TblPalaceMask));   for (int i = 0; i < 8; i++)   {      for (int j = 0; j < 3; j++)      {         if (i & (1 << j))            TblPalaceMask[i] |= 0x1C0E07 << TblMult3[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(){   for (int i = 0; i < 512; i++)   {      TblColumnSingle[i] = 7;      int v = i >> 6; //High 3 bit      if (v != 4 && v != 2 && v != 1)         TblColumnSingle[i] &= 0x3;      v = i >> 3 & 0x7; //Middle 3 bit      if (v != 4 && v != 2 && v != 1)         TblColumnSingle[i] &= 0x5;      v = i & 0x7; //Low 3 bit      if (v != 4 && v != 2 && v != 1)         TblColumnSingle[i] &= 0x6;   }   for (int i = 0; i < 512; i++)   {      TblShrinkSingle[i] = 7;      int j = i & FULL_TO_SHRINK(TblComplexMask[i]);      int v = j & 0x49;      if (v != 1 && v != 8 && v != 64)         TblShrinkSingle[i] &= 0x6;      v = j & 0x92;      if (v != 2 && v != 16 && v != 128)         TblShrinkSingle[i] &= 0x5;      v = j & 0x124;      if (v != 4 && v != 32 && v != 256)         TblShrinkSingle[i] &= 0x3;   }}void CreateTable(){   CreateTblCommon();   CreateTblBasis();   CreateTblBoard();   CreateTblSelfMask();   CreateTblOtherMask();   CreateTblMaskSingle();   CreateTblMaskDouble();   CreateTblPalaceMask();   CreateTblUniqFlag();   CreateShrinkMask();   CreateComplexMask();   CreateTblColumnSingle();}`
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 Palaceint                   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 = 26; B >= 0; --B)   {      BlockMask[B] = U[B] = 0;      CompF[B] = F[B] = -1;   }   //Get Full Mask   for (int i = 80; i >= 0; --i)   {      if (Board[i] == '0')         continue;      int B = TblMult3[Board[i] - '1'] + TblBoard_Block[i];      //Get BlockMask and Sum of BlockMask      BlockMask[B] |= TblBoard_BlockMask[i];      BlockMaskSum[TblBoard_Block[i]] |= BlockMask[B];      //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 = 26; B >= 0; --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++)      {         int NumberOne = TblNumberOne[HML_9_BIT(F[i], j)];         if (NumberOne > 1 && 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 = 26; B >= 0; --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 = 26; B >= 0; --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\tint Single = (TblShrinkSingle[Shrink] & TblColumnSingle[Column]) ^ U[%d];\n", i);      fputs(str, fp);      fputs("\t\t\tif (Single)\n", fp);      fputs("\t\t\t{\n", fp);      sprintf(str, "\t\t\t\tU[%d] |= Single;\n", i);      fputs(str, fp);      //Friend Block      sprintf(str, "\t\t\t\tint S = F[%d] & TblPalaceMask[Single];\n", 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)

WOW! Now 30% faster than JSolve on top1465.

JasonLion
2017 Supporter

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

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

Greetings all,

First, sorry if I am annoying, I did try to share all my code.

Second, though I am in still semi-retirement due to my job taking too many hours a week, but I wanted to see Zhou's latest program. If Jason says it is 30% faster, than that is quite a feat. I have not had time to test it myself yet, maybe over the weekend.

briturner
brit

Posts: 1
Joined: 15 March 2012

Thank you for fixing those bugs. I've also tested your solver against the gen500k test set and it worked.

Of course, if one wants to use it for more general problems some modifications (I mentioned them before) have to be made and the cumbersome compiling procedure with Update.c should be removed.
Afmob

Posts: 130
Joined: 28 June 2011

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

sorry, I don't know your means.
zhouyundong_2012

Posts: 144
Joined: 10 February 2012

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

If you change code in Update.c, recompile is the better way than rewrite each place.
and if you change other code, you needn't open __ProgramWritter.
For example, you want write
Code: Select all
`   for (int i = 0; i < TestCaseNumber; i++)   {      memcpy(Board, AllBoard[i], 81);      InitSodoku();      if ((Answer = Calculate()) != UniqAnswer)         continue;   }`

you needn't redo the 3 steps.
zhouyundong_2012

Posts: 144
Joined: 10 February 2012

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

1 where to download top1465? you can send to my e-mail lao_zhouxi9@163.com 3Q
2 is top1465 the most difficult?
zhouyundong_2012

Posts: 144
Joined: 10 February 2012

Usually the solver is just a small (but important) part of a larger program where the solver is just one tool you use. So you won't rewrite the solver that often. For example, I've been using JSolve for over 2 years and I probably changed it only 4 or 5 times. It can be easily modified to solve Sudokus of abitrary size, it's easy to compile and works on Windows and Linux.

Your solver is fast but currently it's just written too specifically for a certain problem, is tedious to compile and it works only for a fixed number of Sudokus but usually you want to solve millions, billions or trillions of Sudokus but that problem shouldn't be too hard to fix.
Afmob

Posts: 130
Joined: 28 June 2011

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

I find a new way to Guess, I think it will be more fast for difficult case, but some slower for easy case.

I think hard to let U means Uniq in a row not a 3*3grid. I at last find a way.
zhouyundong_2012

Posts: 144
Joined: 10 February 2012

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

Yes ,that is not hard to fix. But I haven't time to do it for I am thinking how to Guess effeciently. And I think I got it now.
zhouyundong_2012

Posts: 144
Joined: 10 February 2012

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

I have also made a visible software,it includes Killer, GT/LT, Extra, and Mix of them.
But I don't know how to post it here.
zhouyundong_2012

Posts: 144
Joined: 10 February 2012

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

I am happy to get this conclusion:

111 110 000
000 000 010
011 001 000

//Shrink
011 100 011 => 000 100 000 (TblShrinkSingle)
//Column
111 111 010 => 100 100 100 (TblColumnSingle)

And of them
===> 000 100 000

000 100 000 => 010 (TblShrinkLow)

010 means the second Row is Uniq
zhouyundong_2012

Posts: 144
Joined: 10 February 2012

PreviousNext