The New Sudoku Players' Forum

[zhouyundong_2012]

I Dicide to Show All Source Code: comment is written by Chinese

sd.h

Code: Select all

#ifndef __sd_h__
#define __sd_h__

typedef unsigned char       byte;
typedef unsigned short       word;

#define TimeBackground       0.000001396825 //背景时耗
#define TotalBoard          30000 //总局数

//解的性质
#define NoAnswer          0
#define UniqAnswer          1
#define MoreAnswer          2

//高中低9位
#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 //完全掩码转换为列掩码
#define FULL_TO_PALACE(v)    ((v) | ((v) >> 6) | ((v) >> 12)) & 0x1FF //完全掩码转换为宫掩码

#define BIT_SET_27          0x07FFFFFF

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

struct CGame {
  public:
   int           Finish; //完成位图
   int             F[27]; //完全掩码
   byte          U[28]; //单格已唯一
   byte          Block; //猜测的区号
   byte          Line; //猜测的行号
   word          Mask; //猜测的着法
   word          Left; //剩余的着法
};

//通用表
extern int             TblMult3[81];
extern int             TblDivide3[81];
extern int             TblRmder3[81];
extern int             TblMult9[9];
//基础表
extern int             TblCombineMask[512];
extern int             TblTailZero[512];
extern int             TblNumberOne[512];
extern int             TblAnother1[27];
extern int             TblAnother2[27];
extern int             TblShiftLeft[27];
//盘面分解
extern int             TblBoard_Palace[81];
extern int             TblBoard_Block[81];
extern int             TblBoard_BlockMask[81];
extern int             TblBoard_GridUniq[81];
//创建用表
extern int             TblSelfMask[81];
extern int             TblOtherMask[81];
//单行排除
extern int             TblSingleRow[12];
extern int             TblPalace_Row[512];
//单双列排除
extern int             TblMaskSingle[512];
extern int             TblMaskDouble[512];
//唯一行排除
extern int             TblConfirmRow[12];
//其他表
extern int             TblPalaceMask[3];
extern int             TblStrange[27];
extern int             TblChangeMask[27];
extern bool             TblUniqFlag[8];


extern void             CreateTable();

#endif


[zhouyundong_2012]

Tbl.cpp

Code: Select all

#include "StdAfx.h"
#include "sd.h"

//通用表
int                   TblMult3[81];
int                   TblDivide3[81];
int                   TblRmder3[81];
int                   TblMult9[9];
//基础表
int                   TblCombineMask[512];
int                   TblTailZero[512];
int                   TblNumberOne[512];
int                   TblAnother1[27];
int                   TblAnother2[27];
int                   TblShiftLeft[27];
//盘面分解
int                   TblBoard_Palace[81];
int                   TblBoard_Block[81];
int                   TblBoard_BlockMask[81];
int                   TblBoard_GridUniq[81];
//创建用表
int                   TblSelfMask[81];
int                   TblOtherMask[81];
//单行排除
int                   TblSingleRow[12];
int                   TblPalace_Row[512];
//单双列排除
int                   TblMaskSingle[512];
int                   TblMaskDouble[512];
//唯一行排除
int                   TblConfirmRow[12];
//其他表
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: //在上面
         TblAnother1[i] = i + 1;
         TblAnother2[i] = i + 2;
         break;
      case 1: //在中间
         TblAnother1[i] = i - 1;
         TblAnother2[i] = i + 1;
         break;
      case 2: //在下面
         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(TblPalace_Row, 0, sizeof(TblPalace_Row)); //不构成单行时为0
   for (int i = 0; i < 512; i++)
   {
      if ((i & 0x1F8) == 0 && i & 0x7)
         TblPalace_Row[i] = 3;
      if ((i & 0x1C7) == 0 && i & 0x38)
         TblPalace_Row[i] = 6;
      if ((i & 0x3F) == 0 && i & 0x1C0)
         TblPalace_Row[i] = 9;
   }
   int Mask[3] = { 0x1F8, 0x1C7, 0x3F };
   for (int i = 0; i < 3; i++) //宫
   {
      TblSingleRow[i] = BIT_SET_27;
      for (int j = 1; j <= 3; j++) //掩码结果
      {
         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; //高3位
      if (v != 4 && v != 2 && v != 1)
         TblMaskSingle[i] &= 0x3F;
      v = i >> 3 & 0x7; //中间3位
      if (v != 4 && v != 2 && v != 1)
         TblMaskSingle[i] &= 0x1C7;
      v = i & 0x7; //低3位
      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; //高3位
      if (v != 6 && v != 5 && v != 3)
         TblMaskDouble[i] &= 0x3F;
      v = i >> 3 & 0x7; //中间3位
      if (v != 6 && v != 5 && v != 3)
         TblMaskDouble[i] &= 0x1C7;
      v = i & 0x7; //低3位
      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++) //掩码结果
   {
      TblConfirmRow[i - 1] = BIT_SET_27;
      for (int j = 0; j < 3; j++) //è¡Œ
      {
         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()
{
   //按每个宫数,每个宫按行数
   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]

Code: Select all

/*************************************** Copyright    ----->   ZhouYunDong******************Involve LT/GT base it**************************/
#include "StdAfx.h"
#include <windows.h>
#include "sd.h"

byte                Board[81]; //盘面
CGame                G[33]; //猜测盘

byte                Index; //猜测索引
int                   Change; //变更位图
int                   Finish; //完成位图
int                   BlockMask[27]; //区掩码
int                   BlockMaskSum[3]; //区掩码和
int                   F[27]; //完全掩码
byte                U[28]; //单格已唯一
int                   CompF[27]; //比较用

byte                AllBoard[TotalBoard][81]; //总盘面
int                   TestCaseNumber; //实际测试数

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));
   //求完全掩码,区掩码和
   for (int i = 80; i >= 0; --i)
   {
      if (Board[i] == '0')
         continue;

      int V = Board[i] - '1'; //值
      int B = TblMult3[V] + TblBoard_Block[i]; //区
      //区掩码及区掩码和
      BlockMask[B] |= TblBoard_BlockMask[i];
      BlockMaskSum[TblBoard_Block[i]] |= TblBoard_BlockMask[i];
      //完全掩码
      F[B] &= TblSelfMask[i];
      F[TblAnother1[B]] &= TblOtherMask[i];
      F[TblAnother2[B]] &= TblOtherMask[i];
      //单格掩码及完成位图
      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;
   //比较用清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;
   //保存环境
   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;
   //还原环境
   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]];
   //是否唯一
   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) //发现新解
            return MoreAnswer;
         FoundAnswer = true;
      }
      if (!Rollback()) //遍历完毕
         return FoundAnswer ? UniqAnswer : NoAnswer;
   }
}

bool UpdateByGrid()
{
   int B = 0;
   while (Change &= ~Finish)
   {
      B = Change >> B ? PosLastBit(Change >> B) + B : PosLastBit(Change); //循环改变
      Change ^= TblShiftLeft[B];
      if (CompF[B] == F[B])
         continue;
      for (int i = 0; i < 3; i++) //三个宫
      {
         if (U[B] & TblShiftLeft[i])
            continue;
         int S = F[B] & TblPalaceMask[i];
         if (S == 0)
            return false;

         int TheMask = FULL_TO_PALACE(S >> TblMult3[i]);
         if (S & S - 1)
         {
            //宫内单行排除
            if (TblPalace_Row[TheMask] != 0 && F[B] & ~TblSingleRow[i + TblPalace_Row[TheMask]])
            {
               F[B] &= TblSingleRow[i + TblPalace_Row[TheMask]];
               Change |= TblShiftLeft[B];
            }
            continue;
         }
         if ((U[B] |= TblShiftLeft[i]) == 7)
            Finish |= TblShiftLeft[B];
         //自区排除
         F[B] &= TblStrange[TblMult9[i] + TblTailZero[TheMask]];
         //友区排除
         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;
         //他区排除
         F[TblAnother1[B]] &= TblCombineMask[FULL_TO_COLUMN(S)];
         F[TblAnother2[B]] &= TblCombineMask[FULL_TO_COLUMN(S)];
         Change |= TblChangeMask[B];
      }
   }
   return true;
}

bool Update()
{
   //用初始或猜测或回溯的改变掩码进行单格排除
   if (!UpdateByGrid())
      return false;
   memcpy(CompF, F, sizeof(F));
   //单双列排除
   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];
   }
   //唯一行排除
   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[TblPalace_Row[Mask] + 2];
      if ((Mask = MID_9_BIT(FullMask)) == 0)
         return false;
      F[B] &= TblConfirmRow[TblPalace_Row[Mask] + 1];
      if ((Mask = LOW_9_BIT(FullMask)) == 0)
         return false;
      F[B] &= TblConfirmRow[TblPalace_Row[Mask]];
   }
   //用排除结果进行比较得到改变掩码
   for (int B = 0; B < 27; B++)
      Change |= (F[B] != CompF[B]) << B;
   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();

   //设置进程和线程优先级
   DWORD dwOldProcessP = GetPriorityClass(GetCurrentProcess());
   DWORD dwOldThreadP  = GetThreadPriority(GetCurrentThread());

   SetPriorityClass(GetCurrentProcess(), REALTIME_PRIORITY_CLASS);
   SetThreadPriority(GetCurrentThread(), THREAD_PRIORITY_TIME_CRITICAL);

   //获取频率
   LARGE_INTEGER Frequency;
   ::QueryPerformanceFrequency(&Frequency);

   //开始时间
   LARGE_INTEGER start;
   ::QueryPerformanceCounter(&start);

   byte Answer = 0;
   //计算过程
   for (int i = 0; i < TestCaseNumber; i++)
   {
      memcpy(Board, AllBoard[i], 81);
      InitSodoku();
      if ((Answer = Calculate()) != UniqAnswer)
         break;
   }

   //结束时间
   LARGE_INTEGER stop;
   ::QueryPerformanceCounter(&stop);

   double spend = (double)(stop.QuadPart - start.QuadPart) / (double)Frequency.QuadPart - TimeBackground;

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

   //还原优先级
   SetThreadPriority(GetCurrentThread(), dwOldThreadP);
   SetPriorityClass(GetCurrentProcess(), dwOldProcessP);

   return true;
}


/*****************************************************************************
 *
 * 这个函数只接受一个2^27以内的数，求其最后一个1所在的位置
 *
 * TblTailZero[512]表达了一个范围在0到511之间的数的末尾0的个数
 *
 *****************************************************************************/
int PosLastBit(int v)
{
   int A = TblTailZero[v & 0x1FF];
   if (A != 9)
      return A; //低9位

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

   return TblTailZero[v >> 18] + 18; //高9位
}


[zhouyundong_2012]

hi all,
Do you love this program?

[ronk]

Let's see now, four minutes after you post some source code, you ask whether others "love" your program. We're fast here, but not that fast.

[Afmob]

After making same modifications (replacing "stdafx.h" with <fstream>, deleting the Chinese comments, merging tbl.cpp with sd.h, increasing the totalboard constant and changing the main to be an int function) I could compare your solver to JSolve (see the link in the first page) using the top50000.

JSolve: 0.768 seconds
Zhou: 0.886 seconds

So your solver is really fast but not as fast as JSolve (at least for this test case).

[tarek]

hi,tarek,
Why annoying?
What does Exchanges mean?

I was annoyed because the exchanges (Your conversation with b_turner) had no source code attached, limiting the benifit to other readers .....

Not anymore !!!!

[JasonLion]

I'm having problems with crashing when I turn on optimizations in the compiler (Mac OS X). The crash is in Rollback, memcpy(F, G[Index].F, sizeof(F)); which makes little sense as Index is valid (1) and everything else there looks good.

Without optimization it works, but the speed is so so (which is to be expected).

I haven't been able to understand the code yet. A few comments in English would help

[zhouyundong_2012]

thanks,
what is the result for other case?

[zhouyundong_2012]

Update sd.cpp: Speed from 24.2 to 21.2 (3 / 24 * 100 % = 12.5% improved) (top50000)

Code: Select all

#include "StdAfx.h"
#include <windows.h>
#include "sd.h"

byte                Board[81]; //盘面
CGame                G[33]; //猜测盘

byte                Index; //猜测索引
int                   Change; //变更位图
int                   Finish; //完成位图
int                   BlockMask[27]; //区掩码
int                   BlockMaskSum[3]; //区掩码和
int                   F[27]; //完全掩码
byte                U[28]; //单格已唯一
int                   CompF[27]; //比较用

byte                AllBoard[TotalBoard][81]; //总盘面
int                   TestCaseNumber; //实际测试数

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));
   //求完全掩码,区掩码和
   for (int i = 80; i >= 0; --i)
   {
      if (Board[i] == '0')
         continue;

      int V = Board[i] - '1'; //值
      int B = TblMult3[V] + TblBoard_Block[i]; //区
      //区掩码及区掩码和
      BlockMask[B] |= TblBoard_BlockMask[i];
      BlockMaskSum[TblBoard_Block[i]] |= TblBoard_BlockMask[i];
      //完全掩码
      F[B] &= TblSelfMask[i];
      F[TblAnother1[B]] &= TblOtherMask[i];
      F[TblAnother2[B]] &= TblOtherMask[i];
      //单格掩码及完成位图
      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;
   //比较用清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;
   //保存环境
   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;
   //还原环境
   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]];
   //是否唯一
   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) //发现新解
            return MoreAnswer;
         FoundAnswer = true;
      }
      if (!Rollback()) //遍历完毕
         return FoundAnswer ? UniqAnswer : NoAnswer;
   }
}

bool UpdateByGrid()
{
   int B = 0;
   while (Change &= ~Finish)
   {
      B = Change >> B ? PosLastBit(Change >> B) + B : PosLastBit(Change); //循环改变
      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)
         {
            //宫内单行排除
            if (TblPalace_Row[TheMask] != 0 && F[B] & ~TblSingleRow[TblPalace_Row[TheMask]])
            {
               F[B] &= TblSingleRow[TblPalace_Row[TheMask]];
               Change |= TblShiftLeft[B];
            }
            goto LB_P1;
         }
         if ((U[B] |= 1) == 7)
            Finish |= TblShiftLeft[B];
         //他区排除
         F[TblAnother1[B]] &= TblCombineMask[FULL_TO_COLUMN(S)];
         F[TblAnother2[B]] &= TblCombineMask[FULL_TO_COLUMN(S)];
         //自区排除
         F[B] &= TblStrange[TblTailZero[TheMask]];
         //友区排除
         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)
         {
            //宫内单行排除
            if (TblPalace_Row[TheMask] != 0 && F[B] & ~TblSingleRow[1 + TblPalace_Row[TheMask]])
            {
               F[B] &= TblSingleRow[1 + TblPalace_Row[TheMask]];
               Change |= TblShiftLeft[B];
               goto LB_P2;
            }
            goto LB_P2;
         }
         if ((U[B] |= 2) == 7)
            Finish |= TblShiftLeft[B];
         //他区排除
         F[TblAnother1[B]] &= TblCombineMask[FULL_TO_COLUMN(S)];
         F[TblAnother2[B]] &= TblCombineMask[FULL_TO_COLUMN(S)];
         //自区排除
         F[B] &= TblStrange[9 + TblTailZero[TheMask]];
         //友区排除
         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)
         {
            //宫内单行排除
            if (TblPalace_Row[TheMask] != 0 && F[B] & ~TblSingleRow[2 + TblPalace_Row[TheMask]])
            {
               F[B] &= TblSingleRow[2 + TblPalace_Row[TheMask]];
               Change |= TblShiftLeft[B];
               goto LB_P0;
            }
            continue;
         }
         if ((U[B] |= 4) == 7)
            Finish |= TblShiftLeft[B];
         //他区排除
         F[TblAnother1[B]] &= TblCombineMask[FULL_TO_COLUMN(S)];
         F[TblAnother2[B]] &= TblCombineMask[FULL_TO_COLUMN(S)];
         //自区排除
         F[B] &= TblStrange[18 + TblTailZero[TheMask]];
         //友区排除
         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];
      }
   }
   return true;
}

bool Update()
{
   //用初始或猜测或回溯的改变掩码进行单格排除
   if (!UpdateByGrid())
      return false;
   memcpy(CompF, F, sizeof(F));
   //单双列排除
   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];
   }
   //唯一行排除
   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[TblPalace_Row[Mask] + 2];
      if ((Mask = MID_9_BIT(FullMask)) == 0)
         return false;
      F[B] &= TblConfirmRow[TblPalace_Row[Mask] + 1];
      if ((Mask = LOW_9_BIT(FullMask)) == 0)
         return false;
      F[B] &= TblConfirmRow[TblPalace_Row[Mask]];
   }
   //用排除结果进行比较得到改变掩码
   for (int B = 0; B < 27; B++)
      Change |= (F[B] != CompF[B]) << B;
   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();

   //设置进程和线程优先级
   DWORD dwOldProcessP = GetPriorityClass(GetCurrentProcess());
   DWORD dwOldThreadP  = GetThreadPriority(GetCurrentThread());

   SetPriorityClass(GetCurrentProcess(), REALTIME_PRIORITY_CLASS);
   SetThreadPriority(GetCurrentThread(), THREAD_PRIORITY_TIME_CRITICAL);

   //获取频率
   LARGE_INTEGER Frequency;
   ::QueryPerformanceFrequency(&Frequency);

   //开始时间
   LARGE_INTEGER start;
   ::QueryPerformanceCounter(&start);

   byte Answer = 0;
   //计算过程
   for (int i = 0; i < TestCaseNumber; i++)
   {
      memcpy(Board, AllBoard[i], 81);
      InitSodoku();
      if ((Answer = Calculate()) != UniqAnswer)
         break;
   }

   //结束时间
   LARGE_INTEGER stop;
   ::QueryPerformanceCounter(&stop);

   double spend = (double)(stop.QuadPart - start.QuadPart) / (double)Frequency.QuadPart - TimeBackground;

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

   //还原优先级
   SetThreadPriority(GetCurrentThread(), dwOldThreadP);
   SetPriorityClass(GetCurrentProcess(), dwOldProcessP);

   return true;
}


/*****************************************************************************
 *
 * 这个函数只接受一个2^27以内的数，求其最后一个1所在的位置
 *
 * TblTailZero[512]表达了一个范围在0到511之间的数的末尾0的个数
 *
 *****************************************************************************/
int PosLastBit(int v)
{
   int A = TblTailZero[v & 0x1FF];
   if (A != 9)
      return A; //低9位

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

   return TblTailZero[v >> 18] + 18; //高9位
}


[zhouyundong_2012]

I'm having problems with crashing when I turn on optimizations in the compiler (Mac OS X). The crash is in Rollback, memcpy(F, G[Index].F, sizeof(F)); which makes little sense as Index is valid (1) and everything else there looks good.

Sorry, I don't know why! Maybe when using optimizations, G[1] should be initialized.
Or maybe G[33] isn't be recogized by computer?

[zhouyundong_2012]

Today's improvement:

top50000: average from 24.2us to 21.2us 12.5%improved (2.2G DoubleCore)
17sudoku: average from 17.5us to 15.0us 14.2%improved (2.2G DoubleCore)



It means 17sudoku at 2.8G CPU,it will take 11.5 * 85.8% = 9.9us (average)

[JasonLion]

I was finally able to avoid the crash. It turned out to be a compiler bug in the optimization of memcpy.

Congratulations, you are getting quite good at easy puzzles. On sudoku17 I have your program at 0.413 seconds and JSolve at 0.462. On the other hand, switching to more difficult puzzles, on top1465 repeated 20 times, I have you at 2.939 seconds and JSolve at 1.610 seconds.

JSolve includes hidden singles, naked singles, and pointing pairs. On easy puzzles it is actually faster to not bother with pointing pairs, but they really help out on more difficult puzzles.

[zhouyundong_2012]

I will try to make some improvement on Update and UpdateByGrid. I hope it can be better.

[zhouyundong_2012]

I made a improvement, from 15.0 to 14.7us 0.3 / 15 * 100% = 2% (at least 2%),maybe 3%