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

Programs which generate, solve, and analyze Sudoku puzzles

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

Postby zhouyundong_2012 » Fri Feb 17, 2012 11:16 am

I made another improvement. it will improve 10% for 17sodoku, and 3% for top50000, and ? for 2465.
zhouyundong_2012
 
Posts: 138
Joined: 10 February 2012

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

Postby zhouyundong_2012 » Fri Feb 17, 2012 4:30 pm

Code: Select all
#ifndef __sd_h__
#define __sd_h__

typedef unsigned char       byte;
typedef unsigned short       word;

#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_PALACE(v)    ((v) | ((v) >> 6) | ((v) >> 12)) & 0x1FF //Full Mask(27-bit) to 9 bit, x-- y-- z--

#define BIT_SET_27          0x07FFFFFF

#define AN(v, n)          (v) &= ~(n)

struct CGame {
  public:
   int           Finish; //27-bit Finish Bitmap
   int             F[27]; //27-bit Full Mask
   byte          U[27]; //3-bit Unique in Palace
   byte          Block; //The Block Number of guess [0, 27)
   byte          Line; //The Line Number of guess [0, 3)
   word          Mask; //The 9-bit Mask of guess
   word          Left; //The 9-bit Left Mask of guess
};

//Common Table
extern int             TblMult3[81];
extern int             TblDivide3[81];
extern int             TblRmder3[81];
extern int             TblMult9[9];
//Basis Table
extern 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 Board
extern int             TblBoard_Palace[81];
extern int             TblBoard_Block[81];
extern int             TblBoard_BlockMask[81];
extern int             TblBoard_GridUniq[81];
//Table of Initial
extern int             TblSelfMask[81];
extern int             TblOtherMask[81];
//Single Row Method
extern int             TblSingleRow[12];
extern int             TblRowNumber[512];
//Single Column Method
extern int             TblMaskSingle[512];
//Double Column Method
extern int             TblMaskDouble[512];
//Confirm Row Method
extern int             TblConfirmRow[12];
//Other Table
extern int             TblPalaceMask[3];
extern int             TblStrange[27];
extern int             TblChangeMask[27];
extern bool             TblUniqFlag[8];


extern void             CreateTable();

#endif
zhouyundong_2012
 
Posts: 138
Joined: 10 February 2012

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

Postby zhouyundong_2012 » Fri Feb 17, 2012 4:30 pm

Code: Select all
#include "StdAfx.h"
#include "sd.h"

//Common Table
int                   TblMult3[81];
int                   TblDivide3[81];
int                   TblRmder3[81];
int                   TblMult9[9];
//Basis Table
int                   TblCombineMask[512];
int                   TblTailZero[512];
int                   TblNumberOne[512];
int                   TblAnother1[27];
int                   TblAnother2[27];
int                   TblShiftLeft[27];
//Table of Decompose Board
int                   TblBoard_Palace[81];
int                   TblBoard_Block[81];
int                   TblBoard_BlockMask[81];
int                   TblBoard_GridUniq[81];
//Table of Initial
int                   TblSelfMask[81];
int                   TblOtherMask[81];
//Single Row Method
int                   TblSingleRow[12];
int                   TblRowNumber[512];
//Single Column Method
int                   TblMaskSingle[512];
//Double Column Method
int                   TblMaskDouble[512];
//Confirm Row Method
int                   TblConfirmRow[12];
//Other Table
int                   TblPalaceMask[3];
int                   TblStrange[27];
int                   TblChangeMask[27];
bool                TblUniqFlag[8];

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 CreateTblSingleRow()
{
   memset(TblRowNumber, 0, sizeof(TblRowNumber)); //0 if Not Single Row
   for (int i = 0; i < 512; i++)
   {
      if ((i & 0x1F8) == 0 && i & 0x7)
         TblRowNumber[i] = 3;
      if ((i & 0x1C7) == 0 && i & 0x38)
         TblRowNumber[i] = 6;
      if ((i & 0x3F) == 0 && i & 0x1C0)
         TblRowNumber[i] = 9;
   }
   int Mask[3] = { 0x1F8, 0x1C7, 0x3F };
   for (int i = 0; i < 3; i++) //Palace Number
   {
      TblSingleRow[i] = BIT_SET_27;
      for (int j = 1; j <= 3; j++) //Result of Mask
      {
         TblSingleRow[i + j * 3] = (Mask[i] << (j - 1) * 9) ^ BIT_SET_27;
      }
   }
}

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 CreateTblConfirmRow()
{
   int Mask[3] = { 0x7038000, 0x70001C0, 0x381C0 };
   for (int i = 1; i <= 3; i++) //Result of Mask
   {
      TblConfirmRow[i - 1] = BIT_SET_27;
      for (int j = 0; j < 3; j++) //Row Number
      {
         TblConfirmRow[i * 3 + j] = (Mask[j] >> (3 - i) * 3) ^ BIT_SET_27;
      }
   }
}

void CreateTblPalaceMask()
{
   memset(TblPalaceMask, 0, sizeof(TblPalaceMask));
   for (int i = 0; i < 3; i++)
   {
      TblPalaceMask[i] = 0x1C0E07 << TblMult3[i];
   }
}

void CreateTblStrange()
{
   //Count by Palace, Count by Row in Palace
   for (int i = 0; i < 27; i++)
   {
      int Grid = TblMult9[i % 9 / 3] + TblRmder3[i % 9] + TblMult3[i / 9];
      TblStrange[i] = TblSelfMask[Grid];
   }
}

void CreateTblChangeMask()
{
   for (int i = 0; i < 27; i++)
   {
      TblChangeMask[i] = (1 << i) | (1 << TblAnother1[i]) | (1 << TblAnother2[i]);
      for (int j = i % 3; j < 27; j += 3)
         TblChangeMask[i] |= 1 << j;
   }
}

void CreateTblUniqFlag()
{
   memset(TblUniqFlag, 0, sizeof(TblUniqFlag));
   for (int i = 0; i < 8; i++)
   {
      if (TblNumberOne[i] >= 2)
         TblUniqFlag[i] = true;
   }
}

void CreateTable()
{
   CreateTblCommon();
   CreateTblBasis();
   CreateTblBoard();
   CreateTblSelfMask();
   CreateTblOtherMask();
   CreateTblSingleRow();
   CreateTblMaskSingle();
   CreateTblMaskDouble();
   CreateTblConfirmRow();
   CreateTblPalaceMask();
   CreateTblStrange();
   CreateTblChangeMask();
   CreateTblUniqFlag();
}
zhouyundong_2012
 
Posts: 138
Joined: 10 February 2012

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

Postby zhouyundong_2012 » Fri Feb 17, 2012 4:31 pm

Code: Select all
#include "StdAfx.h"
#include <windows.h>
#include "sd.h"

byte                Board[81]; //Board
CGame                G[33]; //Guess Board

byte                Index; //Guess Index
int                   Change; //Change Bitmap
int                   Finish; //27-bit Finish Bitmap
int                   BlockMask[27]; //Block
int                   BlockMaskSum[3]; //Sum of BlockMask
int                   F[27]; //27-bit Full Mask
byte                U[27]; //3-bit Unique in Palace
int                   CompF[27]; //Use for Compare

byte                AllBoard[TotalBoard][81]; //All Boards
int                   TestCaseNumber; //Actual Number of Test Case

bool                Update();
void                Guess();
bool                Rollback();
byte                Calculate();
int                   PosLastBit(int v);

void InitSodoku()
{
   Change = BIT_SET_27;
   Finish = 0;
   Index = 1;
   BlockMaskSum[0] = BlockMaskSum[1] = BlockMaskSum[2] = 0;
   memset(BlockMask, 0, sizeof(BlockMask));
   memset(F, -1, sizeof(F));
   memset(U, 0, sizeof(U));
   //Get Full Mask
   for (int i = 80; i >= 0; --i)
   {
      if (Board[i] == '0')
         continue;

      int V = Board[i] - '1'; //Value
      int B = TblMult3[V] + TblBoard_Block[i]; //Block
      //Get BlockMask and Sum of BlockMask
      BlockMask[B] |= TblBoard_BlockMask[i];
      BlockMaskSum[TblBoard_Block[i]] |= TblBoard_BlockMask[i];
      //Get Full Mask
      F[B] &= TblSelfMask[i];
      F[TblAnother1[B]] &= TblOtherMask[i];
      F[TblAnother2[B]] &= TblOtherMask[i];
      //Get Grid Uniq Bitmap and Finish Bitmap
      if ((U[B] |= TblBoard_GridUniq[i]) == 7)
         Finish |= TblShiftLeft[B];
   }
   for (int B = 26; B >= 0; --B)
      F[B] &= BlockMaskSum[TblRmder3[B]] ^ BlockMask[B] ^ BIT_SET_27;
   //Clear CompF, Save F as the G[0]
   memset(CompF, 0, sizeof(F));
   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[MID_9_BIT(F[i])] == 2)
      {
         G[Index].Line = 1;
         goto FoundLeast;
      }
      if (TblNumberOne[LOW_9_BIT(F[i])] == 2)
      {
         G[Index].Line = 0;
         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:
   word Left = HML_9_BIT(F[G[Index].Block], G[Index].Line);
   word Mask = Left & -Left;
   //Save Data
   G[Index].Finish = Finish;
   G[Index].Mask = Mask;
   G[Index].Left = Left;
   memcpy(G[Index].F, F, sizeof(F));
   memcpy(CompF, F, sizeof(F));
   memcpy(G[Index].U, U, sizeof(U));
   F[G[Index].Block] &= TblSelfMask[TblTailZero[Mask] + TblMult9[G[Index].Line]];

   Change = 1 << G[Index].Block;
   Index++;
}

bool Rollback()
{
   if (Index-- == 1)
      return false;
   //Restore Data
   Finish = G[Index].Finish;
   byte Block = G[Index].Block;
   byte Line = G[Index].Line;
   memcpy(F, G[Index].F, sizeof(F));
   memcpy(CompF, F, sizeof(F));
   memcpy(U, G[Index].U, sizeof(U));

   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;
   Change = TblShiftLeft[Block];
   return true;
}

byte Calculate()
{
   bool FoundAnswer = false;
   while (true)
   {
      if (Update())
      {
         if (Finish != BIT_SET_27)
         {
            Guess();
            continue;
         }
         if (FoundAnswer) //Find Answer
            return MoreAnswer;
         FoundAnswer = true;
      }
      if (!Rollback()) //Backtrack Over
         return FoundAnswer ? UniqAnswer : NoAnswer;
   }
}

bool UpdateByGrid()
{
   int B = 0;
   while (Change &= ~Finish)
   {
      B = Change >> B ? PosLastBit(Change >> B) + B : PosLastBit(Change); //Loop Like Circle
      Change ^= TblShiftLeft[B];
      if (CompF[B] == F[B])
         continue;
LB_P0:   if ((U[B] & 1) == 0)
      {
         int S = F[B] & TblPalaceMask[0];
         if (S == 0)
            return false;

         int TheMask = FULL_TO_PALACE(S);
         if (S & S - 1)
         {
            //Single Row Method
            if (TblRowNumber[TheMask] != 0 && F[B] & ~TblSingleRow[TblRowNumber[TheMask]])
            {
               F[B] &= TblSingleRow[TblRowNumber[TheMask]];
               Change |= TblShiftLeft[B];
            }
            goto LB_P1;
         }
         if ((U[B] |= 1) == 7)
            Finish |= TblShiftLeft[B];
         //Neighbour Block
         F[TblAnother1[B]] &= TblCombineMask[FULL_TO_COLUMN(S)];
         F[TblAnother2[B]] &= TblCombineMask[FULL_TO_COLUMN(S)];
         //Self Block
         F[B] &= TblStrange[TblTailZero[TheMask]];
         //Friend Block
         int OldMask = F[B];
         switch (TblRmder3[B])
         {
         case 0:
            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); AN(F[24], S);
            break;
         case 1:
            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); AN(F[25], S);
            break;
         case 2:
            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); AN(F[26], S);
            break;
         }
         F[B] = OldMask;
         Change |= TblChangeMask[B];
      }
LB_P1:   if ((U[B] & 2) == 0)
      {
         int S = F[B] & TblPalaceMask[1];
         if (S == 0)
            return false;

         int TheMask = FULL_TO_PALACE(S >> 3);
         if (S & S - 1)
         {
            //Single Row Method
            if (TblRowNumber[TheMask] != 0 && F[B] & ~TblSingleRow[1 + TblRowNumber[TheMask]])
            {
               F[B] &= TblSingleRow[1 + TblRowNumber[TheMask]];
               Change |= TblShiftLeft[B];
            }
            goto LB_P2;
         }
         if ((U[B] |= 2) == 7)
            Finish |= TblShiftLeft[B];
         //Neighbour Block
         F[TblAnother1[B]] &= TblCombineMask[FULL_TO_COLUMN(S)];
         F[TblAnother2[B]] &= TblCombineMask[FULL_TO_COLUMN(S)];
         //Self Block
         F[B] &= TblStrange[9 + TblTailZero[TheMask]];
         //Friend Block
         int OldMask = F[B];
         switch (TblRmder3[B])
         {
         case 0:
            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); AN(F[24], S);
            break;
         case 1:
            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); AN(F[25], S);
            break;
         case 2:
            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); AN(F[26], S);
            break;
         }
         F[B] = OldMask;
         Change |= TblChangeMask[B];
      }
LB_P2:   if ((U[B] & 4) == 0)
      {
         int S = F[B] & TblPalaceMask[2];
         if (S == 0)
            return false;

         int TheMask = FULL_TO_PALACE(S >> 6);
         if (S & S - 1)
         {
            //Single Row Method
            if (TblRowNumber[TheMask] != 0 && F[B] & ~TblSingleRow[2 + TblRowNumber[TheMask]])
            {
               F[B] &= TblSingleRow[2 + TblRowNumber[TheMask]];
               Change |= TblShiftLeft[B];
               goto LB_P0;
            }
            CompF[B] = F[B];
            continue;
         }
         if ((U[B] |= 4) == 7)
            Finish |= TblShiftLeft[B];
         //Neighbour Block
         F[TblAnother1[B]] &= TblCombineMask[FULL_TO_COLUMN(S)];
         F[TblAnother2[B]] &= TblCombineMask[FULL_TO_COLUMN(S)];
         //Self Block
         F[B] &= TblStrange[18 + TblTailZero[TheMask]];
         //Friend Block
         int OldMask = F[B];
         switch (TblRmder3[B])
         {
         case 0:
            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); AN(F[24], S);
            break;
         case 1:
            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); AN(F[25], S);
            break;
         case 2:
            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); AN(F[26], S);
            break;
         }
         F[B] = OldMask;
         Change |= TblChangeMask[B];
      }
      if ((Change & TblShiftLeft[B]) == 0)
         CompF[B] = F[B];
   }
   return true;
}

bool Update()
{
   //Single Grid Method
   if (!UpdateByGrid())
      return false;
   memcpy(CompF, F, sizeof(F));
   //Single Column Method And Double Column Method
   for (int B = 0; B < 27; B += 3)
   {
      int C0 = FULL_TO_COLUMN(F[B]);
      int C1 = FULL_TO_COLUMN(F[B + 1]);
      int C2 = FULL_TO_COLUMN(F[B + 2]);
      F[B]     &= TblMaskSingle[C1] & TblMaskSingle[C2] & TblMaskDouble[C1 | C2];
      F[B + 1] &= TblMaskSingle[C0] & TblMaskSingle[C2] & TblMaskDouble[C0 | C2];
      F[B + 2] &= TblMaskSingle[C0] & TblMaskSingle[C1] & TblMaskDouble[C0 | C1];
   }
   //Confirm Row Method
   int Mask;
   for (int B = 0; B < 27; B++)
   {
      if (G[Index - 1].F[B] == F[B])
         continue;
      int FullMask = F[B];
      if ((Mask = HIGH_9_BIT(FullMask)) == 0)
         return false;
      F[B] &= TblConfirmRow[TblRowNumber[Mask] + 2];
      if ((Mask = MID_9_BIT(FullMask)) == 0)
         return false;
      F[B] &= TblConfirmRow[TblRowNumber[Mask] + 1];
      if ((Mask = LOW_9_BIT(FullMask)) == 0)
         return false;
      F[B] &= TblConfirmRow[TblRowNumber[Mask]];
   }
   //Get Change by Compare F with CompF
   for (int B = 0; B < 27; B++)
      Change |= (F[B] != CompF[B]) << B;
   //Single Grid Method
   if (!UpdateByGrid())
      return false;

   return true;
}

bool 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();
   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);

   byte 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;
}


/*****************************************************************************
 *
 * This Function get the number of 0 which is at the tail of a 27-bit Number
 *
 *****************************************************************************/
int PosLastBit(int v)
{
   int A = TblTailZero[v & 0x1FF];
   if (A != 9)
      return A; //Low 9 bit

   int B = TblTailZero[v >> 9 & 0x1FF];
   if (B != 9)
      return B + 9; //Middle 9 bit

   return TblTailZero[v >> 18] + 18; //High 9 bit
}
zhouyundong_2012
 
Posts: 138
Joined: 10 February 2012

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

Postby JasonLion » Sat Feb 18, 2012 12:35 am

Thank you for translating the comments to English!
User avatar
JasonLion
2017 Supporter
 
Posts: 621
Joined: 25 October 2007
Location: Silver Spring, MD, USA

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

Postby zhouyundong_2012 » Sat Feb 18, 2012 2:36 am

I am not good at English yet,Is there anybody whill modify and correct the comment?
zhouyundong_2012
 
Posts: 138
Joined: 10 February 2012

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

Postby zhouyundong_2012 » Sun Feb 19, 2012 3:48 pm

Code: Select all
#include "StdAfx.h"
#include <windows.h>
#include "sd.h"

byte                Board[81]; //Board
CGame                G[33]; //Guess Board

byte                Index; //Guess Index
int                   Change; //Change Bitmap
int                   Finish; //27-bit Finish Bitmap
int                   BlockMask[27]; //Block
int                   BlockMaskSum[3]; //Sum of BlockMask
int                   F[27]; //27-bit Full Mask
byte                U[27]; //3-bit Unique in Palace
int                   CompF[27]; //Use for Compare

byte                AllBoard[TotalBoard][81]; //All Boards
int                   TestCaseNumber; //Actual Number of Test Case

bool                Update();
void                Guess();
bool                Rollback();
byte                Calculate();
int                   PosLastBit(int v);

void InitSodoku()
{
   Change = BIT_SET_27;
   Finish = 0;
   Index = 1;
   BlockMaskSum[0] = BlockMaskSum[1] = BlockMaskSum[2] = 0;
   memset(BlockMask, 0, sizeof(BlockMask));
   memset(F, -1, sizeof(F));
   memset(U, 0, sizeof(U));
   //Get Full Mask
   for (int i = 80; i >= 0; --i)
   {
      if (Board[i] == '0')
         continue;

      int V = Board[i] - '1'; //Value
      int B = TblMult3[V] + TblBoard_Block[i]; //Block
      //Get BlockMask and Sum of BlockMask
      BlockMask[B] |= TblBoard_BlockMask[i];
      BlockMaskSum[TblBoard_Block[i]] |= TblBoard_BlockMask[i];
      //Get Full Mask
      F[B] &= TblSelfMask[i];
      F[TblAnother1[B]] &= TblOtherMask[i];
      F[TblAnother2[B]] &= TblOtherMask[i];
      //Get Grid Uniq Bitmap and Finish Bitmap
      if ((U[B] |= TblBoard_GridUniq[i]) == 7)
         Finish |= TblShiftLeft[B];
   }
   for (int B = 26; B >= 0; --B)
      F[B] &= BlockMaskSum[TblRmder3[B]] ^ BlockMask[B] ^ BIT_SET_27;
   //Clear CompF, Save F as the G[0]
   memset(CompF, 0, sizeof(F));
   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[MID_9_BIT(F[i])] == 2)
      {
         G[Index].Line = 1;
         goto FoundLeast;
      }
      if (TblNumberOne[LOW_9_BIT(F[i])] == 2)
      {
         G[Index].Line = 0;
         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:
   word Left = HML_9_BIT(F[G[Index].Block], G[Index].Line);
   word Mask = Left & -Left;
   //Save Data
   G[Index].Finish = Finish;
   G[Index].Mask = Mask;
   G[Index].Left = Left;
   memcpy(G[Index].F, F, sizeof(F));
   memcpy(CompF, F, sizeof(F));
   memcpy(G[Index].U, U, sizeof(U));
   F[G[Index].Block] &= TblSelfMask[TblTailZero[Mask] + TblMult9[G[Index].Line]];

   Change = 1 << G[Index].Block;
   Index++;
}

bool Rollback()
{
   if (Index-- == 1)
      return false;
   //Restore Data
   Finish = G[Index].Finish;
   byte Block = G[Index].Block;
   byte Line = G[Index].Line;
   memcpy(F, G[Index].F, sizeof(F));
   memcpy(CompF, F, sizeof(F));
   memcpy(U, G[Index].U, sizeof(U));

   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;
   Change = TblShiftLeft[Block];
   return true;
}

byte Calculate()
{
   bool FoundAnswer = false;
   while (true)
   {
      if (Update())
      {
         if (Finish != BIT_SET_27)
         {
            Guess();
            continue;
         }
         if (FoundAnswer) //Find Answer
            return MoreAnswer;
         FoundAnswer = true;
      }
      if (!Rollback()) //Backtrack Over
         return FoundAnswer ? UniqAnswer : NoAnswer;
   }
}
int TblColumnMask[10] = {
   0, 0, 0, 0x1FF, 0, 0, 0x1FF << 9, 0, 0, 0x1FF << 18
};

bool UpdateByGrid()
{
   int B = 0;
   while (Change &= ~Finish)
   {
      B = Change >> B ? PosLastBit(Change >> B) + B : PosLastBit(Change); //Loop Like Circle
      Change ^= TblShiftLeft[B];
      if (CompF[B] == F[B])
         continue;
LB_P0:   if ((U[B] & 1) == 0)
      {
         int S = F[B] & TblPalaceMask[0];
         if (S == 0)
            return false;

         int TheMask = FULL_TO_PALACE(S);
         if (S & S - 1)
         {
            //Single Row Method
            if (TblRowNumber[TheMask] != 0 && F[B] & ~TblSingleRow[TblRowNumber[TheMask]])
            {
               F[B] &= TblSingleRow[TblRowNumber[TheMask]];
               Change |= TblShiftLeft[B];
               if (TblNumberOne[TheMask] == 2)
               {
                  int ColumnMask = TblColumnMask[TblRowNumber[TheMask]];
                  for (int j = TblRmder3[B]; j < 27; j += 3)
                  {
                     if (j != B && ((F[j] & TblPalaceMask[0]) == S || (F[j] & ColumnMask) == S))
                     {
                        for (int k = TblRmder3[B]; k < 27; k += 3)
                        {
                           if (k != B && k != j && F[k] & S)
                           {
                              F[k] &= ~S;
                              Change |= TblShiftLeft[k];
                           }
                        }
                        break;
                     }
                  }
               }
            }
            goto LB_P1;
         }
         if ((U[B] |= 1) == 7)
            Finish |= TblShiftLeft[B];
         //Neighbour Block
         F[TblAnother1[B]] &= TblCombineMask[FULL_TO_COLUMN(S)];
         F[TblAnother2[B]] &= TblCombineMask[FULL_TO_COLUMN(S)];
         //Self Block
         F[B] &= TblStrange[TblTailZero[TheMask]];
         //Friend Block
         int OldMask = F[B];
         switch (TblRmder3[B])
         {
         case 0:
            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); AN(F[24], S);
            break;
         case 1:
            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); AN(F[25], S);
            break;
         case 2:
            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); AN(F[26], S);
            break;
         }
         F[B] = OldMask;
         Change |= TblChangeMask[B];
      }
LB_P1:   if ((U[B] & 2) == 0)
      {
         int S = F[B] & TblPalaceMask[1];
         if (S == 0)
            return false;

         int TheMask = FULL_TO_PALACE(S >> 3);
         if (S & S - 1)
         {
            //Single Row Method
            if (TblRowNumber[TheMask] != 0 && F[B] & ~TblSingleRow[1 + TblRowNumber[TheMask]])
            {
               F[B] &= TblSingleRow[1 + TblRowNumber[TheMask]];
               Change |= TblShiftLeft[B];
               if (TblNumberOne[TheMask] == 2)
               {
                  int ColumnMask = TblColumnMask[TblRowNumber[TheMask]];
                  for (int j = TblRmder3[B]; j < 27; j += 3)
                  {
                     if (j != B && ((F[j] & TblPalaceMask[1]) == S || (F[j] & ColumnMask) == S))
                     {
                        for (int k = TblRmder3[B]; k < 27; k += 3)
                        {
                           if (k != B && k != j && F[k] & S)
                           {
                              F[k] &= ~S;
                              Change |= TblShiftLeft[k];
                           }
                        }
                        break;
                     }
                  }
               }
            }
            goto LB_P2;
         }
         if ((U[B] |= 2) == 7)
            Finish |= TblShiftLeft[B];
         //Neighbour Block
         F[TblAnother1[B]] &= TblCombineMask[FULL_TO_COLUMN(S)];
         F[TblAnother2[B]] &= TblCombineMask[FULL_TO_COLUMN(S)];
         //Self Block
         F[B] &= TblStrange[9 + TblTailZero[TheMask]];
         //Friend Block
         int OldMask = F[B];
         switch (TblRmder3[B])
         {
         case 0:
            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); AN(F[24], S);
            break;
         case 1:
            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); AN(F[25], S);
            break;
         case 2:
            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); AN(F[26], S);
            break;
         }
         F[B] = OldMask;
         Change |= TblChangeMask[B];
      }
LB_P2:   if ((U[B] & 4) == 0)
      {
         int S = F[B] & TblPalaceMask[2];
         if (S == 0)
            return false;

         int TheMask = FULL_TO_PALACE(S >> 6);
         if (S & S - 1)
         {
            //Single Row Method
            if (TblRowNumber[TheMask] != 0 && F[B] & ~TblSingleRow[2 + TblRowNumber[TheMask]])
            {
               F[B] &= TblSingleRow[2 + TblRowNumber[TheMask]];
               Change |= TblShiftLeft[B];
               if (TblNumberOne[TheMask] == 2)
               {
                  int ColumnMask = TblColumnMask[TblRowNumber[TheMask]];
                  for (int j = TblRmder3[B]; j < 27; j += 3)
                  {
                     if (j != B && ((F[j] & TblPalaceMask[2]) == S || (F[j] & ColumnMask) == S))
                     {
                        for (int k = TblRmder3[B]; k < 27; k += 3)
                        {
                           if (k != B && k != j && F[k] & S)
                           {
                              F[k] &= ~S;
                              Change |= TblShiftLeft[k];
                           }
                        }
                        break;
                     }
                  }
               }
               goto LB_P0;
            }
            CompF[B] = F[B];
            continue;
         }
         if ((U[B] |= 4) == 7)
            Finish |= TblShiftLeft[B];
         //Neighbour Block
         F[TblAnother1[B]] &= TblCombineMask[FULL_TO_COLUMN(S)];
         F[TblAnother2[B]] &= TblCombineMask[FULL_TO_COLUMN(S)];
         //Self Block
         F[B] &= TblStrange[18 + TblTailZero[TheMask]];
         //Friend Block
         int OldMask = F[B];
         switch (TblRmder3[B])
         {
         case 0:
            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); AN(F[24], S);
            break;
         case 1:
            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); AN(F[25], S);
            break;
         case 2:
            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); AN(F[26], S);
            break;
         }
         F[B] = OldMask;
         Change |= TblChangeMask[B];
      }
      if ((Change & TblShiftLeft[B]) == 0)
         CompF[B] = F[B];
   }
   return true;
}

bool Update()
{
   //Single Grid Method
   if (!UpdateByGrid())
      return false;
   memcpy(CompF, F, sizeof(F));
   //Single Column Method And Double Column Method
   for (int B = 0; B < 27; B += 3)
   {
      int C0 = FULL_TO_COLUMN(F[B]);
      int C1 = FULL_TO_COLUMN(F[B + 1]);
      int C2 = FULL_TO_COLUMN(F[B + 2]);
      F[B]     &= TblMaskSingle[C1] & TblMaskSingle[C2] & TblMaskDouble[C1 | C2];
      F[B + 1] &= TblMaskSingle[C0] & TblMaskSingle[C2] & TblMaskDouble[C0 | C2];
      F[B + 2] &= TblMaskSingle[C0] & TblMaskSingle[C1] & TblMaskDouble[C0 | C1];
   }
   //Confirm Row Method
   int Mask;
   for (int B = 0; B < 27; B++)
   {
      if (G[Index - 1].F[B] == F[B])
         continue;
      int FullMask = F[B];
      if ((Mask = HIGH_9_BIT(FullMask)) == 0)
         return false;
      F[B] &= TblConfirmRow[TblRowNumber[Mask] + 2];
      if ((Mask = MID_9_BIT(FullMask)) == 0)
         return false;
      F[B] &= TblConfirmRow[TblRowNumber[Mask] + 1];
      if ((Mask = LOW_9_BIT(FullMask)) == 0)
         return false;
      F[B] &= TblConfirmRow[TblRowNumber[Mask]];
   }
   //Get Change by Compare F with CompF
   for (int B = 0; B < 27; B++)
      Change |= (F[B] != CompF[B]) << B;
   //Single Grid Method
   if (!UpdateByGrid())
      return false;

   return true;
}

bool 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();
   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);

   byte 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;
}


/*****************************************************************************
 *
 * This Function get the number of 0 which is at the tail of a 27-bit Number
 *
 *****************************************************************************/
int PosLastBit(int v)
{
   int A = TblTailZero[v & 0x1FF];
   if (A != 9)
      return A; //Low 9 bit

   int B = TblTailZero[v >> 9 & 0x1FF];
   if (B != 9)
      return B + 9; //Middle 9 bit

   return TblTailZero[v >> 18] + 18; //High 9 bit
}



hi,JasonLion
Test this code please. I think it will work faster.
and I want to know the result about top1465
zhouyundong_2012
 
Posts: 138
Joined: 10 February 2012

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

Postby JasonLion » Sun Feb 19, 2012 6:59 pm

Your most recent code shows an 8% improvement on top1465. That is impressive, but still slower than JSolve for the same puzzles.
User avatar
JasonLion
2017 Supporter
 
Posts: 621
Joined: 25 October 2007
Location: Silver Spring, MD, USA

ZSolver! It maybe the fastest in any case.

Postby zhouyundong_2012 » Sun Mar 11, 2012 7:28 am

Code: Select all
#ifndef __sd_h__
#define __sd_h__

typedef unsigned char       byte;
typedef unsigned short       word;

#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_PALACE(v)    (((v) | ((v) >> 6) | ((v) >> 12)) & 0x1FF) //Full Mask(27-bit) to 9 bit, x-- y-- z--

#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           Finish; //27-bit Finish Bitmap
   int             F[27]; //27-bit Full Mask
   byte          U[27]; //3-bit Unique in Palace
   byte          Block; //The Block Number of guess [0, 27)
   byte          Line; //The Line Number of guess [0, 3)
   word          Mask; //The 9-bit Mask of guess
   word          Left; //The 9-bit Left Mask of guess
   int             BlockMask[27];
   int             BlockMaskSum[3];
};

//Common Table
extern int             TblMult3[81];
extern int             TblDivide3[81];
extern int             TblRmder3[81];
extern int             TblMult9[9];
//Basis Table
extern 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 Board
extern int             TblBoard_Palace[81];
extern int             TblBoard_Block[81];
extern int             TblBoard_BlockMask[81];
extern int             TblBoard_GridUniq[81];
//Table of Initial
extern int             TblSelfMask[81];
extern int             TblOtherMask[81];
//Complex Friend Method
extern int             TblMaskSingle[512];
extern int             TblMaskDouble[512];
//Other Table
extern int             TblPalaceMask[8];
extern bool             TblUniqFlag[8];
//Shrink Mask
extern int             TblShrinkLow[512];
extern int             TblShrinkMid[512];
extern int             TblShrinkHigh[512];
//Complex Method
extern int             TblComplexMask[512];
extern int             TblColumnSingle[512];
extern int             TblRowSingle[512];

extern void             CreateTable();

#endif
zhouyundong_2012
 
Posts: 138
Joined: 10 February 2012

Re: ZSolver! It maybe the fastest in any case.

Postby zhouyundong_2012 » Sun Mar 11, 2012 7:29 am

Code: Select all
#include <string.h>
#include "sd.h"

//Common Table
int                   TblMult3[81];
int                   TblDivide3[81];
int                   TblRmder3[81];
int                   TblMult9[9];
//Basis Table
int                   TblCombineMask[512];
int                   TblTailZero[512];
int                   TblNumberOne[512];
int                   TblAnother1[27];
int                   TblAnother2[27];
int                   TblShiftLeft[27];
//Table of Decompose Board
int                   TblBoard_Palace[81];
int                   TblBoard_Block[81];
int                   TblBoard_BlockMask[81];
int                   TblBoard_GridUniq[81];
//Table of Initial
int                   TblSelfMask[81];
int                   TblOtherMask[81];
//Complex Friend Method
int                   TblMaskSingle[512];
int                   TblMaskDouble[512];
//Other Table
int                   TblPalaceMask[8];
bool                TblUniqFlag[8];
//Shrink Mask
int                   TblShrinkLow[512];
int                   TblShrinkMid[512];
int                   TblShrinkHigh[512];
//Complex Method
int                   TblComplexMask[512];
int                   TblColumnSingle[512];
int                   TblRowSingle[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++)
   {
      TblRowSingle[i] = 7;
      int v = i & 0x49;
      if (v != 1 && v != 8 && v != 64)
         TblRowSingle[i] &= 6;
      v = i & 0x92;
      if (v != 2 && v != 16 && v != 128)
         TblRowSingle[i] &= 5;
      v = i & 0x124;
      if (v != 4 && v != 32 && v != 256)
         TblRowSingle[i] &= 3;
   }
}

void CreateTable()
{
   CreateTblCommon();
   CreateTblBasis();
   CreateTblBoard();
   CreateTblSelfMask();
   CreateTblOtherMask();
   CreateTblMaskSingle();
   CreateTblMaskDouble();
   CreateTblPalaceMask();
   CreateTblUniqFlag();
   CreateShrinkMask();
   CreateComplexMask();
   CreateTblColumnSingle();
}
zhouyundong_2012
 
Posts: 138
Joined: 10 February 2012

Re: ZSolver! It maybe the fastest in any case.

Postby zhouyundong_2012 » Sun Mar 11, 2012 7:30 am

Code: Select all
#include <windows.h>
#include <stdio.h>
#include "sd.h"

byte                Board[81]; //Board
CGame                G[33]; //Guess Board

byte                Index; //Guess Index
int                   Finish; //27-bit Finish Bitmap
int                   BlockMask[27]; //Block
int                   BlockMaskSum[3]; //Sum of BlockMask
int                   F[27]; //27-bit Full Mask
byte                U[27]; //3-bit Unique in Palace
int                   CompF[27]; //Use for Compare

byte                AllBoard[TotalBoard][81]; //All Boards
int                   TestCaseNumber; //Actual Number of Test Case

bool                Update();
void                Guess();
bool                Rollback();
byte                Calculate();

void InitSodoku()
{
   Finish = 0;
   Index = 1;
   BlockMaskSum[0] = BlockMaskSum[1] = BlockMaskSum[2] = 0;
   memset(BlockMask, 0, sizeof(BlockMask));
   memset(F, -1, sizeof(F));
   memset(U, 0, sizeof(U));
   //Get Full Mask
   for (int i = 80; i >= 0; --i)
   {
      if (Board[i] == '0')
         continue;

      int V = Board[i] - '1'; //Value
      int B = TblMult3[V] + TblBoard_Block[i]; //Block
      //Get BlockMask and Sum of BlockMask
      BlockMask[B] |= TblBoard_BlockMask[i];
      BlockMaskSum[TblBoard_Block[i]] |= TblBoard_BlockMask[i];
      //Get Full Mask
      F[B] &= TblSelfMask[i];
      F[TblAnother1[B]] &= TblOtherMask[i];
      F[TblAnother2[B]] &= TblOtherMask[i];
      //Get Grid Uniq Bitmap and Finish Bitmap
      if ((U[B] |= TblBoard_GridUniq[i]) == 7)
         Finish |= TblShiftLeft[B];
   }
   for (int B = 26; B >= 0; --B)
      F[B] &= BlockMaskSum[TblRmder3[B]] ^ BlockMask[B] ^ BIT_SET_27;
   //Clear CompF, Save F as the G[0]
   memset(CompF, 0, sizeof(F));
   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:
   word Left = HML_9_BIT(F[G[Index].Block], G[Index].Line);
   word Mask = Left & -Left;
   //Save Data
   G[Index].Finish = Finish;
   G[Index].Mask = Mask;
   G[Index].Left = Left;
   memcpy(G[Index].F, F, sizeof(F));
   memcpy(CompF, F, sizeof(F));
   memcpy(G[Index].U, U, sizeof(U));
   F[G[Index].Block] &= TblSelfMask[TblTailZero[Mask] + TblMult9[G[Index].Line]];
   Index++;
}

bool Rollback()
{
   if (Index-- == 1)
      return false;
   //Restore Data
   Finish = G[Index].Finish;
   byte Block = G[Index].Block;
   byte Line = G[Index].Line;
   memcpy(F, G[Index].F, sizeof(F));
   memcpy(CompF, F, sizeof(F));
   memcpy(U, G[Index].U, sizeof(U));

   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 (Finish != BIT_SET_27)
         {
            Guess();
            continue;
         }
         if (FoundAnswer) //Find Answer
            return MoreAnswer;
         FoundAnswer = true;
      }
      if (!Rollback()) //Backtrack Over
         return FoundAnswer ? UniqAnswer : NoAnswer;
   }
}

bool Update()
{
   bool Change = true;
   while (Change)
   {
      Change = false;
      for (int B = 0; B < 27; B++)
      {
         if (CompF[B] == F[B])
            continue;
         Change = true;
         //Complex Self Method
         int Shrink = FULL_TO_SHRINK(F[B]);
         if (TblComplexMask[Shrink] == 0)
            return false;
         if (TblComplexMask[Shrink] != BIT_SET_27)
         {
            F[B] &= TblComplexMask[Shrink];
            Shrink = FULL_TO_SHRINK(F[B]);
         }
         CompF[B] = F[B];
         //Complex Friend Method
         int Column = FULL_TO_COLUMN(F[B]);
         int C1 = FULL_TO_COLUMN(F[TblAnother1[B]]);
         int C2 = FULL_TO_COLUMN(F[TblAnother2[B]]);
         F[TblAnother2[B]] &= TblMaskSingle[Column] & TblMaskDouble[Column | C1];
         F[TblAnother1[B]] &= TblMaskSingle[Column] & TblMaskDouble[Column | C2];
         //Single Grid Method
         int Single = (TblRowSingle[Shrink] & TblColumnSingle[Column]) ^ U[B];
         if (Single == 0)
            continue;
         if ((U[B] |= Single) == 7)
            Finish |= TblShiftLeft[B];
         int S = F[B] & TblPalaceMask[Single];
         //Friend Block
         switch (TblRmder3[B])
         {
         case 0:
            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); AN(F[24], S);
            break;
         case 1:
            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); AN(F[25], S);
            break;
         case 2:
            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); AN(F[26], S);
            break;
         }
         F[B] = CompF[B];
      }
   }
   return true;
}

bool 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();
   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);

   byte 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;
}
zhouyundong_2012
 
Posts: 138
Joined: 10 February 2012

Postby Afmob » Sun Mar 11, 2012 9:00 am

First, congratulations! Your solver only took 481 ms (this includes reading the text file) on the Top 50000, which is faster than JSolve (768 ms).

BUT, you didn't have to make a new thread for your update. Secondly, your solver crashed when I tried a puzzle with multiple solutions (for example, a Sudoku with no given) or with no solution (all cells set to 1). Furthermore your solver should be able to handle files of arbitrary size, so the number of puzzles allowed should not be limited by "TotalBoard". It also cannot handle characters correctly which aren't numbers such as "." which is commonly used for 0. On a minor note, you should include reading the text file into the total time spent to make a fair comparison between the solvers.

Another thing I noticed in the code is that no further Sudoku is tested as soon as a puzzle with no unique solution occurs. Wouldn't it make more sense to test the remaining puzzles?
Afmob
 
Posts: 130
Joined: 28 June 2011

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

Postby JasonLion-Admin » Sun Mar 11, 2012 12:18 pm

Very impressive! You beat JSolve by nearly 10% on top1465.

I merged your new topic into your existing topic. It is better to keep everything together in one place.
User avatar
JasonLion-Admin
Site Admin
Site Admin
 
Posts: 72
Joined: 17 April 2010
Location: Silver Spring, MD, USA

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

Postby champagne » Sun Mar 11, 2012 2:06 pm

for brute force solving, I am using the code from dobrichev

fss

does anybody know how it compares to these ones
for the function limited to "checking the validity of a puzzle"

champagne
champagne
2017 Supporter
 
Posts: 5653
Joined: 02 August 2007
Location: France Brittany

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

Postby JasonLion » Sun Mar 11, 2012 5:50 pm

dobrichev's code is in the same general range as JSolve, slightly better with some compilers/puzzles, slightly worse with others. Preliminary tests show that zhouyundong_2012's code is now faster than either of them by roughly 10%. However, I haven't run zhouyundong_2012's code against the complete range of puzzle collections, so there is a small chance of better or worse times on some kinds of puzzles.
User avatar
JasonLion
2017 Supporter
 
Posts: 621
Joined: 25 October 2007
Location: Silver Spring, MD, USA

PreviousNext

Return to Software