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 » Sun Apr 08, 2012 1:37 pm

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_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                   TblColumnMask[8];
bool                TblUniqFlag[8];
//Complex Method
byte                TblShrinkMask[32768];
int                   TblComplexMask[512];
int                   TblColumnSingle[512];
int                   TblShrinkSingle[512];


void CreateTblCommon()
{
   for (int i = 0; i < 81; i++)
   {
      TblMult3[i] = i * 3;
      TblDivide3[i] = i / 3;
      TblRmder3[i] = i % 3;
   }
   for (int i = 0; i < 9; i++)
   {
      TblMult9[i] = i * 9;
   }
}

void CreateTblCombineMask()
{
   for (int i = 0; i < 512; i++)
   {
      TblCombineMask[i] = (i | (i << 9) | (i << 18)) ^ BIT_SET_27;
   }
}

void CreateTblAnother()
{
   for (int i = 0; i < 27; i++)
   {
      switch (i % 3)
      {
      case 0: //At Top
         TblAnother1[i] = i + 1;
         TblAnother2[i] = i + 2;
         break;
      case 1: //At Middle
         TblAnother1[i] = i - 1;
         TblAnother2[i] = i + 1;
         break;
      case 2: //At Bottom
         TblAnother1[i] = i - 2;
         TblAnother2[i] = i - 1;
         break;
      }
   }
}

void CreateTblTailZero()
{
   memset(TblTailZero, 0, sizeof(TblTailZero));
   for (int i = 0; i < 512; i++)
   {
      for (int j = 0; j < 9; j++)
      {
         if (i & (1 << j))
            break;
         TblTailZero[i]++;
      }
   }
}

void CreateTblNumberOne()
{
   memset(TblNumberOne, 0, sizeof(TblNumberOne));
   for (int i = 0; i < 512; i++)
   {
      for (int j = 0; j < 9; j++)
      {
         if (i & (1 << j))
            TblNumberOne[i]++;
      }
   }
}

void CreateTblShiftLeft()
{
   for (int i = 0; i < 27; i++)
   {
      TblShiftLeft[i] = 1 << i;
   }
}

void CreateTblBasis()
{
   CreateTblCombineMask();
   CreateTblAnother();
   CreateTblTailZero();
   CreateTblNumberOne();
   CreateTblShiftLeft();
}

void CreateTblBoard()
{
   for (int i = 0; i < 81; i++)
   {
      TblBoard_Block[i] = i / 27;
      TblBoard_BlockMask[i] = 1 << i % 27;
      TblBoard_GridUniq[i] = 1 << i % 27 / 9;
   }
}

void CreateTblSelfMask()
{
   int Mask[3] = { 0x7E3F1F8, 0x71F8FC7, 0x0FC7E3F };
   int Row[3] = { 0x7FFFE00, 0x7FC01FF, 0x3FFFF };
   for (int i = 0; i < 81; i++)
   {
      int Palace = i % 9 / 3;
      TblSelfMask[i] = Mask[Palace] & Row[i % 27 / 9] | TblBoard_BlockMask[i];
   }
}

void CreateTblOtherMask()
{
   for (int i = 0; i < 81; i++)
   {
      TblOtherMask[i] = TblCombineMask[1 << i % 9];
   }
}

void CreateTblMaskSingle()
{
   for (int i = 0; i < 512; i++)
   {
      TblMaskSingle[i] = i;
      int v = i >> 6; //High 3 bit
      if (v != 4 && v != 2 && v != 1)
         TblMaskSingle[i] &= 0x3F;
      v = i >> 3 & 0x7; //Middle 3 bit
      if (v != 4 && v != 2 && v != 1)
         TblMaskSingle[i] &= 0x1C7;
      v = i & 0x7; //Low 3 bit
      if (v != 4 && v != 2 && v != 1)
         TblMaskSingle[i] &= 0x1F8;
      TblMaskSingle[i] = TblCombineMask[TblMaskSingle[i]];
   }
}

void CreateTblMaskDouble()
{
   for (int i = 0; i < 512; i++)
   {
      TblMaskDouble[i] = i;
      int v = i >> 6; //High 3 bit
      if (v != 6 && v != 5 && v != 3)
         TblMaskDouble[i] &= 0x3F;
      v = i >> 3 & 0x7; //Middle 3 bit
      if (v != 6 && v != 5 && v != 3)
         TblMaskDouble[i] &= 0x1C7;
      v = i & 0x7; //Low 3 bit
      if (v != 6 && v != 5 && v != 3)
         TblMaskDouble[i] &= 0x1F8;
      TblMaskDouble[i] = TblCombineMask[TblMaskDouble[i]];
   }
}

void CreateTblColumnMask()
{
   memset(TblColumnMask, 0, sizeof(TblColumnMask));
   for (int i = 0; i < 8; i++)
   {
      for (int j = 0; j < 3; j++)
      {
         if (i & (1 << j))
            TblColumnMask[i] |= 0x1FF << TblMult9[j];
      }
   }
}

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

void CreateTblShrinkMask()
{
   memset(TblShrinkMask, 0, sizeof(TblShrinkMask));
   for (int i = 0; i < 32768; i++)
   {
      TblShrinkMask[i] |= i & 0x7000 ? 16 : 0;
      TblShrinkMask[i] |= i & 0xE00 ? 8 : 0;
      TblShrinkMask[i] |= i & 0x1C0 ? 4 : 0;
      TblShrinkMask[i] |= i & 0x38 ? 2 : 0;
      TblShrinkMask[i] |= i & 0x7 ? 1 : 0;
   }
}

void CreateTblComplexMask()
{
   int MaskH[9] = { 0x7FFFE07, 0x7FFFE38, 0x7FFFFC0, 0x7FC0FFF, 0x7FC71FF, 0x7FF81FF, 0x1FFFFF, 0xE3FFFF, 0x703FFFF }; //A B C
   int MaskV[9] = { 0x7E3F1FF, 0x71F8FFF, 0xFC7FFF, 0x7E3FFF8, 0x71FFFC7, 0xFFFE3F, 0x7FFF1F8, 0x7FF8FC7, 0x7FC7E3F }; //A 0 0

   int index;
   for (int i = 0; i < 512; i++)
   {
      if (!(i & 0x7) || !(i & 0x38) || !(i & 0x1C0) || !(i & 0x124) || !(i & 0x92) || !(i & 0x49))
      {
         TblComplexMask[i] = 0;
         continue;
      }
      TblComplexMask[i] = BIT_SET_27;
      //Like Locked Candidate
      for (int j = 0; j < 3; j++)
      {
         for (int k = 0; k < 3; k++)
         {
            index = TblMult3[k] + j;
            if ((i & (1 << index)) && !(i & (1 << (TblMult3[TblAnother1[k]] + j))) && !(i & (1 << (TblMult3[TblAnother2[k]] + j))))
               TblComplexMask[i] &= MaskH[index]; //Horizontal
            index = TblMult3[j] + k;
            if ((i & (1 << index)) && !(i & (1 << TblAnother1[index])) && !(i & (1 << TblAnother2[index])))
               TblComplexMask[i] &= MaskV[index]; //Vertical
         }
      }
   }
   for (int i = 0; i < 512; i++)
   {
      if ((i & FULL_TO_SHRINK(TblComplexMask[i])) == 0)
         TblComplexMask[i] = 0;
      else if ((i & FULL_TO_SHRINK(TblComplexMask[i])) == i)
         TblComplexMask[i] = BIT_SET_27;
   }
}

void CreateTblColumnSingle()
{
   memset(TblColumnSingle, 0, sizeof(TblColumnSingle));
   for (int i = 0; i < 512; i++)
   {
      if (TblNumberOne[i & 0x7] == 0 || TblNumberOne[i & 0x38] == 0 || TblNumberOne[i & 0x1C0] == 0)
         continue;
      if (TblNumberOne[i & 0x7] == 1) //Low 3 bit
         TblColumnSingle[i] |= 0x49;
      if (TblNumberOne[i & 0x38] == 1) //Middle 3 bit
         TblColumnSingle[i] |= 0x92;
      if (TblNumberOne[i & 0x1C0] == 1) //High 3 bit
         TblColumnSingle[i] |= 0x124;
   }
}

void CreateTblShrinkSingle()
{
   for (int i = 0; i < 512; i++)
   {
      int j = i & FULL_TO_SHRINK(TblComplexMask[i]);
      TblShrinkSingle[i] = j;
      if (TblNumberOne[j & 0x7] != 1) //Low 3 bit
         TblShrinkSingle[i] &= 0x1F8;
      if (TblNumberOne[j & 0x38] != 1) //Middle 3 bit
         TblShrinkSingle[i] &= 0x1C7;
      if (TblNumberOne[j & 0x1C0] != 1) //High 3 bit
         TblShrinkSingle[i] &= 0x3F;
   }
}

void CreateTable()
{
   CreateTblCommon();
   CreateTblBasis();
   CreateTblBoard();
   CreateTblSelfMask();
   CreateTblOtherMask();
   CreateTblMaskSingle();
   CreateTblMaskDouble();
   CreateTblColumnMask();
   CreateTblUniqFlag();
   CreateTblShrinkMask();
   CreateTblComplexMask();
   CreateTblColumnSingle();
   CreateTblShrinkSingle();
}
zhouyundong_2012
 
Posts: 148
Joined: 10 February 2012

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

Postby zhouyundong_2012 » Sun Apr 08, 2012 1:39 pm

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

/*
 * First Step : Compile this project with __ProgramWritter used and Run it
 * Second Step: Replace the function Update in the bottom of this file with all contents of Update.c created by First Step in current directory
 * Third Step : Recompile this project without __ProgramWritter and Run it
 *
 *           Warning: Can NOT comment __ProgramWritter until finish 3 steps!
 *
 * Good Luck! Shanghai China 2012/3/14 Zhou Yun Dong
 */
#define __ProgramWritter

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

int                   Index; //Guess Index
int                   BlockMask[27]; //Block
int                   BlockMaskSum[3]; //Sum of BlockMask
int                   F[27]; //27-bit Full Mask
int                   U[27]; //3-bit Unique in Row
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()
{
   Index = 0;
   BlockMaskSum[0] = BlockMaskSum[1] = BlockMaskSum[2] = 0;
   for (int B = 26; B >= 0; B--)
   {
      BlockMask[B] = U[B] = 0;
      CompF[B] = F[B] = BIT_SET_27;
   }
   //Get Full Mask
   for (int i = 80; i >= 0; i--)
   {
      if (Board[i] == '0')
         continue;

      int B = TblMult3[Board[i] - '1'] + TblBoard_Block[i];
      //Get BlockMask and Sum of BlockMask
      BlockMaskSum[TblBoard_Block[i]] |= TblBoard_BlockMask[i];
      BlockMask[B] |= TblBoard_BlockMask[i];
      //Get Full Mask
      F[B] &= TblSelfMask[i];
      F[TblAnother1[B]] &= TblOtherMask[i];
      F[TblAnother2[B]] &= TblOtherMask[i];
      U[B] |= TblBoard_GridUniq[i];
   }
   BlockMaskSum[0] ^= BIT_SET_27;
   BlockMaskSum[1] ^= BIT_SET_27;
   BlockMaskSum[2] ^= BIT_SET_27;
   F[0]  &= BlockMaskSum[0] ^ BlockMask[0];
   F[3]  &= BlockMaskSum[0] ^ BlockMask[3];
   F[6]  &= BlockMaskSum[0] ^ BlockMask[6];
   F[9]  &= BlockMaskSum[0] ^ BlockMask[9];
   F[12] &= BlockMaskSum[0] ^ BlockMask[12];
   F[15] &= BlockMaskSum[0] ^ BlockMask[15];
   F[18] &= BlockMaskSum[0] ^ BlockMask[18];
   F[21] &= BlockMaskSum[0] ^ BlockMask[21];
   F[24] &= BlockMaskSum[0] ^ BlockMask[24];
   F[1]  &= BlockMaskSum[1] ^ BlockMask[1];
   F[4]  &= BlockMaskSum[1] ^ BlockMask[4];
   F[7]  &= BlockMaskSum[1] ^ BlockMask[7];
   F[10] &= BlockMaskSum[1] ^ BlockMask[10];
   F[13] &= BlockMaskSum[1] ^ BlockMask[13];
   F[16] &= BlockMaskSum[1] ^ BlockMask[16];
   F[19] &= BlockMaskSum[1] ^ BlockMask[19];
   F[22] &= BlockMaskSum[1] ^ BlockMask[22];
   F[25] &= BlockMaskSum[1] ^ BlockMask[25];
   F[2]  &= BlockMaskSum[2] ^ BlockMask[2];
   F[5]  &= BlockMaskSum[2] ^ BlockMask[5];
   F[8]  &= BlockMaskSum[2] ^ BlockMask[8];
   F[11] &= BlockMaskSum[2] ^ BlockMask[11];
   F[14] &= BlockMaskSum[2] ^ BlockMask[14];
   F[17] &= BlockMaskSum[2] ^ BlockMask[17];
   F[20] &= BlockMaskSum[2] ^ BlockMask[20];
   F[23] &= BlockMaskSum[2] ^ BlockMask[23];
   F[26] &= BlockMaskSum[2] ^ BlockMask[26];
}

void Guess()
{
   int Least = 9;
   for (int i = 0; i < 18; i++)
   {
      if (TblUniqFlag[U[i]])
         continue;

      G[Index].Block = i;
      if (TblNumberOne[HIGH_9_BIT(F[i])] == 2)
      {
         G[Index].Line = 2;
         goto FoundLeast;
      }
      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;
      }
   }
   for (int i = 0; i < 27; i++)
   {
      for (int j = 0; j < 3; j++)
      {
         if (U[i] & TblShiftLeft[j])
            continue;
         int NumberOne = TblNumberOne[HML_9_BIT(F[i], j)];
         if (Least > NumberOne)
         {
            G[Index].Block = i;
            G[Index].Line = j;
            if ((Least = NumberOne) == 2)
               goto FoundLeast;
         }
      }
   }
FoundLeast:
   int Left = HML_9_BIT(F[G[Index].Block], G[Index].Line);
   int Mask = Left & -Left;
   //Save Data
   G[Index].Mask = Mask;
   G[Index].Left = Left;
   for (int B = 26; B >= 0; B--)
   {
      G[Index].F[B] = CompF[B] = F[B];
      G[Index].U[B] = U[B];
   }
   F[G[Index].Block] &= TblSelfMask[TblTailZero[Mask] + TblMult9[G[Index].Line]];
   Index++;
}

bool Rollback()
{
   if (Index-- == 0)
      return false;
   //Restore Data
   for (int B = 26; B >= 0; B--)
   {
      CompF[B] = F[B] = G[Index].F[B];
      U[B] = G[Index].U[B];
   }
   G[Index].Left ^= G[Index].Mask;
   G[Index].Mask = G[Index].Left & -G[Index].Left;
   F[G[Index].Block] &= TblSelfMask[TblTailZero[G[Index].Mask] + TblMult9[G[Index].Line]];
   //Whether The Last Guess
   Index += TblNumberOne[G[Index].Left] != 1;
   return true;
}

byte Calculate()
{
   bool FoundAnswer = false;
   while (true)
   {
      if (Update())
      {
         if (U[26] + U[22] != 14 || U[25] + U[21] != 14 || U[24] + U[20] != 14
            || U[18] + U[19] + U[20] != 21 || U[15] + U[16] + U[17] != 21 || U[12] + U[13] + U[14] != 21
            || U[9] + U[10] + U[11] != 21 || U[6] + U[7] + U[8] != 21 || U[3] + U[4] + U[5] != 21)
         {
            Guess();
            continue;
         }
         if (FoundAnswer) //Find Answer
            return MoreAnswer;
         FoundAnswer = true;
      }
      if (!Rollback()) //Backtrack Over
         return FoundAnswer ? UniqAnswer : NoAnswer;
   }
}

#ifdef __ProgramWritter
void ProgramWritter()
{
   char str[256];

   FILE *fp = fopen("Update.c", "w+");
   fputs("bool Update()\n", fp);
   fputs("{\n", fp);
   fputs("\tint Shrink = ~0;\n", fp);
   fputs("\twhile (Shrink)\n", fp);
   fputs("\t{\n", fp);
   fputs("\t\tShrink = 0;\n", fp);
   for (int i = 0; i < 27; i++)
   {
      sprintf(str, "\t\tif (CompF[%d] != F[%d])\n", i, i);
      fputs(str, fp);
      fputs("\t\t{\n", fp);
      //Complex Self Method
      sprintf(str, "\t\t\tShrink = FULL_TO_SHRINK(F[%d]);\n", i);
      fputs(str, fp);
      sprintf(str, "\t\t\tif ((F[%d] &= TblComplexMask[Shrink]) == 0)\n", i);
      fputs(str, fp);
      fputs("\t\t\t\treturn false;\n", fp);
      sprintf(str, "\t\t\tCompF[%d] = F[%d];\n", i, i);
      fputs(str, fp);
      //Complex Friend Method
      sprintf(str, "\t\t\tint Column = FULL_TO_COLUMN(F[%d]);\n", i);
      fputs(str, fp);
      sprintf(str, "\t\t\tint C1 = Column | FULL_TO_COLUMN(F[%d]);\n", TblAnother1[i]);
      fputs(str, fp);
      sprintf(str, "\t\t\tint C2 = Column | FULL_TO_COLUMN(F[%d]);\n", TblAnother2[i]);
      fputs(str, fp);
      sprintf(str, "\t\t\tF[%d] &= TblMaskSingle[Column] & TblMaskDouble[C2];\n", TblAnother1[i]);
      fputs(str, fp);
      sprintf(str, "\t\t\tF[%d] &= TblMaskSingle[Column] & TblMaskDouble[C1];\n", TblAnother2[i]);
      fputs(str, fp);
      //Single Grid Method
      sprintf(str, "\t\t\tif (TblShrinkMask[TblShrinkSingle[Shrink] & TblColumnSingle[Column]] != U[%d])\n", i);
      fputs(str, fp);
      fputs("\t\t\t{\n", fp);
      sprintf(str, "\t\t\t\tU[%d] |= TblShrinkMask[TblShrinkSingle[Shrink] & TblColumnSingle[Column]];\n", i);
      fputs(str, fp);
      //Friend Block
      sprintf(str, "\t\t\t\tint S = ~(F[%d] & TblColumnMask[U[%d]]);\n", i, i);
      fputs(str, fp);
      fputs("\t\t\t\t", fp);
      for (int j = TblRmder3[i]; j < 27; j += 3)
      {
         if (j != i)
         {
            sprintf(str, "AN(F[%d], S); ", j);
            fputs(str, fp);
         }
      }
      fputs("\n", fp);
      fputs("\t\t\t}\n", fp);
      fputs("\t\t}\n", fp);
   }
   fputs("\t}\n", fp);
   fputs("\treturn true;\n", fp);
   fputs("}", fp);
   fclose(fp);
}
#endif

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

#ifdef __ProgramWritter
   ProgramWritter();
   return true;
#endif

   if (!ReadFile())
      return false;

   printf("Press Enter to Slove ...");
   getchar();

   //Set Highest Priority
   DWORD dwOldProcessP = GetPriorityClass(GetCurrentProcess());
   DWORD dwOldThreadP  = GetThreadPriority(GetCurrentThread());

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

   //Get Frequency
   LARGE_INTEGER Frequency;
   ::QueryPerformanceFrequency(&Frequency);

   //Get Start Time
   LARGE_INTEGER start;
   ::QueryPerformanceCounter(&start);

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

   //Get Stop Time
   LARGE_INTEGER stop;
   ::QueryPerformanceCounter(&stop);

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

   printf("Spend   = %f us\n", spend * 1000 * 1000);
   printf("Total   = %d\n", TestCaseNumber);
   printf("Average = %f us\n", spend * 1000 * 1000 / TestCaseNumber);
   if (Answer != UniqAnswer)
      printf("***************Result: %d   ***************\n", Answer);

   //Restore Priority
   SetThreadPriority(GetCurrentThread(), dwOldThreadP);
   SetPriorityClass(GetCurrentProcess(), dwOldProcessP);

   return true;
}

#ifdef __ProgramWritter
bool Update()
{
   return true;
}
#else
//open Update.c and copy to here
#endif
zhouyundong_2012
 
Posts: 148
Joined: 10 February 2012

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

Postby JasonLion » Sun Apr 08, 2012 2:22 pm

There seems to be a minor bug in this version. Very rarely it is counting a multi-solution puzzle as having only one solution. Here are three examples:
Code: Select all
060000092002100080007400000003026000000030604070000500200000050000005000400081000
400300600000000701000000008009050000000070050016800003005900000020500000040010026
690200040100500008300000000000730005900008000008000200000004000000009500041002007
User avatar
JasonLion
2017 Supporter
 
Posts: 642
Joined: 25 October 2007
Location: Silver Spring, MD, USA

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

Postby zhouyundong_2012 » Mon Apr 09, 2012 11:13 am

Code: Select all
         if (U[26] + U[22] != 14 || U[25] + U[21] != 14 || U[24] + U[20] != 14
            || U[18] + U[19] + U[20] != 21 || U[15] + U[16] + U[17] != 21 || U[12] + U[13] + U[14] != 21
            || U[9] + U[10] + U[11] != 21 || U[6] + U[7] + U[8] != 21 || U[3] + U[4] + U[5] != 21 || U[2] + U[1] + U[0] != 21)

|| U[2] + U[1] + U[0] != 21

You did a good test job. It is difficult to find this bug. Because I think U[2] + U[1] + U[0] must be 21,if other U are all 7. It seems that I am wrong!
So replease this three lines.
zhouyundong_2012
 
Posts: 148
Joined: 10 February 2012

ZSolve 3.82us for each 17-clues sudoku(2.8G CPU)

Postby zhouyundong_2012 » Tue Oct 23, 2012 12:29 pm

I made some improvement, from 3.97us to 3.82us.
F is 30 bits. The first 3 bits of F is U.
F 010 000111000 000100000 111010110
The Shrink of F is (T1[010000111000000] << 5) + T2[100000111010110]
zhouyundong_2012
 
Posts: 148
Joined: 10 February 2012

Re: ZSolve 3.82us for each 17-clues sudoku(2.8G CPU)

Postby zhouyundong_2012 » Tue Oct 23, 2012 12:39 pm

FULL_TO_COLLUM has no change.
((F >> 9) and (F >> 18) and F) and 0x1FF

some Tbls have changed. but Update() has no additional calculation.


Guess() has changed.
F 000 000111000 000110111 111000111
1. Left = 000 000111000 000000000 000000000
2. Mask=000 000001000 000000000 000000000
3. F = 000 000000000 000110111 111000111
4. G[0].F = 000 0000000000 000110111 111000111
5. Left = 000 000110000 000000000 000000000
1.Left = F and T3[2];
2.Mask = Left and -Left;
3.F = F ^ Left
4.G[0].F = F;
5.Left = Left ^ Mask;
zhouyundong_2012
 
Posts: 148
Joined: 10 February 2012

Re: ZSolve 3.82us for each 17-clues sudoku(2.8G CPU)

Postby zhouyundong_2012 » Tue Oct 23, 2012 12:47 pm

RollBack() has changed.
1. F = 000 000000000 000110111 111000111
2. Mask = 000 000010000 000000000 000000000
3. Left = 000 000100000 000000000 000000000
4. F = 000 000010000 000000000 000000000

1. F = G[0].F;
2. Mask = Left and -Left;
3.Left = Left ^ Mask;
4.F = F ^ Mask;

RollBack() is more efficient.
zhouyundong_2012
 
Posts: 148
Joined: 10 February 2012

Re: ZSolve 3.82us for each 17-clues sudoku(2.8G CPU)

Postby zhouyundong_2012 » Tue Oct 23, 2012 12:49 pm

I think top-1465 will get more improvement because Guess() and RollBack() execute more times.
zhouyundong_2012
 
Posts: 148
Joined: 10 February 2012

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

Postby Serg » Wed Oct 24, 2012 7:48 pm

Hi, zhouyundong_2012!
It's very likely you wrote the fastest sudoku solver. But unfortunately it is not so easy to use it (at least for me) - I read posts of other experienced people - they found problems during compilation of your program. You publish many pieces of your code. In what way they should be assembled? Can you post separate file that could be compliled without manual changing code, without compilator's complicated keys setting, etc?
Another nice variant - to post Windows 32-bit executable, that reads puzzles (in linear form) from stdin and writes solutions to stdout (it would be ideal if it can write number of solutions first (1-st output line) and then solutions in linear form.

Your solver could help me and other people in exhaustive search and solving other sudoku-concerning problems.

Serg
Serg
2018 Supporter
 
Posts: 890
Joined: 01 June 2010
Location: Russia

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

Postby zhouyundong_2012 » Sun Oct 28, 2012 4:14 am

I made an another improvement, 3.77us now.
I have written an doc to explain the details of this solver.But it is written in Chinese.
I will post the latest codes a few days later.
zhouyundong_2012
 
Posts: 148
Joined: 10 February 2012

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

Postby zhouyundong_2012 » Fri Nov 09, 2012 7:34 am

2012.11.9 Update
Code: Select all
#include <windows.h>
#include <stdio.h>
#include "ZSolver.h"

/*
 * First Step : Compile this project with __ProgramWritter used and Run it
 * Second Step: Replace the function Update in the bottom of this file with all contents of Update.c created by First Step in current directory
 * Third Step : Recompile this project without __ProgramWritter and Run it
 *
 *           Warning: Can NOT comment __ProgramWritter until finish 3 steps!
 *
 * Good Luck! Shanghai China 2012/3/14 Zhou Yun Dong
 */
//#define __ProgramWritter

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

int                 Index; //Guess Index
int                 BlockMask[27]; //Block
int                 BlockMaskSum[3]; //Sum of BlockMask
int                 F[27]; //30-bit Full Mask
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()
{
   Index = 1;
   BlockMaskSum[0] = BlockMaskSum[1] = BlockMaskSum[2] = 0;
   for (int i = 0; i < 27; i++)
   {
      CompF[i] = F[i] = BIT_SET_30;
      BlockMask[i] = 0;
   }
   //Get Full Mask
   for (int i = 80; i >= 0; i--)
   {
      if (Board[i] == '0')
         continue;

      int B = TblMult3[Board[i] - '1'] + TblBoard_Block[i];
      //Get BlockMask and Sum of BlockMask
      BlockMaskSum[TblBoard_Block[i]] |= TblBoard_BlockMask[i];
      BlockMask[B] |= TblBoard_BlockMask[i];
      //Self and Another Block
      F[B] &= TblSelfMask[i];
      F[TblAnother1[B]] &= TblOtherMask[i];
      F[TblAnother2[B]] &= TblOtherMask[i];
   }
   BlockMaskSum[0] ^= BIT_SET_30;
   BlockMaskSum[1] ^= BIT_SET_30;
   BlockMaskSum[2] ^= BIT_SET_30;
   NORF(0) NORF(3) NORF(6) NORF(9) NORF(12)NORF(15)NORF(18)NORF(21)NORF(24)
   NORF(1) NORF(4) NORF(7) NORF(10)NORF(13)NORF(16)NORF(19)NORF(22)NORF(25)
   NORF(2) NORF(5) NORF(8) NORF(11)NORF(14)NORF(17)NORF(20)NORF(23)NORF(26)
}

int T[3] = { 0x1FF, 0x3FE00, 0x7FC0000 };
void Guess()
{
   int Line;
   for (int i = 0; i < 21; i++)
   {
      if (TblUniqFlag[F[i] >> 27])
         continue;

      G[Index].Block = i;
      if (TblNumberOne[HIGH_9_BIT(F[i])] == 2)
      {
         Line = 2;
         goto FoundLeast;
      }
      if (TblNumberOne[MID_9_BIT(F[i])] == 2)
      {
         Line = 1;
         goto FoundLeast;
      }
      if (TblNumberOne[LOW_9_BIT(F[i])] == 2)
      {
         Line = 0;
         goto FoundLeast;
      }
   }
   int Least = 10;
   int NumberOne;
   for (int i = 0; i < 27; i++)
   {
      if (F[i] & 0x08000000)
      {
         NumberOne = TblNumberOne[LOW_9_BIT(F[i])];
         if (Least > NumberOne)
         {
            G[Index].Block = i;
            Line = 0;
            if ((Least = NumberOne) == 2)
               goto FoundLeast;
         }
      }
      if (F[i] & 0x10000000)
      {
         NumberOne = TblNumberOne[MID_9_BIT(F[i])];
         if (Least > NumberOne)
         {
            G[Index].Block = i;
            Line = 1;
            if ((Least = NumberOne) == 2)
               goto FoundLeast;
         }
      }
      if (F[i] & 0x20000000)
      {
         NumberOne = TblNumberOne[HIGH_9_BIT(F[i])];
         if (Least > NumberOne)
         {
            G[Index].Block = i;
            Line = 2;
            if ((Least = NumberOne) == 2)
               goto FoundLeast;
         }
      }
   }

FoundLeast:
   G[Index].Left = F[G[Index].Block] & T[Line];
   F[G[Index].Block] ^= G[Index].Left;
   //Save Data
   SAVF(0) SAVF(1) SAVF(2) SAVF(3) SAVF(4) SAVF(5) SAVF(6) SAVF(7) SAVF(8)
   SAVF(9) SAVF(10)SAVF(11)SAVF(12)SAVF(13)SAVF(14)SAVF(15)SAVF(16)SAVF(17)
   SAVF(18)SAVF(19)SAVF(20)SAVF(21)SAVF(22)SAVF(23)SAVF(24)SAVF(25)SAVF(26)
   G[Index].Mask = G[Index].Left & -G[Index].Left;
   G[Index].Left ^= G[Index].Mask;
   F[G[Index].Block] ^= G[Index].Mask;
   Index++;
}

bool Rollback()
{
   if (!--Index)
      return false;
   //Restore Data
   RESF(0) RESF(1) RESF(2) RESF(3) RESF(4) RESF(5) RESF(6) RESF(7) RESF(8)
   RESF(9) RESF(10)RESF(11)RESF(12)RESF(13)RESF(14)RESF(15)RESF(16)RESF(17)
   RESF(18)RESF(19)RESF(20)RESF(21)RESF(22)RESF(23)RESF(24)RESF(25)RESF(26)
   //Whether The Last Guess
   G[Index].Mask = G[Index].Left & -G[Index].Left;
   F[G[Index].Block] ^= G[Index].Mask;
   Index += (G[Index].Left ^= G[Index].Mask) != 0;
   return true;
}

byte Calculate()
{
   bool FoundAnswer = false;
   while (true)
   {
#ifndef __ProgramWritter
      if (Update())
#endif
      {
         if (   (F[18] | F[22] | F[26]) > BIT_SET_27
            || (F[19] | F[23] | F[24]) > BIT_SET_27
            || (F[20] | F[21] | F[25]) > BIT_SET_27
            || (F[15] | F[16] | F[17]) > BIT_SET_27
            || (F[12] | F[13] | F[14]) > BIT_SET_27
            || (F[9]  | F[10] | F[11]) > BIT_SET_27
            || (F[6]  | F[7]  | F[8] ) > BIT_SET_27
            || (F[3]  | F[4]  | F[5] ) > BIT_SET_27)
         {
            Guess();
            continue;
         }
         if (FoundAnswer) //Find Answer
            return MoreAnswer;
         FoundAnswer = true;
      }
      if (!Rollback()) //Backtrack Over
         return FoundAnswer ? UniqAnswer : NoAnswer;
   }
}

#ifdef __ProgramWritter
void ProgramWritter()
{
   char str[256];

   FILE *fp = fopen("Update.cpp", "w+");
   fputs("#include \"ZSolver.h\"\n", fp);
   fputs("\n", fp);
   fputs("\n", fp);
   fputs("bool Update()\n", fp);
   fputs("{\n", fp);
   fputs("\tint Shrink = ~0, S, C1, C2;\n", fp);
   fputs("\twhile (Shrink)\n", fp);
   fputs("\t{\n", fp);
   fputs("\t\tShrink = 0;\n", fp);
   for (int i = 0; i < 27; i++)
   {
      sprintf(str, "\t\tif (CompF[%d] != F[%d])\n", i, i);
      fputs(str, fp);
      fputs("\t\t{\n", fp);
      //Complex Self Method
      sprintf(str, "\t\t\tShrink = FULL_TO_SHRINK(F[%d]);\n", i);
      fputs(str, fp);
      sprintf(str, "\t\t\tif ((F[%d] &= TblComplexMask[Shrink]) == 0)\n", i);
      fputs(str, fp);
      fputs("\t\t\t\treturn false;\n", fp);
      //Complex Friend Method
      sprintf(str, "\t\t\tS = FULL_TO_COLUMN(F[%d]);\n", i);
      fputs(str, fp);
      sprintf(str, "\t\t\tC1 = S | FULL_TO_COLUMN(F[%d]);\n", TblAnother1[i]);
      fputs(str, fp);
      sprintf(str, "\t\t\tC2 = S | FULL_TO_COLUMN(F[%d]);\n", TblAnother2[i]);
      fputs(str, fp);
      sprintf(str, "\t\t\tF[%d] &= TblMaskSingle[S] & TblMaskDouble[C1];\n", TblAnother2[i]);
      fputs(str, fp);
      sprintf(str, "\t\t\tF[%d] &= TblMaskSingle[S] & TblMaskDouble[C2];\n", TblAnother1[i]);
      fputs(str, fp);
      //Single Grid Method
     fputs("\t\t\tS = TblRowUniq[TblShrinkSingle[Shrink] & TblColumnSingle[S]];\n", fp);
      sprintf(str, "\t\t\tif ((F[%d] >> 27) != S)\n", i, i);
      fputs(str, fp);
      fputs("\t\t\t{\n", fp);
      sprintf(str, "\t\t\t\tF[%d] &= S << 27 | BIT_SET_27;\n", i);
      fputs(str, fp);
     sprintf(str, "\t\t\t\tS = ~(F[%d] & TblRowMask[S]);\n", i, i);
     fputs(str, fp);
      fputs("\t\t\t\t", fp);
      for (int j = i % 3; j < 27; j += 3)
      {
         if (j != i)
         {
            sprintf(str, "AN(F[%d], S); ", j);
            fputs(str, fp);
         }
      }
      fputs("\n", fp);
      fputs("\t\t\t}\n", fp);
      sprintf(str, "\t\t\tCompF[%d] = F[%d];\n", i, i);
      fputs(str, fp);
      fputs("\t\t}\n", fp);
   }
   fputs("\t}\n", fp);
   fputs("\treturn true;\n", fp);
   fputs("}", fp);
   fclose(fp);
}
#endif

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

#ifdef __ProgramWritter
   ProgramWritter();
   return true;
#endif

   if (!ReadFile())
      return false;

   printf("Press Enter to Slove ...");
   getchar();

   //Set Highest Priority
   DWORD dwOldProcessP = GetPriorityClass(GetCurrentProcess());
   DWORD dwOldThreadP  = GetThreadPriority(GetCurrentThread());

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

   //Get Frequency
   LARGE_INTEGER Frequency;
   ::QueryPerformanceFrequency(&Frequency);

   //Get Start Time
   LARGE_INTEGER start;
   ::QueryPerformanceCounter(&start);

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

   //Get Stop Time
   LARGE_INTEGER stop;
   ::QueryPerformanceCounter(&stop);

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

   printf("Spend   = %f us\n", spend * 1000 * 1000);
   printf("Total   = %d\n", TestCaseNumber);
   printf("Average = %f us\n", spend * 1000 * 1000 / TestCaseNumber);
   if (Answer != UniqAnswer)
      printf("***************Result: %d   ***************\n", Answer);

   //Restore Priority
   SetThreadPriority(GetCurrentThread(), dwOldThreadP);
   SetPriorityClass(GetCurrentProcess(), dwOldProcessP);

   return true;
}
zhouyundong_2012
 
Posts: 148
Joined: 10 February 2012

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

Postby zhouyundong_2012 » Fri Nov 09, 2012 7:35 am

2012.11.9Update
Code: Select all
#ifndef __sd_h__
#define __sd_h__

typedef unsigned char       byte;

#define TotalBoard          50000 //Total Games

//Answer Attribute
#define NoAnswer            0
#define UniqAnswer          1
#define MoreAnswer          2

//High, Middle, Low 9 bit of a 27-bit number
#define HIGH_9_BIT(v)       (((v) >> 18) & 0x1FF)
#define MID_9_BIT(v)        (((v) >> 9) & 0x1FF)
#define LOW_9_BIT(v)        ((v) & 0x1FF)

#define FULL_TO_COLUMN(v)   (((v) | ((v) >> 9) | ((v) >> 18)) & 0x1FF) //Full Mask(27-bit) to 9 bit
#define FULL_TO_SHRINK(v)   ((TblShrinkMask[(v) >> 15] << 5) | TblShrinkMask[(v) & 0x7FFF]) //000 to 0, else to 1

#define BIT_SET_27          0x07FFFFFF
#define BIT_SET_30          0x3FFFFFFF
#define BIT_U_MASK          0x38000000

#define NORF(n)             F[n] &= BlockMaskSum[n%3] ^ BlockMask[n];
#define SAVF(n)             G[Index].F[n] = F[n];
#define RESF(n)             CompF[n] = F[n] = G[Index].F[n];

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

struct CGame {
  public:
   int             F[27]; //30-bit Full Mask
   int             Block; //The Block Number of guess [0, 27)
   int             Mask; //The 9-bit Mask of guess
   int             Left; //The 9-bit Left Mask of guess
};

//Common Table
extern int             TblMult3[9];
extern int             TblMult9[9];
//Basis Table
extern int             TblCombineMask[512];
extern int             TblNumberOne[512];
extern int             TblAnother1[27];
extern int             TblAnother2[27];
//Table of Decompose Board
extern int             TblBoard_Block[81];
extern int             TblBoard_BlockMask[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             TblRowMask[8];
extern bool            TblUniqFlag[8];
//Complex Method
extern byte            TblShrinkMask[32768];
extern int             TblRowUniq[512];
extern int             TblComplexMask[1024];
extern int             TblColumnSingle[512];
extern int             TblShrinkSingle[1024];

extern int             F[27]; //30-bit Full Mask
extern int             CompF[27]; //Use for Compare

extern void            CreateTable();

#endif
zhouyundong_2012
 
Posts: 148
Joined: 10 February 2012

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

Postby zhouyundong_2012 » Fri Nov 09, 2012 7:35 am

2012.11.9Update
Code: Select all
#include <string.h>
#include "ZSolver.h"

//Common Table
int                   TblMult3[9];
int                   TblMult9[9];
//Basis Table
int                   TblCombineMask[512];
int                   TblNumberOne[512];
int                   TblAnother1[27];
int                   TblAnother2[27];
//Table of Decompose Board
int                   TblBoard_Block[81];
int                   TblBoard_BlockMask[81];
//Table of Initial
int                   TblSelfMask[81];
int                   TblOtherMask[81];
//Complex Friend Method
int                   TblMaskSingle[512];
int                   TblMaskDouble[512];
//Other Table
int                   TblRowMask[8];
bool                  TblUniqFlag[8];
//Complex Method
byte                  TblShrinkMask[32768];
int                   TblRowUniq[512];
int                   TblComplexMask[1024];
int                   TblColumnSingle[512];
int                   TblShrinkSingle[1024];


void CreateTblCommon()
{
   for (int i = 0; i < 9; i++)
   {      
      TblMult3[i] = i * 3;
      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 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 CreateTblBasis()
{
   CreateTblCombineMask();
   CreateTblAnother();
   CreateTblNumberOne();
}

void CreateTblBoard()
{
   for (int i = 0; i < 81; i++)
   {
      TblBoard_Block[i] = i / 27;
      TblBoard_BlockMask[i] = 1 << i % 27;
   }
}

void CreateTblSelfMask()
{
   int Mask[3] = { 0x7E3F1F8, 0x71F8FC7, 0x0FC7E3F };
   int Row[3] = { 0x7FFFE00, 0x7FC01FF, 0x3FFFF };
   int Uniq[3] = { 0x30000000, 0x28000000, 0x18000000 };
   for (int i = 0; i < 81; i++)
   {
      int Palace = i % 9 / 3;
      int Line = i % 27 / 9;
      TblSelfMask[i] = Mask[Palace] & Row[Line] | TblBoard_BlockMask[i] | Uniq[Line];
   }
}

void CreateTblOtherMask()
{
   for (int i = 0; i < 81; i++)
      TblOtherMask[i] = TblCombineMask[1 << i % 9] | BIT_U_MASK;
}

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]] | BIT_U_MASK;
   }
}

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]] | BIT_U_MASK;
   }
}

void CreateTblRowMask()
{
   memset(TblRowMask, 0, sizeof(TblRowMask));
   for (int i = 0; i < 8; i++)
   {
      for (int j = 0; j < 3; j++)
      {
         if ((i & (1 << j)) == 0)
            TblRowMask[i] |= 0x1FF << TblMult9[j];
      }
   }
}

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

void CreateTblShrinkMask()
{
   memset(TblShrinkMask, 0, sizeof(TblShrinkMask));
   for (int i = 0; i < 32768; i++)
   {
      TblShrinkMask[i] |= i & 0x7000 ? 16 : 0;
      TblShrinkMask[i] |= i & 0xE00 ? 8 : 0;
      TblShrinkMask[i] |= i & 0x1C0 ? 4 : 0;
      TblShrinkMask[i] |= i & 0x38 ? 2 : 0;
      TblShrinkMask[i] |= i & 0x7 ? 1 : 0;
   }
}

void CreateTblRowUniq()
{
   for (int i = 0; i < 512; i++)
   {
      TblRowUniq[i] |= i & 0x1C0 ? 4 : 0;
      TblRowUniq[i] |= i & 0x38 ? 2 : 0;
      TblRowUniq[i] |= i & 0x7 ? 1 : 0;
      TblRowUniq[i] = 7 - TblRowUniq[i];
   }
}

void CreateTblComplexMask()
{
   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 Candidates
      for (int j = 0; j < 3; j++)
      {
         for (int k = 0; k < 3; k++)
         {
            index = k * 3 + j;
            if ((i & (1 << index)) && !(i & (1 << (TblAnother1[k] * 3 + j))) && !(i & (1 << (TblAnother2[k] * 3 + j))))
               TblComplexMask[i] &= MaskH[index]; //Horizontal
            index = j * 3 + 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_30;
      else
         TblComplexMask[i] |= BIT_U_MASK;
   }
   for (int i = 512; i < 1024; i++)
      TblComplexMask[i] = TblComplexMask[i & 0x1FF];
}

void CreateTblColumnSingle()
{
   memset(TblColumnSingle, 0, sizeof(TblColumnSingle));
   for (int i = 0; i < 512; i++)
   {
      if (TblNumberOne[i & 0x7] == 0 || TblNumberOne[i & 0x38] == 0 || TblNumberOne[i & 0x1C0] == 0)
         continue;
      if (TblNumberOne[i & 0x7] == 1) //Low 3 bit
         TblColumnSingle[i] |= 0x49;
      if (TblNumberOne[i & 0x38] == 1) //Middle 3 bit
         TblColumnSingle[i] |= 0x92;
      if (TblNumberOne[i & 0x1C0] == 1) //High 3 bit
         TblColumnSingle[i] |= 0x124;
   }
}

void CreateTblShrinkSingle()
{
   for (int i = 0; i < 512; i++)
   {
      int j = i & FULL_TO_SHRINK(TblComplexMask[i]);
      TblShrinkSingle[i] = j;
      if (TblNumberOne[j & 0x7] != 1) //Low 3 bit
         TblShrinkSingle[i] &= 0x1F8;
      if (TblNumberOne[j & 0x38] != 1) //Middle 3 bit
         TblShrinkSingle[i] &= 0x1C7;
      if (TblNumberOne[j & 0x1C0] != 1) //High 3 bit
         TblShrinkSingle[i] &= 0x3F;
   }
   for (int i = 512; i < 1024; i++)
      TblShrinkSingle[i] = TblShrinkSingle[i & 0x1FF];
}

void CreateTable()
{
   CreateTblCommon();
   CreateTblBasis();
   CreateTblBoard();
   CreateTblSelfMask();
   CreateTblOtherMask();
   CreateTblMaskSingle();
   CreateTblMaskDouble();
   CreateTblRowMask();
   CreateTblUniqFlag();
   CreateTblShrinkMask();
   CreateTblRowUniq();
   CreateTblComplexMask();
   CreateTblColumnSingle();
   CreateTblShrinkSingle();
}
zhouyundong_2012
 
Posts: 148
Joined: 10 February 2012

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

Postby zhouyundong_2012 » Fri Nov 09, 2012 7:36 am

2012.11.9Update
Code: Select all
#include "ZSolver.h"


bool Update()
{
   int Shrink = ~0, S, C1, C2;
   while (Shrink)
   {
      Shrink = 0;
      if (CompF[0] != F[0])
      {
         Shrink = FULL_TO_SHRINK(F[0]);
         if ((F[0] &= TblComplexMask[Shrink]) == 0)
            return false;
         S = FULL_TO_COLUMN(F[0]);
         C1 = S | FULL_TO_COLUMN(F[1]);
         C2 = S | FULL_TO_COLUMN(F[2]);
         F[2] &= TblMaskSingle[S] & TblMaskDouble[C1];
         F[1] &= TblMaskSingle[S] & TblMaskDouble[C2];
         S = TblRowUniq[TblShrinkSingle[Shrink] & TblColumnSingle[S]];
         if ((F[0] >> 27) != S)
         {
            F[0] &= S << 27 | BIT_SET_27;
            S = ~(F[0] & TblRowMask[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);
         }
         CompF[0] = F[0];
      }
      if (CompF[1] != F[1])
      {
         Shrink = FULL_TO_SHRINK(F[1]);
         if ((F[1] &= TblComplexMask[Shrink]) == 0)
            return false;
         S = FULL_TO_COLUMN(F[1]);
         C1 = S | FULL_TO_COLUMN(F[0]);
         C2 = S | FULL_TO_COLUMN(F[2]);
         F[2] &= TblMaskSingle[S] & TblMaskDouble[C1];
         F[0] &= TblMaskSingle[S] & TblMaskDouble[C2];
         S = TblRowUniq[TblShrinkSingle[Shrink] & TblColumnSingle[S]];
         if ((F[1] >> 27) != S)
         {
            F[1] &= S << 27 | BIT_SET_27;
            S = ~(F[1] & TblRowMask[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);
         }
         CompF[1] = F[1];
      }
      if (CompF[2] != F[2])
      {
         Shrink = FULL_TO_SHRINK(F[2]);
         if ((F[2] &= TblComplexMask[Shrink]) == 0)
            return false;
         S = FULL_TO_COLUMN(F[2]);
         C1 = S | FULL_TO_COLUMN(F[0]);
         C2 = S | FULL_TO_COLUMN(F[1]);
         F[1] &= TblMaskSingle[S] & TblMaskDouble[C1];
         F[0] &= TblMaskSingle[S] & TblMaskDouble[C2];
         S = TblRowUniq[TblShrinkSingle[Shrink] & TblColumnSingle[S]];
         if ((F[2] >> 27) != S)
         {
            F[2] &= S << 27 | BIT_SET_27;
            S = ~(F[2] & TblRowMask[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);
         }
         CompF[2] = F[2];
      }
      if (CompF[3] != F[3])
      {
         Shrink = FULL_TO_SHRINK(F[3]);
         if ((F[3] &= TblComplexMask[Shrink]) == 0)
            return false;
         S = FULL_TO_COLUMN(F[3]);
         C1 = S | FULL_TO_COLUMN(F[4]);
         C2 = S | FULL_TO_COLUMN(F[5]);
         F[5] &= TblMaskSingle[S] & TblMaskDouble[C1];
         F[4] &= TblMaskSingle[S] & TblMaskDouble[C2];
         S = TblRowUniq[TblShrinkSingle[Shrink] & TblColumnSingle[S]];
         if ((F[3] >> 27) != S)
         {
            F[3] &= S << 27 | BIT_SET_27;
            S = ~(F[3] & TblRowMask[S]);
            AN(F[0], S); AN(F[6], S); AN(F[9], S); AN(F[12], S); AN(F[15], S); AN(F[18], S); AN(F[21], S); AN(F[24], S);
         }
         CompF[3] = F[3];
      }
      if (CompF[4] != F[4])
      {
         Shrink = FULL_TO_SHRINK(F[4]);
         if ((F[4] &= TblComplexMask[Shrink]) == 0)
            return false;
         S = FULL_TO_COLUMN(F[4]);
         C1 = S | FULL_TO_COLUMN(F[3]);
         C2 = S | FULL_TO_COLUMN(F[5]);
         F[5] &= TblMaskSingle[S] & TblMaskDouble[C1];
         F[3] &= TblMaskSingle[S] & TblMaskDouble[C2];
         S = TblRowUniq[TblShrinkSingle[Shrink] & TblColumnSingle[S]];
         if ((F[4] >> 27) != S)
         {
            F[4] &= S << 27 | BIT_SET_27;
            S = ~(F[4] & TblRowMask[S]);
            AN(F[1], S); AN(F[7], S); AN(F[10], S); AN(F[13], S); AN(F[16], S); AN(F[19], S); AN(F[22], S); AN(F[25], S);
         }
         CompF[4] = F[4];
      }
      if (CompF[5] != F[5])
      {
         Shrink = FULL_TO_SHRINK(F[5]);
         if ((F[5] &= TblComplexMask[Shrink]) == 0)
            return false;
         S = FULL_TO_COLUMN(F[5]);
         C1 = S | FULL_TO_COLUMN(F[3]);
         C2 = S | FULL_TO_COLUMN(F[4]);
         F[4] &= TblMaskSingle[S] & TblMaskDouble[C1];
         F[3] &= TblMaskSingle[S] & TblMaskDouble[C2];
         S = TblRowUniq[TblShrinkSingle[Shrink] & TblColumnSingle[S]];
         if ((F[5] >> 27) != S)
         {
            F[5] &= S << 27 | BIT_SET_27;
            S = ~(F[5] & TblRowMask[S]);
            AN(F[2], S); AN(F[8], S); AN(F[11], S); AN(F[14], S); AN(F[17], S); AN(F[20], S); AN(F[23], S); AN(F[26], S);
         }
         CompF[5] = F[5];
      }
      if (CompF[6] != F[6])
      {
         Shrink = FULL_TO_SHRINK(F[6]);
         if ((F[6] &= TblComplexMask[Shrink]) == 0)
            return false;
         S = FULL_TO_COLUMN(F[6]);
         C1 = S | FULL_TO_COLUMN(F[7]);
         C2 = S | FULL_TO_COLUMN(F[8]);
         F[8] &= TblMaskSingle[S] & TblMaskDouble[C1];
         F[7] &= TblMaskSingle[S] & TblMaskDouble[C2];
         S = TblRowUniq[TblShrinkSingle[Shrink] & TblColumnSingle[S]];
         if ((F[6] >> 27) != S)
         {
            F[6] &= S << 27 | BIT_SET_27;
            S = ~(F[6] & TblRowMask[S]);
            AN(F[0], S); AN(F[3], S); AN(F[9], S); AN(F[12], S); AN(F[15], S); AN(F[18], S); AN(F[21], S); AN(F[24], S);
         }
         CompF[6] = F[6];
      }
      if (CompF[7] != F[7])
      {
         Shrink = FULL_TO_SHRINK(F[7]);
         if ((F[7] &= TblComplexMask[Shrink]) == 0)
            return false;
         S = FULL_TO_COLUMN(F[7]);
         C1 = S | FULL_TO_COLUMN(F[6]);
         C2 = S | FULL_TO_COLUMN(F[8]);
         F[8] &= TblMaskSingle[S] & TblMaskDouble[C1];
         F[6] &= TblMaskSingle[S] & TblMaskDouble[C2];
         S = TblRowUniq[TblShrinkSingle[Shrink] & TblColumnSingle[S]];
         if ((F[7] >> 27) != S)
         {
            F[7] &= S << 27 | BIT_SET_27;
            S = ~(F[7] & TblRowMask[S]);
            AN(F[1], S); AN(F[4], S); AN(F[10], S); AN(F[13], S); AN(F[16], S); AN(F[19], S); AN(F[22], S); AN(F[25], S);
         }
         CompF[7] = F[7];
      }
      if (CompF[8] != F[8])
      {
         Shrink = FULL_TO_SHRINK(F[8]);
         if ((F[8] &= TblComplexMask[Shrink]) == 0)
            return false;
         S = FULL_TO_COLUMN(F[8]);
         C1 = S | FULL_TO_COLUMN(F[6]);
         C2 = S | FULL_TO_COLUMN(F[7]);
         F[7] &= TblMaskSingle[S] & TblMaskDouble[C1];
         F[6] &= TblMaskSingle[S] & TblMaskDouble[C2];
         S = TblRowUniq[TblShrinkSingle[Shrink] & TblColumnSingle[S]];
         if ((F[8] >> 27) != S)
         {
            F[8] &= S << 27 | BIT_SET_27;
            S = ~(F[8] & TblRowMask[S]);
            AN(F[2], S); AN(F[5], S); AN(F[11], S); AN(F[14], S); AN(F[17], S); AN(F[20], S); AN(F[23], S); AN(F[26], S);
         }
         CompF[8] = F[8];
      }
      if (CompF[9] != F[9])
      {
         Shrink = FULL_TO_SHRINK(F[9]);
         if ((F[9] &= TblComplexMask[Shrink]) == 0)
            return false;
         S = FULL_TO_COLUMN(F[9]);
         C1 = S | FULL_TO_COLUMN(F[10]);
         C2 = S | FULL_TO_COLUMN(F[11]);
         F[11] &= TblMaskSingle[S] & TblMaskDouble[C1];
         F[10] &= TblMaskSingle[S] & TblMaskDouble[C2];
         S = TblRowUniq[TblShrinkSingle[Shrink] & TblColumnSingle[S]];
         if ((F[9] >> 27) != S)
         {
            F[9] &= S << 27 | BIT_SET_27;
            S = ~(F[9] & TblRowMask[S]);
            AN(F[0], S); AN(F[3], S); AN(F[6], S); AN(F[12], S); AN(F[15], S); AN(F[18], S); AN(F[21], S); AN(F[24], S);
         }
         CompF[9] = F[9];
      }
      if (CompF[10] != F[10])
      {
         Shrink = FULL_TO_SHRINK(F[10]);
         if ((F[10] &= TblComplexMask[Shrink]) == 0)
            return false;
         S = FULL_TO_COLUMN(F[10]);
         C1 = S | FULL_TO_COLUMN(F[9]);
         C2 = S | FULL_TO_COLUMN(F[11]);
         F[11] &= TblMaskSingle[S] & TblMaskDouble[C1];
         F[9] &= TblMaskSingle[S] & TblMaskDouble[C2];
         S = TblRowUniq[TblShrinkSingle[Shrink] & TblColumnSingle[S]];
         if ((F[10] >> 27) != S)
         {
            F[10] &= S << 27 | BIT_SET_27;
            S = ~(F[10] & TblRowMask[S]);
            AN(F[1], S); AN(F[4], S); AN(F[7], S); AN(F[13], S); AN(F[16], S); AN(F[19], S); AN(F[22], S); AN(F[25], S);
         }
         CompF[10] = F[10];
      }
      if (CompF[11] != F[11])
      {
         Shrink = FULL_TO_SHRINK(F[11]);
         if ((F[11] &= TblComplexMask[Shrink]) == 0)
            return false;
         S = FULL_TO_COLUMN(F[11]);
         C1 = S | FULL_TO_COLUMN(F[9]);
         C2 = S | FULL_TO_COLUMN(F[10]);
         F[10] &= TblMaskSingle[S] & TblMaskDouble[C1];
         F[9] &= TblMaskSingle[S] & TblMaskDouble[C2];
         S = TblRowUniq[TblShrinkSingle[Shrink] & TblColumnSingle[S]];
         if ((F[11] >> 27) != S)
         {
            F[11] &= S << 27 | BIT_SET_27;
            S = ~(F[11] & TblRowMask[S]);
            AN(F[2], S); AN(F[5], S); AN(F[8], S); AN(F[14], S); AN(F[17], S); AN(F[20], S); AN(F[23], S); AN(F[26], S);
         }
         CompF[11] = F[11];
      }
      if (CompF[12] != F[12])
      {
         Shrink = FULL_TO_SHRINK(F[12]);
         if ((F[12] &= TblComplexMask[Shrink]) == 0)
            return false;
         S = FULL_TO_COLUMN(F[12]);
         C1 = S | FULL_TO_COLUMN(F[13]);
         C2 = S | FULL_TO_COLUMN(F[14]);
         F[14] &= TblMaskSingle[S] & TblMaskDouble[C1];
         F[13] &= TblMaskSingle[S] & TblMaskDouble[C2];
         S = TblRowUniq[TblShrinkSingle[Shrink] & TblColumnSingle[S]];
         if ((F[12] >> 27) != S)
         {
            F[12] &= S << 27 | BIT_SET_27;
            S = ~(F[12] & TblRowMask[S]);
            AN(F[0], S); AN(F[3], S); AN(F[6], S); AN(F[9], S); AN(F[15], S); AN(F[18], S); AN(F[21], S); AN(F[24], S);
         }
         CompF[12] = F[12];
      }
      if (CompF[13] != F[13])
      {
         Shrink = FULL_TO_SHRINK(F[13]);
         if ((F[13] &= TblComplexMask[Shrink]) == 0)
            return false;
         S = FULL_TO_COLUMN(F[13]);
         C1 = S | FULL_TO_COLUMN(F[12]);
         C2 = S | FULL_TO_COLUMN(F[14]);
         F[14] &= TblMaskSingle[S] & TblMaskDouble[C1];
         F[12] &= TblMaskSingle[S] & TblMaskDouble[C2];
         S = TblRowUniq[TblShrinkSingle[Shrink] & TblColumnSingle[S]];
         if ((F[13] >> 27) != S)
         {
            F[13] &= S << 27 | BIT_SET_27;
            S = ~(F[13] & TblRowMask[S]);
            AN(F[1], S); AN(F[4], S); AN(F[7], S); AN(F[10], S); AN(F[16], S); AN(F[19], S); AN(F[22], S); AN(F[25], S);
         }
         CompF[13] = F[13];
      }
      if (CompF[14] != F[14])
      {
         Shrink = FULL_TO_SHRINK(F[14]);
         if ((F[14] &= TblComplexMask[Shrink]) == 0)
            return false;
         S = FULL_TO_COLUMN(F[14]);
         C1 = S | FULL_TO_COLUMN(F[12]);
         C2 = S | FULL_TO_COLUMN(F[13]);
         F[13] &= TblMaskSingle[S] & TblMaskDouble[C1];
         F[12] &= TblMaskSingle[S] & TblMaskDouble[C2];
         S = TblRowUniq[TblShrinkSingle[Shrink] & TblColumnSingle[S]];
         if ((F[14] >> 27) != S)
         {
            F[14] &= S << 27 | BIT_SET_27;
            S = ~(F[14] & TblRowMask[S]);
            AN(F[2], S); AN(F[5], S); AN(F[8], S); AN(F[11], S); AN(F[17], S); AN(F[20], S); AN(F[23], S); AN(F[26], S);
         }
         CompF[14] = F[14];
      }
      if (CompF[15] != F[15])
      {
         Shrink = FULL_TO_SHRINK(F[15]);
         if ((F[15] &= TblComplexMask[Shrink]) == 0)
            return false;
         S = FULL_TO_COLUMN(F[15]);
         C1 = S | FULL_TO_COLUMN(F[16]);
         C2 = S | FULL_TO_COLUMN(F[17]);
         F[17] &= TblMaskSingle[S] & TblMaskDouble[C1];
         F[16] &= TblMaskSingle[S] & TblMaskDouble[C2];
         S = TblRowUniq[TblShrinkSingle[Shrink] & TblColumnSingle[S]];
         if ((F[15] >> 27) != S)
         {
            F[15] &= S << 27 | BIT_SET_27;
            S = ~(F[15] & TblRowMask[S]);
            AN(F[0], S); AN(F[3], S); AN(F[6], S); AN(F[9], S); AN(F[12], S); AN(F[18], S); AN(F[21], S); AN(F[24], S);
         }
         CompF[15] = F[15];
      }
      if (CompF[16] != F[16])
      {
         Shrink = FULL_TO_SHRINK(F[16]);
         if ((F[16] &= TblComplexMask[Shrink]) == 0)
            return false;
         S = FULL_TO_COLUMN(F[16]);
         C1 = S | FULL_TO_COLUMN(F[15]);
         C2 = S | FULL_TO_COLUMN(F[17]);
         F[17] &= TblMaskSingle[S] & TblMaskDouble[C1];
         F[15] &= TblMaskSingle[S] & TblMaskDouble[C2];
         S = TblRowUniq[TblShrinkSingle[Shrink] & TblColumnSingle[S]];
         if ((F[16] >> 27) != S)
         {
            F[16] &= S << 27 | BIT_SET_27;
            S = ~(F[16] & TblRowMask[S]);
            AN(F[1], S); AN(F[4], S); AN(F[7], S); AN(F[10], S); AN(F[13], S); AN(F[19], S); AN(F[22], S); AN(F[25], S);
         }
         CompF[16] = F[16];
      }
      if (CompF[17] != F[17])
      {
         Shrink = FULL_TO_SHRINK(F[17]);
         if ((F[17] &= TblComplexMask[Shrink]) == 0)
            return false;
         S = FULL_TO_COLUMN(F[17]);
         C1 = S | FULL_TO_COLUMN(F[15]);
         C2 = S | FULL_TO_COLUMN(F[16]);
         F[16] &= TblMaskSingle[S] & TblMaskDouble[C1];
         F[15] &= TblMaskSingle[S] & TblMaskDouble[C2];
         S = TblRowUniq[TblShrinkSingle[Shrink] & TblColumnSingle[S]];
         if ((F[17] >> 27) != S)
         {
            F[17] &= S << 27 | BIT_SET_27;
            S = ~(F[17] & TblRowMask[S]);
            AN(F[2], S); AN(F[5], S); AN(F[8], S); AN(F[11], S); AN(F[14], S); AN(F[20], S); AN(F[23], S); AN(F[26], S);
         }
         CompF[17] = F[17];
      }
      if (CompF[18] != F[18])
      {
         Shrink = FULL_TO_SHRINK(F[18]);
         if ((F[18] &= TblComplexMask[Shrink]) == 0)
            return false;
         S = FULL_TO_COLUMN(F[18]);
         C1 = S | FULL_TO_COLUMN(F[19]);
         C2 = S | FULL_TO_COLUMN(F[20]);
         F[20] &= TblMaskSingle[S] & TblMaskDouble[C1];
         F[19] &= TblMaskSingle[S] & TblMaskDouble[C2];
         S = TblRowUniq[TblShrinkSingle[Shrink] & TblColumnSingle[S]];
         if ((F[18] >> 27) != S)
         {
            F[18] &= S << 27 | BIT_SET_27;
            S = ~(F[18] & TblRowMask[S]);
            AN(F[0], S); AN(F[3], S); AN(F[6], S); AN(F[9], S); AN(F[12], S); AN(F[15], S); AN(F[21], S); AN(F[24], S);
         }
         CompF[18] = F[18];
      }
      if (CompF[19] != F[19])
      {
         Shrink = FULL_TO_SHRINK(F[19]);
         if ((F[19] &= TblComplexMask[Shrink]) == 0)
            return false;
         S = FULL_TO_COLUMN(F[19]);
         C1 = S | FULL_TO_COLUMN(F[18]);
         C2 = S | FULL_TO_COLUMN(F[20]);
         F[20] &= TblMaskSingle[S] & TblMaskDouble[C1];
         F[18] &= TblMaskSingle[S] & TblMaskDouble[C2];
         S = TblRowUniq[TblShrinkSingle[Shrink] & TblColumnSingle[S]];
         if ((F[19] >> 27) != S)
         {
            F[19] &= S << 27 | BIT_SET_27;
            S = ~(F[19] & TblRowMask[S]);
            AN(F[1], S); AN(F[4], S); AN(F[7], S); AN(F[10], S); AN(F[13], S); AN(F[16], S); AN(F[22], S); AN(F[25], S);
         }
         CompF[19] = F[19];
      }
      if (CompF[20] != F[20])
      {
         Shrink = FULL_TO_SHRINK(F[20]);
         if ((F[20] &= TblComplexMask[Shrink]) == 0)
            return false;
         S = FULL_TO_COLUMN(F[20]);
         C1 = S | FULL_TO_COLUMN(F[18]);
         C2 = S | FULL_TO_COLUMN(F[19]);
         F[19] &= TblMaskSingle[S] & TblMaskDouble[C1];
         F[18] &= TblMaskSingle[S] & TblMaskDouble[C2];
         S = TblRowUniq[TblShrinkSingle[Shrink] & TblColumnSingle[S]];
         if ((F[20] >> 27) != S)
         {
            F[20] &= S << 27 | BIT_SET_27;
            S = ~(F[20] & TblRowMask[S]);
            AN(F[2], S); AN(F[5], S); AN(F[8], S); AN(F[11], S); AN(F[14], S); AN(F[17], S); AN(F[23], S); AN(F[26], S);
         }
         CompF[20] = F[20];
      }
      if (CompF[21] != F[21])
      {
         Shrink = FULL_TO_SHRINK(F[21]);
         if ((F[21] &= TblComplexMask[Shrink]) == 0)
            return false;
         S = FULL_TO_COLUMN(F[21]);
         C1 = S | FULL_TO_COLUMN(F[22]);
         C2 = S | FULL_TO_COLUMN(F[23]);
         F[23] &= TblMaskSingle[S] & TblMaskDouble[C1];
         F[22] &= TblMaskSingle[S] & TblMaskDouble[C2];
         S = TblRowUniq[TblShrinkSingle[Shrink] & TblColumnSingle[S]];
         if ((F[21] >> 27) != S)
         {
            F[21] &= S << 27 | BIT_SET_27;
            S = ~(F[21] & TblRowMask[S]);
            AN(F[0], S); AN(F[3], S); AN(F[6], S); AN(F[9], S); AN(F[12], S); AN(F[15], S); AN(F[18], S); AN(F[24], S);
         }
         CompF[21] = F[21];
      }
      if (CompF[22] != F[22])
      {
         Shrink = FULL_TO_SHRINK(F[22]);
         if ((F[22] &= TblComplexMask[Shrink]) == 0)
            return false;
         S = FULL_TO_COLUMN(F[22]);
         C1 = S | FULL_TO_COLUMN(F[21]);
         C2 = S | FULL_TO_COLUMN(F[23]);
         F[23] &= TblMaskSingle[S] & TblMaskDouble[C1];
         F[21] &= TblMaskSingle[S] & TblMaskDouble[C2];
         S = TblRowUniq[TblShrinkSingle[Shrink] & TblColumnSingle[S]];
         if ((F[22] >> 27) != S)
         {
            F[22] &= S << 27 | BIT_SET_27;
            S = ~(F[22] & TblRowMask[S]);
            AN(F[1], S); AN(F[4], S); AN(F[7], S); AN(F[10], S); AN(F[13], S); AN(F[16], S); AN(F[19], S); AN(F[25], S);
         }
         CompF[22] = F[22];
      }
      if (CompF[23] != F[23])
      {
         Shrink = FULL_TO_SHRINK(F[23]);
         if ((F[23] &= TblComplexMask[Shrink]) == 0)
            return false;
         S = FULL_TO_COLUMN(F[23]);
         C1 = S | FULL_TO_COLUMN(F[21]);
         C2 = S | FULL_TO_COLUMN(F[22]);
         F[22] &= TblMaskSingle[S] & TblMaskDouble[C1];
         F[21] &= TblMaskSingle[S] & TblMaskDouble[C2];
         S = TblRowUniq[TblShrinkSingle[Shrink] & TblColumnSingle[S]];
         if ((F[23] >> 27) != S)
         {
            F[23] &= S << 27 | BIT_SET_27;
            S = ~(F[23] & TblRowMask[S]);
            AN(F[2], S); AN(F[5], S); AN(F[8], S); AN(F[11], S); AN(F[14], S); AN(F[17], S); AN(F[20], S); AN(F[26], S);
         }
         CompF[23] = F[23];
      }
      if (CompF[24] != F[24])
      {
         Shrink = FULL_TO_SHRINK(F[24]);
         if ((F[24] &= TblComplexMask[Shrink]) == 0)
            return false;
         S = FULL_TO_COLUMN(F[24]);
         C1 = S | FULL_TO_COLUMN(F[25]);
         C2 = S | FULL_TO_COLUMN(F[26]);
         F[26] &= TblMaskSingle[S] & TblMaskDouble[C1];
         F[25] &= TblMaskSingle[S] & TblMaskDouble[C2];
         S = TblRowUniq[TblShrinkSingle[Shrink] & TblColumnSingle[S]];
         if ((F[24] >> 27) != S)
         {
            F[24] &= S << 27 | BIT_SET_27;
            S = ~(F[24] & TblRowMask[S]);
            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);
         }
         CompF[24] = F[24];
      }
      if (CompF[25] != F[25])
      {
         Shrink = FULL_TO_SHRINK(F[25]);
         if ((F[25] &= TblComplexMask[Shrink]) == 0)
            return false;
         S = FULL_TO_COLUMN(F[25]);
         C1 = S | FULL_TO_COLUMN(F[24]);
         C2 = S | FULL_TO_COLUMN(F[26]);
         F[26] &= TblMaskSingle[S] & TblMaskDouble[C1];
         F[24] &= TblMaskSingle[S] & TblMaskDouble[C2];
         S = TblRowUniq[TblShrinkSingle[Shrink] & TblColumnSingle[S]];
         if ((F[25] >> 27) != S)
         {
            F[25] &= S << 27 | BIT_SET_27;
            S = ~(F[25] & TblRowMask[S]);
            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);
         }
         CompF[25] = F[25];
      }
      if (CompF[26] != F[26])
      {
         Shrink = FULL_TO_SHRINK(F[26]);
         if ((F[26] &= TblComplexMask[Shrink]) == 0)
            return false;
         S = FULL_TO_COLUMN(F[26]);
         C1 = S | FULL_TO_COLUMN(F[24]);
         C2 = S | FULL_TO_COLUMN(F[25]);
         F[25] &= TblMaskSingle[S] & TblMaskDouble[C1];
         F[24] &= TblMaskSingle[S] & TblMaskDouble[C2];
         S = TblRowUniq[TblShrinkSingle[Shrink] & TblColumnSingle[S]];
         if ((F[26] >> 27) != S)
         {
            F[26] &= S << 27 | BIT_SET_27;
            S = ~(F[26] & TblRowMask[S]);
            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);
         }
         CompF[26] = F[26];
      }
   }
   return true;
}
zhouyundong_2012
 
Posts: 148
Joined: 10 February 2012

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

Postby JasonLion » Fri Nov 09, 2012 2:33 pm

I got two compile errors, both fairly easily fixed.

In Guess(), I moved
Code: Select all
   int Least = 10;
   int NumberOne;
up to the top of the function to avoid errors about jumping over the declarations.

In CreateTblSelfMask(), I added parentheses around the & expression to avoid a warning
Code: Select all
      TblSelfMask[i] = (Mask[Palace] & Row[Line]) | TblBoard_BlockMask[i] | Uniq[Line];
User avatar
JasonLion
2017 Supporter
 
Posts: 642
Joined: 25 October 2007
Location: Silver Spring, MD, USA

PreviousNext

Return to Software

cron