The New Sudoku Players' Forum

by **zhouyundong_2012** » Fri Feb 17, 2012 11:16 am

I made another improvement. it will improve 10% for 17sodoku, and 3% for top50000, and ? for 2465.

by **zhouyundong_2012** » Fri Feb 17, 2012 4:30 pm

Code: Select all: #ifndef __sd_h__ #define __sd_h__ typedef unsigned char byte; typedef unsigned short word; #define TotalBoard 50000 //Total Games //Answer Attribute #define NoAnswer 0 #define UniqAnswer 1 #define MoreAnswer 2 //High, Middle, Low 9 bit of a 27-bit number #define HIGH_9_BIT(v) (v) >> 18 #define MID_9_BIT(v) ((v) >> 9) & 0x1FF #define LOW_9_BIT(v) (v) & 0x1FF #define HML_9_BIT(v, l) (v) >> TblMult9[l] & 0x1FF #define FULL_TO_COLUMN(v) ((v) | ((v) >> 9) | ((v) >> 18)) & 0x1FF //Full Mask(27-bit) to 9 bit #define FULL_TO_PALACE(v) ((v) | ((v) >> 6) | ((v) >> 12)) & 0x1FF //Full Mask(27-bit) to 9 bit, x-- y-- z-- #define BIT_SET_27 0x07FFFFFF #define AN(v, n) (v) &= ~(n) struct CGame { public: int Finish; //27-bit Finish Bitmap int F[27]; //27-bit Full Mask byte U[27]; //3-bit Unique in Palace byte Block; //The Block Number of guess [0, 27) byte Line; //The Line Number of guess [0, 3) word Mask; //The 9-bit Mask of guess word Left; //The 9-bit Left Mask of guess }; //Common Table extern int TblMult3[81]; extern int TblDivide3[81]; extern int TblRmder3[81]; extern int TblMult9[9]; //Basis Table extern int TblCombineMask[512]; extern int TblTailZero[512]; extern int TblNumberOne[512]; extern int TblAnother1[27]; extern int TblAnother2[27]; extern int TblShiftLeft[27]; //Table of Decompose Board extern int TblBoard_Palace[81]; extern int TblBoard_Block[81]; extern int TblBoard_BlockMask[81]; extern int TblBoard_GridUniq[81]; //Table of Initial extern int TblSelfMask[81]; extern int TblOtherMask[81]; //Single Row Method extern int TblSingleRow[12]; extern int TblRowNumber[512]; //Single Column Method extern int TblMaskSingle[512]; //Double Column Method extern int TblMaskDouble[512]; //Confirm Row Method extern int TblConfirmRow[12]; //Other Table extern int TblPalaceMask[3]; extern int TblStrange[27]; extern int TblChangeMask[27]; extern bool TblUniqFlag[8]; extern void CreateTable(); #endif

by **zhouyundong_2012** » Fri Feb 17, 2012 4:30 pm

Code: Select all: #include "StdAfx.h" #include "sd.h" //Common Table int TblMult3[81]; int TblDivide3[81]; int TblRmder3[81]; int TblMult9[9]; //Basis Table int TblCombineMask[512]; int TblTailZero[512]; int TblNumberOne[512]; int TblAnother1[27]; int TblAnother2[27]; int TblShiftLeft[27]; //Table of Decompose Board int TblBoard_Palace[81]; int TblBoard_Block[81]; int TblBoard_BlockMask[81]; int TblBoard_GridUniq[81]; //Table of Initial int TblSelfMask[81]; int TblOtherMask[81]; //Single Row Method int TblSingleRow[12]; int TblRowNumber[512]; //Single Column Method int TblMaskSingle[512]; //Double Column Method int TblMaskDouble[512]; //Confirm Row Method int TblConfirmRow[12]; //Other Table int TblPalaceMask[3]; int TblStrange[27]; int TblChangeMask[27]; bool TblUniqFlag[8]; void CreateTblCommon() { for (int i = 0; i < 81; i++) { TblMult3[i] = i * 3; TblDivide3[i] = i / 3; TblRmder3[i] = i % 3; } for (int i = 0; i < 9; i++) { TblMult9[i] = i * 9; } } void CreateTblCombineMask() { for (int i = 0; i < 512; i++) { TblCombineMask[i] = (i | (i << 9) | (i << 18)) ^ BIT_SET_27; } } void CreateTblAnother() { for (int i = 0; i < 27; i++) { switch (i % 3) { case 0: //At Top TblAnother1[i] = i + 1; TblAnother2[i] = i + 2; break; case 1: //At Middle TblAnother1[i] = i - 1; TblAnother2[i] = i + 1; break; case 2: //At Bottom TblAnother1[i] = i - 2; TblAnother2[i] = i - 1; break; } } } void CreateTblTailZero() { memset(TblTailZero, 0, sizeof(TblTailZero)); for (int i = 0; i < 512; i++) { for (int j = 0; j < 9; j++) { if (i & (1 << j)) break; TblTailZero[i]++; } } } void CreateTblNumberOne() { memset(TblNumberOne, 0, sizeof(TblNumberOne)); for (int i = 0; i < 512; i++) { for (int j = 0; j < 9; j++) { if (i & (1 << j)) TblNumberOne[i]++; } } } void CreateTblShiftLeft() { for (int i = 0; i < 27; i++) { TblShiftLeft[i] = 1 << i; } } void CreateTblBasis() { CreateTblCombineMask(); CreateTblAnother(); CreateTblTailZero(); CreateTblNumberOne(); CreateTblShiftLeft(); } void CreateTblBoard() { for (int i = 0; i < 81; i++) { TblBoard_Palace[i] = TblMult3[i / 27] + TblDivide3[i % 9]; TblBoard_Block[i] = i / 27; TblBoard_BlockMask[i] = 1 << i % 27; TblBoard_GridUniq[i] = 1 << TblBoard_Palace[i] % 3; } } void CreateTblSelfMask() { int Mask[3] = { 0x7E3F1F8, 0x71F8FC7, 0x0FC7E3F }; int Row[3] = { 0x7FFFE00, 0x7FC01FF, 0x3FFFF }; for (int i = 0; i < 81; i++) { int Palace = TblBoard_Palace[i % 27]; TblSelfMask[i] = Mask[Palace] & Row[i % 27 / 9] | TblBoard_BlockMask[i]; } } void CreateTblOtherMask() { for (int i = 0; i < 81; i++) { TblOtherMask[i] = TblCombineMask[1 << i % 9]; } } void CreateTblSingleRow() { memset(TblRowNumber, 0, sizeof(TblRowNumber)); //0 if Not Single Row for (int i = 0; i < 512; i++) { if ((i & 0x1F8) == 0 && i & 0x7) TblRowNumber[i] = 3; if ((i & 0x1C7) == 0 && i & 0x38) TblRowNumber[i] = 6; if ((i & 0x3F) == 0 && i & 0x1C0) TblRowNumber[i] = 9; } int Mask[3] = { 0x1F8, 0x1C7, 0x3F }; for (int i = 0; i < 3; i++) //Palace Number { TblSingleRow[i] = BIT_SET_27; for (int j = 1; j <= 3; j++) //Result of Mask { TblSingleRow[i + j * 3] = (Mask[i] << (j - 1) * 9) ^ BIT_SET_27; } } } void CreateTblMaskSingle() { for (int i = 0; i < 512; i++) { TblMaskSingle[i] = i; int v = i >> 6; //High 3 bit if (v != 4 && v != 2 && v != 1) TblMaskSingle[i] &= 0x3F; v = i >> 3 & 0x7; //Middle 3 bit if (v != 4 && v != 2 && v != 1) TblMaskSingle[i] &= 0x1C7; v = i & 0x7; //Low 3 bit if (v != 4 && v != 2 && v != 1) TblMaskSingle[i] &= 0x1F8; TblMaskSingle[i] = TblCombineMask[TblMaskSingle[i]]; } } void CreateTblMaskDouble() { for (int i = 0; i < 512; i++) { TblMaskDouble[i] = i; int v = i >> 6; //High 3 bit if (v != 6 && v != 5 && v != 3) TblMaskDouble[i] &= 0x3F; v = i >> 3 & 0x7; //Middle 3 bit if (v != 6 && v != 5 && v != 3) TblMaskDouble[i] &= 0x1C7; v = i & 0x7; //Low 3 bit if (v != 6 && v != 5 && v != 3) TblMaskDouble[i] &= 0x1F8; TblMaskDouble[i] = TblCombineMask[TblMaskDouble[i]]; } } void CreateTblConfirmRow() { int Mask[3] = { 0x7038000, 0x70001C0, 0x381C0 }; for (int i = 1; i <= 3; i++) //Result of Mask { TblConfirmRow[i - 1] = BIT_SET_27; for (int j = 0; j < 3; j++) //Row Number { TblConfirmRow[i * 3 + j] = (Mask[j] >> (3 - i) * 3) ^ BIT_SET_27; } } } void CreateTblPalaceMask() { memset(TblPalaceMask, 0, sizeof(TblPalaceMask)); for (int i = 0; i < 3; i++) { TblPalaceMask[i] = 0x1C0E07 << TblMult3[i]; } } void CreateTblStrange() { //Count by Palace, Count by Row in Palace for (int i = 0; i < 27; i++) { int Grid = TblMult9[i % 9 / 3] + TblRmder3[i % 9] + TblMult3[i / 9]; TblStrange[i] = TblSelfMask[Grid]; } } void CreateTblChangeMask() { for (int i = 0; i < 27; i++) { TblChangeMask[i] = (1 << i) | (1 << TblAnother1[i]) | (1 << TblAnother2[i]); for (int j = i % 3; j < 27; j += 3) TblChangeMask[i] |= 1 << j; } } void CreateTblUniqFlag() { memset(TblUniqFlag, 0, sizeof(TblUniqFlag)); for (int i = 0; i < 8; i++) { if (TblNumberOne[i] >= 2) TblUniqFlag[i] = true; } } void CreateTable() { CreateTblCommon(); CreateTblBasis(); CreateTblBoard(); CreateTblSelfMask(); CreateTblOtherMask(); CreateTblSingleRow(); CreateTblMaskSingle(); CreateTblMaskDouble(); CreateTblConfirmRow(); CreateTblPalaceMask(); CreateTblStrange(); CreateTblChangeMask(); CreateTblUniqFlag(); }

by **zhouyundong_2012** » Fri Feb 17, 2012 4:31 pm

Code: Select all: #include "StdAfx.h" #include <windows.h> #include "sd.h" byte Board[81]; //Board CGame G[33]; //Guess Board byte Index; //Guess Index int Change; //Change Bitmap int Finish; //27-bit Finish Bitmap int BlockMask[27]; //Block int BlockMaskSum[3]; //Sum of BlockMask int F[27]; //27-bit Full Mask byte U[27]; //3-bit Unique in Palace int CompF[27]; //Use for Compare byte AllBoard[TotalBoard][81]; //All Boards int TestCaseNumber; //Actual Number of Test Case bool Update(); void Guess(); bool Rollback(); byte Calculate(); int PosLastBit(int v); void InitSodoku() { Change = BIT_SET_27; Finish = 0; Index = 1; BlockMaskSum[0] = BlockMaskSum[1] = BlockMaskSum[2] = 0; memset(BlockMask, 0, sizeof(BlockMask)); memset(F, -1, sizeof(F)); memset(U, 0, sizeof(U)); //Get Full Mask for (int i = 80; i >= 0; --i) { if (Board[i] == '0') continue; int V = Board[i] - '1'; //Value int B = TblMult3[V] + TblBoard_Block[i]; //Block //Get BlockMask and Sum of BlockMask BlockMask[B] |= TblBoard_BlockMask[i]; BlockMaskSum[TblBoard_Block[i]] |= TblBoard_BlockMask[i]; //Get Full Mask F[B] &= TblSelfMask[i]; F[TblAnother1[B]] &= TblOtherMask[i]; F[TblAnother2[B]] &= TblOtherMask[i]; //Get Grid Uniq Bitmap and Finish Bitmap if ((U[B] |= TblBoard_GridUniq[i]) == 7) Finish |= TblShiftLeft[B]; } for (int B = 26; B >= 0; --B) F[B] &= BlockMaskSum[TblRmder3[B]] ^ BlockMask[B] ^ BIT_SET_27; //Clear CompF, Save F as the G[0] memset(CompF, 0, sizeof(F)); memcpy(G[0].F, F, sizeof(F)); } void Guess() { int Least = 9; for (int i = 0; i < 27; i++) { if (TblUniqFlag[U[i]]) continue; G[Index].Block = i; if (TblNumberOne[MID_9_BIT(F[i])] == 2) { G[Index].Line = 1; goto FoundLeast; } if (TblNumberOne[LOW_9_BIT(F[i])] == 2) { G[Index].Line = 0; goto FoundLeast; } if (TblNumberOne[HIGH_9_BIT(F[i])] == 2) { G[Index].Line = 2; goto FoundLeast; } } Least = 9; for (int i = 0; i < 27; i++) { for (int j = 0; j < 3; j++) { int NumberOne = TblNumberOne[HML_9_BIT(F[i], j)]; if (NumberOne > 1 && Least > NumberOne) { G[Index].Block = i; G[Index].Line = j; if ((Least = NumberOne) == 2) goto FoundLeast; } } } FoundLeast: word Left = HML_9_BIT(F[G[Index].Block], G[Index].Line); word Mask = Left & -Left; //Save Data G[Index].Finish = Finish; G[Index].Mask = Mask; G[Index].Left = Left; memcpy(G[Index].F, F, sizeof(F)); memcpy(CompF, F, sizeof(F)); memcpy(G[Index].U, U, sizeof(U)); F[G[Index].Block] &= TblSelfMask[TblTailZero[Mask] + TblMult9[G[Index].Line]]; Change = 1 << G[Index].Block; Index++; } bool Rollback() { if (Index-- == 1) return false; //Restore Data Finish = G[Index].Finish; byte Block = G[Index].Block; byte Line = G[Index].Line; memcpy(F, G[Index].F, sizeof(F)); memcpy(CompF, F, sizeof(F)); memcpy(U, G[Index].U, sizeof(U)); G[Index].Left ^= G[Index].Mask; G[Index].Mask = G[Index].Left & -G[Index].Left; F[Block] &= TblSelfMask[TblTailZero[G[Index].Mask] + TblMult9[Line]]; //Whether The Last Guess Index += TblNumberOne[G[Index].Left] != 1; Change = TblShiftLeft[Block]; return true; } byte Calculate() { bool FoundAnswer = false; while (true) { if (Update()) { if (Finish != BIT_SET_27) { Guess(); continue; } if (FoundAnswer) //Find Answer return MoreAnswer; FoundAnswer = true; } if (!Rollback()) //Backtrack Over return FoundAnswer ? UniqAnswer : NoAnswer; } } bool UpdateByGrid() { int B = 0; while (Change &= ~Finish) { B = Change >> B ? PosLastBit(Change >> B) + B : PosLastBit(Change); //Loop Like Circle Change ^= TblShiftLeft[B]; if (CompF[B] == F[B]) continue; LB_P0: if ((U[B] & 1) == 0) { int S = F[B] & TblPalaceMask[0]; if (S == 0) return false; int TheMask = FULL_TO_PALACE(S); if (S & S - 1) { //Single Row Method if (TblRowNumber[TheMask] != 0 && F[B] & ~TblSingleRow[TblRowNumber[TheMask]]) { F[B] &= TblSingleRow[TblRowNumber[TheMask]]; Change |= TblShiftLeft[B]; } goto LB_P1; } if ((U[B] |= 1) == 7) Finish |= TblShiftLeft[B]; //Neighbour Block F[TblAnother1[B]] &= TblCombineMask[FULL_TO_COLUMN(S)]; F[TblAnother2[B]] &= TblCombineMask[FULL_TO_COLUMN(S)]; //Self Block F[B] &= TblStrange[TblTailZero[TheMask]]; //Friend Block int OldMask = F[B]; switch (TblRmder3[B]) { case 0: AN(F[0], S); AN(F[3], S); AN(F[6], S); AN(F[9], S); AN(F[12], S); AN(F[15], S); AN(F[18], S); AN(F[21], S); AN(F[24], S); break; case 1: AN(F[1], S); AN(F[4], S); AN(F[7], S); AN(F[10], S); AN(F[13], S); AN(F[16], S); AN(F[19], S); AN(F[22], S); AN(F[25], S); break; case 2: AN(F[2], S); AN(F[5], S); AN(F[8], S); AN(F[11], S); AN(F[14], S); AN(F[17], S); AN(F[20], S); AN(F[23], S); AN(F[26], S); break; } F[B] = OldMask; Change |= TblChangeMask[B]; } LB_P1: if ((U[B] & 2) == 0) { int S = F[B] & TblPalaceMask[1]; if (S == 0) return false; int TheMask = FULL_TO_PALACE(S >> 3); if (S & S - 1) { //Single Row Method if (TblRowNumber[TheMask] != 0 && F[B] & ~TblSingleRow[1 + TblRowNumber[TheMask]]) { F[B] &= TblSingleRow[1 + TblRowNumber[TheMask]]; Change |= TblShiftLeft[B]; } goto LB_P2; } if ((U[B] |= 2) == 7) Finish |= TblShiftLeft[B]; //Neighbour Block F[TblAnother1[B]] &= TblCombineMask[FULL_TO_COLUMN(S)]; F[TblAnother2[B]] &= TblCombineMask[FULL_TO_COLUMN(S)]; //Self Block F[B] &= TblStrange[9 + TblTailZero[TheMask]]; //Friend Block int OldMask = F[B]; switch (TblRmder3[B]) { case 0: AN(F[0], S); AN(F[3], S); AN(F[6], S); AN(F[9], S); AN(F[12], S); AN(F[15], S); AN(F[18], S); AN(F[21], S); AN(F[24], S); break; case 1: AN(F[1], S); AN(F[4], S); AN(F[7], S); AN(F[10], S); AN(F[13], S); AN(F[16], S); AN(F[19], S); AN(F[22], S); AN(F[25], S); break; case 2: AN(F[2], S); AN(F[5], S); AN(F[8], S); AN(F[11], S); AN(F[14], S); AN(F[17], S); AN(F[20], S); AN(F[23], S); AN(F[26], S); break; } F[B] = OldMask; Change |= TblChangeMask[B]; } LB_P2: if ((U[B] & 4) == 0) { int S = F[B] & TblPalaceMask[2]; if (S == 0) return false; int TheMask = FULL_TO_PALACE(S >> 6); if (S & S - 1) { //Single Row Method if (TblRowNumber[TheMask] != 0 && F[B] & ~TblSingleRow[2 + TblRowNumber[TheMask]]) { F[B] &= TblSingleRow[2 + TblRowNumber[TheMask]]; Change |= TblShiftLeft[B]; goto LB_P0; } CompF[B] = F[B]; continue; } if ((U[B] |= 4) == 7) Finish |= TblShiftLeft[B]; //Neighbour Block F[TblAnother1[B]] &= TblCombineMask[FULL_TO_COLUMN(S)]; F[TblAnother2[B]] &= TblCombineMask[FULL_TO_COLUMN(S)]; //Self Block F[B] &= TblStrange[18 + TblTailZero[TheMask]]; //Friend Block int OldMask = F[B]; switch (TblRmder3[B]) { case 0: AN(F[0], S); AN(F[3], S); AN(F[6], S); AN(F[9], S); AN(F[12], S); AN(F[15], S); AN(F[18], S); AN(F[21], S); AN(F[24], S); break; case 1: AN(F[1], S); AN(F[4], S); AN(F[7], S); AN(F[10], S); AN(F[13], S); AN(F[16], S); AN(F[19], S); AN(F[22], S); AN(F[25], S); break; case 2: AN(F[2], S); AN(F[5], S); AN(F[8], S); AN(F[11], S); AN(F[14], S); AN(F[17], S); AN(F[20], S); AN(F[23], S); AN(F[26], S); break; } F[B] = OldMask; Change |= TblChangeMask[B]; } if ((Change & TblShiftLeft[B]) == 0) CompF[B] = F[B]; } return true; } bool Update() { //Single Grid Method if (!UpdateByGrid()) return false; memcpy(CompF, F, sizeof(F)); //Single Column Method And Double Column Method for (int B = 0; B < 27; B += 3) { int C0 = FULL_TO_COLUMN(F[B]); int C1 = FULL_TO_COLUMN(F[B + 1]); int C2 = FULL_TO_COLUMN(F[B + 2]); F[B] &= TblMaskSingle[C1] & TblMaskSingle[C2] & TblMaskDouble[C1 | C2]; F[B + 1] &= TblMaskSingle[C0] & TblMaskSingle[C2] & TblMaskDouble[C0 | C2]; F[B + 2] &= TblMaskSingle[C0] & TblMaskSingle[C1] & TblMaskDouble[C0 | C1]; } //Confirm Row Method int Mask; for (int B = 0; B < 27; B++) { if (G[Index - 1].F[B] == F[B]) continue; int FullMask = F[B]; if ((Mask = HIGH_9_BIT(FullMask)) == 0) return false; F[B] &= TblConfirmRow[TblRowNumber[Mask] + 2]; if ((Mask = MID_9_BIT(FullMask)) == 0) return false; F[B] &= TblConfirmRow[TblRowNumber[Mask] + 1]; if ((Mask = LOW_9_BIT(FullMask)) == 0) return false; F[B] &= TblConfirmRow[TblRowNumber[Mask]]; } //Get Change by Compare F with CompF for (int B = 0; B < 27; B++) Change |= (F[B] != CompF[B]) << B; //Single Grid Method if (!UpdateByGrid()) return false; return true; } bool ReadFile() { FILE *file = fopen("TestCase.txt", "r"); if (!file) { printf("Can not open TestCase.txt in current directory"); getchar(); return false; } TestCaseNumber = 0; while (fgets((char *)AllBoard[TestCaseNumber], 1024, file)) { if (++TestCaseNumber == TotalBoard) break; } fclose(file); return true; } bool main() { CreateTable(); if (!ReadFile()) return false; printf("Press Enter to Slove ..."); getchar(); //Set Highest Priority DWORD dwOldProcessP = GetPriorityClass(GetCurrentProcess()); DWORD dwOldThreadP = GetThreadPriority(GetCurrentThread()); SetPriorityClass(GetCurrentProcess(), REALTIME_PRIORITY_CLASS); SetThreadPriority(GetCurrentThread(), THREAD_PRIORITY_TIME_CRITICAL); //Get Frequency LARGE_INTEGER Frequency; ::QueryPerformanceFrequency(&Frequency); //Get Start Time LARGE_INTEGER start; ::QueryPerformanceCounter(&start); byte Answer = 0; //Procedure of Calculate for (int i = 0; i < TestCaseNumber; i++) { memcpy(Board, AllBoard[i], 81); InitSodoku(); if ((Answer = Calculate()) != UniqAnswer) break; } //Get Stop Time LARGE_INTEGER stop; ::QueryPerformanceCounter(&stop); double spend = (double)(stop.QuadPart - start.QuadPart) / (double)Frequency.QuadPart; printf("Spend = %f us\n", spend * 1000 * 1000); printf("Total = %d\n", TestCaseNumber); printf("Average = %f us\n", spend * 1000 * 1000 / TestCaseNumber); if (Answer != UniqAnswer) printf("***************Result: %d ***************\n", Answer); //Restore Priority SetThreadPriority(GetCurrentThread(), dwOldThreadP); SetPriorityClass(GetCurrentProcess(), dwOldProcessP); return true; } /***************************************************************************** * * This Function get the number of 0 which is at the tail of a 27-bit Number * *****************************************************************************/ int PosLastBit(int v) { int A = TblTailZero[v & 0x1FF]; if (A != 9) return A; //Low 9 bit int B = TblTailZero[v >> 9 & 0x1FF]; if (B != 9) return B + 9; //Middle 9 bit return TblTailZero[v >> 18] + 18; //High 9 bit }

by **JasonLion** » Sat Feb 18, 2012 12:35 am

Thank you for translating the comments to English!

by **zhouyundong_2012** » Sat Feb 18, 2012 2:36 am

I am not good at English yet,Is there anybody whill modify and correct the comment?

by **zhouyundong_2012** » Sun Feb 19, 2012 3:48 pm

Code: Select all: #include "StdAfx.h" #include <windows.h> #include "sd.h" byte Board[81]; //Board CGame G[33]; //Guess Board byte Index; //Guess Index int Change; //Change Bitmap int Finish; //27-bit Finish Bitmap int BlockMask[27]; //Block int BlockMaskSum[3]; //Sum of BlockMask int F[27]; //27-bit Full Mask byte U[27]; //3-bit Unique in Palace int CompF[27]; //Use for Compare byte AllBoard[TotalBoard][81]; //All Boards int TestCaseNumber; //Actual Number of Test Case bool Update(); void Guess(); bool Rollback(); byte Calculate(); int PosLastBit(int v); void InitSodoku() { Change = BIT_SET_27; Finish = 0; Index = 1; BlockMaskSum[0] = BlockMaskSum[1] = BlockMaskSum[2] = 0; memset(BlockMask, 0, sizeof(BlockMask)); memset(F, -1, sizeof(F)); memset(U, 0, sizeof(U)); //Get Full Mask for (int i = 80; i >= 0; --i) { if (Board[i] == '0') continue; int V = Board[i] - '1'; //Value int B = TblMult3[V] + TblBoard_Block[i]; //Block //Get BlockMask and Sum of BlockMask BlockMask[B] |= TblBoard_BlockMask[i]; BlockMaskSum[TblBoard_Block[i]] |= TblBoard_BlockMask[i]; //Get Full Mask F[B] &= TblSelfMask[i]; F[TblAnother1[B]] &= TblOtherMask[i]; F[TblAnother2[B]] &= TblOtherMask[i]; //Get Grid Uniq Bitmap and Finish Bitmap if ((U[B] |= TblBoard_GridUniq[i]) == 7) Finish |= TblShiftLeft[B]; } for (int B = 26; B >= 0; --B) F[B] &= BlockMaskSum[TblRmder3[B]] ^ BlockMask[B] ^ BIT_SET_27; //Clear CompF, Save F as the G[0] memset(CompF, 0, sizeof(F)); memcpy(G[0].F, F, sizeof(F)); } void Guess() { int Least = 9; for (int i = 0; i < 27; i++) { if (TblUniqFlag[U[i]]) continue; G[Index].Block = i; if (TblNumberOne[MID_9_BIT(F[i])] == 2) { G[Index].Line = 1; goto FoundLeast; } if (TblNumberOne[LOW_9_BIT(F[i])] == 2) { G[Index].Line = 0; goto FoundLeast; } if (TblNumberOne[HIGH_9_BIT(F[i])] == 2) { G[Index].Line = 2; goto FoundLeast; } } Least = 9; for (int i = 0; i < 27; i++) { for (int j = 0; j < 3; j++) { int NumberOne = TblNumberOne[HML_9_BIT(F[i], j)]; if (NumberOne > 1 && Least > NumberOne) { G[Index].Block = i; G[Index].Line = j; if ((Least = NumberOne) == 2) goto FoundLeast; } } } FoundLeast: word Left = HML_9_BIT(F[G[Index].Block], G[Index].Line); word Mask = Left & -Left; //Save Data G[Index].Finish = Finish; G[Index].Mask = Mask; G[Index].Left = Left; memcpy(G[Index].F, F, sizeof(F)); memcpy(CompF, F, sizeof(F)); memcpy(G[Index].U, U, sizeof(U)); F[G[Index].Block] &= TblSelfMask[TblTailZero[Mask] + TblMult9[G[Index].Line]]; Change = 1 << G[Index].Block; Index++; } bool Rollback() { if (Index-- == 1) return false; //Restore Data Finish = G[Index].Finish; byte Block = G[Index].Block; byte Line = G[Index].Line; memcpy(F, G[Index].F, sizeof(F)); memcpy(CompF, F, sizeof(F)); memcpy(U, G[Index].U, sizeof(U)); G[Index].Left ^= G[Index].Mask; G[Index].Mask = G[Index].Left & -G[Index].Left; F[Block] &= TblSelfMask[TblTailZero[G[Index].Mask] + TblMult9[Line]]; //Whether The Last Guess Index += TblNumberOne[G[Index].Left] != 1; Change = TblShiftLeft[Block]; return true; } byte Calculate() { bool FoundAnswer = false; while (true) { if (Update()) { if (Finish != BIT_SET_27) { Guess(); continue; } if (FoundAnswer) //Find Answer return MoreAnswer; FoundAnswer = true; } if (!Rollback()) //Backtrack Over return FoundAnswer ? UniqAnswer : NoAnswer; } } int TblColumnMask[10] = { 0, 0, 0, 0x1FF, 0, 0, 0x1FF << 9, 0, 0, 0x1FF << 18 }; bool UpdateByGrid() { int B = 0; while (Change &= ~Finish) { B = Change >> B ? PosLastBit(Change >> B) + B : PosLastBit(Change); //Loop Like Circle Change ^= TblShiftLeft[B]; if (CompF[B] == F[B]) continue; LB_P0: if ((U[B] & 1) == 0) { int S = F[B] & TblPalaceMask[0]; if (S == 0) return false; int TheMask = FULL_TO_PALACE(S); if (S & S - 1) { //Single Row Method if (TblRowNumber[TheMask] != 0 && F[B] & ~TblSingleRow[TblRowNumber[TheMask]]) { F[B] &= TblSingleRow[TblRowNumber[TheMask]]; Change |= TblShiftLeft[B]; if (TblNumberOne[TheMask] == 2) { int ColumnMask = TblColumnMask[TblRowNumber[TheMask]]; for (int j = TblRmder3[B]; j < 27; j += 3) { if (j != B && ((F[j] & TblPalaceMask[0]) == S || (F[j] & ColumnMask) == S)) { for (int k = TblRmder3[B]; k < 27; k += 3) { if (k != B && k != j && F[k] & S) { F[k] &= ~S; Change |= TblShiftLeft[k]; } } break; } } } } goto LB_P1; } if ((U[B] |= 1) == 7) Finish |= TblShiftLeft[B]; //Neighbour Block F[TblAnother1[B]] &= TblCombineMask[FULL_TO_COLUMN(S)]; F[TblAnother2[B]] &= TblCombineMask[FULL_TO_COLUMN(S)]; //Self Block F[B] &= TblStrange[TblTailZero[TheMask]]; //Friend Block int OldMask = F[B]; switch (TblRmder3[B]) { case 0: AN(F[0], S); AN(F[3], S); AN(F[6], S); AN(F[9], S); AN(F[12], S); AN(F[15], S); AN(F[18], S); AN(F[21], S); AN(F[24], S); break; case 1: AN(F[1], S); AN(F[4], S); AN(F[7], S); AN(F[10], S); AN(F[13], S); AN(F[16], S); AN(F[19], S); AN(F[22], S); AN(F[25], S); break; case 2: AN(F[2], S); AN(F[5], S); AN(F[8], S); AN(F[11], S); AN(F[14], S); AN(F[17], S); AN(F[20], S); AN(F[23], S); AN(F[26], S); break; } F[B] = OldMask; Change |= TblChangeMask[B]; } LB_P1: if ((U[B] & 2) == 0) { int S = F[B] & TblPalaceMask[1]; if (S == 0) return false; int TheMask = FULL_TO_PALACE(S >> 3); if (S & S - 1) { //Single Row Method if (TblRowNumber[TheMask] != 0 && F[B] & ~TblSingleRow[1 + TblRowNumber[TheMask]]) { F[B] &= TblSingleRow[1 + TblRowNumber[TheMask]]; Change |= TblShiftLeft[B]; if (TblNumberOne[TheMask] == 2) { int ColumnMask = TblColumnMask[TblRowNumber[TheMask]]; for (int j = TblRmder3[B]; j < 27; j += 3) { if (j != B && ((F[j] & TblPalaceMask[1]) == S || (F[j] & ColumnMask) == S)) { for (int k = TblRmder3[B]; k < 27; k += 3) { if (k != B && k != j && F[k] & S) { F[k] &= ~S; Change |= TblShiftLeft[k]; } } break; } } } } goto LB_P2; } if ((U[B] |= 2) == 7) Finish |= TblShiftLeft[B]; //Neighbour Block F[TblAnother1[B]] &= TblCombineMask[FULL_TO_COLUMN(S)]; F[TblAnother2[B]] &= TblCombineMask[FULL_TO_COLUMN(S)]; //Self Block F[B] &= TblStrange[9 + TblTailZero[TheMask]]; //Friend Block int OldMask = F[B]; switch (TblRmder3[B]) { case 0: AN(F[0], S); AN(F[3], S); AN(F[6], S); AN(F[9], S); AN(F[12], S); AN(F[15], S); AN(F[18], S); AN(F[21], S); AN(F[24], S); break; case 1: AN(F[1], S); AN(F[4], S); AN(F[7], S); AN(F[10], S); AN(F[13], S); AN(F[16], S); AN(F[19], S); AN(F[22], S); AN(F[25], S); break; case 2: AN(F[2], S); AN(F[5], S); AN(F[8], S); AN(F[11], S); AN(F[14], S); AN(F[17], S); AN(F[20], S); AN(F[23], S); AN(F[26], S); break; } F[B] = OldMask; Change |= TblChangeMask[B]; } LB_P2: if ((U[B] & 4) == 0) { int S = F[B] & TblPalaceMask[2]; if (S == 0) return false; int TheMask = FULL_TO_PALACE(S >> 6); if (S & S - 1) { //Single Row Method if (TblRowNumber[TheMask] != 0 && F[B] & ~TblSingleRow[2 + TblRowNumber[TheMask]]) { F[B] &= TblSingleRow[2 + TblRowNumber[TheMask]]; Change |= TblShiftLeft[B]; if (TblNumberOne[TheMask] == 2) { int ColumnMask = TblColumnMask[TblRowNumber[TheMask]]; for (int j = TblRmder3[B]; j < 27; j += 3) { if (j != B && ((F[j] & TblPalaceMask[2]) == S || (F[j] & ColumnMask) == S)) { for (int k = TblRmder3[B]; k < 27; k += 3) { if (k != B && k != j && F[k] & S) { F[k] &= ~S; Change |= TblShiftLeft[k]; } } break; } } } goto LB_P0; } CompF[B] = F[B]; continue; } if ((U[B] |= 4) == 7) Finish |= TblShiftLeft[B]; //Neighbour Block F[TblAnother1[B]] &= TblCombineMask[FULL_TO_COLUMN(S)]; F[TblAnother2[B]] &= TblCombineMask[FULL_TO_COLUMN(S)]; //Self Block F[B] &= TblStrange[18 + TblTailZero[TheMask]]; //Friend Block int OldMask = F[B]; switch (TblRmder3[B]) { case 0: AN(F[0], S); AN(F[3], S); AN(F[6], S); AN(F[9], S); AN(F[12], S); AN(F[15], S); AN(F[18], S); AN(F[21], S); AN(F[24], S); break; case 1: AN(F[1], S); AN(F[4], S); AN(F[7], S); AN(F[10], S); AN(F[13], S); AN(F[16], S); AN(F[19], S); AN(F[22], S); AN(F[25], S); break; case 2: AN(F[2], S); AN(F[5], S); AN(F[8], S); AN(F[11], S); AN(F[14], S); AN(F[17], S); AN(F[20], S); AN(F[23], S); AN(F[26], S); break; } F[B] = OldMask; Change |= TblChangeMask[B]; } if ((Change & TblShiftLeft[B]) == 0) CompF[B] = F[B]; } return true; } bool Update() { //Single Grid Method if (!UpdateByGrid()) return false; memcpy(CompF, F, sizeof(F)); //Single Column Method And Double Column Method for (int B = 0; B < 27; B += 3) { int C0 = FULL_TO_COLUMN(F[B]); int C1 = FULL_TO_COLUMN(F[B + 1]); int C2 = FULL_TO_COLUMN(F[B + 2]); F[B] &= TblMaskSingle[C1] & TblMaskSingle[C2] & TblMaskDouble[C1 | C2]; F[B + 1] &= TblMaskSingle[C0] & TblMaskSingle[C2] & TblMaskDouble[C0 | C2]; F[B + 2] &= TblMaskSingle[C0] & TblMaskSingle[C1] & TblMaskDouble[C0 | C1]; } //Confirm Row Method int Mask; for (int B = 0; B < 27; B++) { if (G[Index - 1].F[B] == F[B]) continue; int FullMask = F[B]; if ((Mask = HIGH_9_BIT(FullMask)) == 0) return false; F[B] &= TblConfirmRow[TblRowNumber[Mask] + 2]; if ((Mask = MID_9_BIT(FullMask)) == 0) return false; F[B] &= TblConfirmRow[TblRowNumber[Mask] + 1]; if ((Mask = LOW_9_BIT(FullMask)) == 0) return false; F[B] &= TblConfirmRow[TblRowNumber[Mask]]; } //Get Change by Compare F with CompF for (int B = 0; B < 27; B++) Change |= (F[B] != CompF[B]) << B; //Single Grid Method if (!UpdateByGrid()) return false; return true; } bool ReadFile() { FILE *file = fopen("TestCase.txt", "r"); if (!file) { printf("Can not open TestCase.txt in current directory"); getchar(); return false; } TestCaseNumber = 0; while (fgets((char *)AllBoard[TestCaseNumber], 1024, file)) { if (++TestCaseNumber == TotalBoard) break; } fclose(file); return true; } bool main() { CreateTable(); if (!ReadFile()) return false; printf("Press Enter to Slove ..."); getchar(); //Set Highest Priority DWORD dwOldProcessP = GetPriorityClass(GetCurrentProcess()); DWORD dwOldThreadP = GetThreadPriority(GetCurrentThread()); SetPriorityClass(GetCurrentProcess(), REALTIME_PRIORITY_CLASS); SetThreadPriority(GetCurrentThread(), THREAD_PRIORITY_TIME_CRITICAL); //Get Frequency LARGE_INTEGER Frequency; ::QueryPerformanceFrequency(&Frequency); //Get Start Time LARGE_INTEGER start; ::QueryPerformanceCounter(&start); byte Answer = 0; //Procedure of Calculate for (int i = 0; i < TestCaseNumber; i++) { memcpy(Board, AllBoard[i], 81); InitSodoku(); if ((Answer = Calculate()) != UniqAnswer) break; } //Get Stop Time LARGE_INTEGER stop; ::QueryPerformanceCounter(&stop); double spend = (double)(stop.QuadPart - start.QuadPart) / (double)Frequency.QuadPart; printf("Spend = %f us\n", spend * 1000 * 1000); printf("Total = %d\n", TestCaseNumber); printf("Average = %f us\n", spend * 1000 * 1000 / TestCaseNumber); if (Answer != UniqAnswer) printf("***************Result: %d ***************\n", Answer); //Restore Priority SetThreadPriority(GetCurrentThread(), dwOldThreadP); SetPriorityClass(GetCurrentProcess(), dwOldProcessP); return true; } /***************************************************************************** * * This Function get the number of 0 which is at the tail of a 27-bit Number * *****************************************************************************/ int PosLastBit(int v) { int A = TblTailZero[v & 0x1FF]; if (A != 9) return A; //Low 9 bit int B = TblTailZero[v >> 9 & 0x1FF]; if (B != 9) return B + 9; //Middle 9 bit return TblTailZero[v >> 18] + 18; //High 9 bit }

hi,JasonLion
Test this code please. I think it will work faster.
and I want to know the result about top1465

by **JasonLion** » Sun Feb 19, 2012 6:59 pm

Your most recent code shows an 8% improvement on top1465. That is impressive, but still slower than JSolve for the same puzzles.

by **zhouyundong_2012** » Sun Mar 11, 2012 7:28 am

Code: Select all: #ifndef __sd_h__ #define __sd_h__ typedef unsigned char byte; typedef unsigned short word; #define TotalBoard 50000 //Total Games //Answer Attribute #define NoAnswer 0 #define UniqAnswer 1 #define MoreAnswer 2 //High, Middle, Low 9 bit of a 27-bit number #define HIGH_9_BIT(v) ((v) >> 18) #define MID_9_BIT(v) (((v) >> 9) & 0x1FF) #define LOW_9_BIT(v) ((v) & 0x1FF) #define HML_9_BIT(v, l) ((v) >> TblMult9[l] & 0x1FF) #define FULL_TO_COLUMN(v) (((v) | ((v) >> 9) | ((v) >> 18)) & 0x1FF) //Full Mask(27-bit) to 9 bit #define FULL_TO_PALACE(v) (((v) | ((v) >> 6) | ((v) >> 12)) & 0x1FF) //Full Mask(27-bit) to 9 bit, x-- y-- z-- #define FULL_TO_SHRINK(v) (TblShrinkHigh[(v) >> 18] | TblShrinkMid[((v) >> 9) & 0x1FF] | TblShrinkLow[(v) & 0x1FF]) //000 to 0, else to 1 #define BIT_SET_27 0x07FFFFFF #define AN(v, n) (v) &= ~(n) struct CGame { public: int Finish; //27-bit Finish Bitmap int F[27]; //27-bit Full Mask byte U[27]; //3-bit Unique in Palace byte Block; //The Block Number of guess [0, 27) byte Line; //The Line Number of guess [0, 3) word Mask; //The 9-bit Mask of guess word Left; //The 9-bit Left Mask of guess int BlockMask[27]; int BlockMaskSum[3]; }; //Common Table extern int TblMult3[81]; extern int TblDivide3[81]; extern int TblRmder3[81]; extern int TblMult9[9]; //Basis Table extern int TblCombineMask[512]; extern int TblTailZero[512]; extern int TblNumberOne[512]; extern int TblAnother1[27]; extern int TblAnother2[27]; extern int TblShiftLeft[27]; //Table of Decompose Board extern int TblBoard_Palace[81]; extern int TblBoard_Block[81]; extern int TblBoard_BlockMask[81]; extern int TblBoard_GridUniq[81]; //Table of Initial extern int TblSelfMask[81]; extern int TblOtherMask[81]; //Complex Friend Method extern int TblMaskSingle[512]; extern int TblMaskDouble[512]; //Other Table extern int TblPalaceMask[8]; extern bool TblUniqFlag[8]; //Shrink Mask extern int TblShrinkLow[512]; extern int TblShrinkMid[512]; extern int TblShrinkHigh[512]; //Complex Method extern int TblComplexMask[512]; extern int TblColumnSingle[512]; extern int TblRowSingle[512]; extern void CreateTable(); #endif

by **zhouyundong_2012** » Sun Mar 11, 2012 7:29 am

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

by **zhouyundong_2012** » Sun Mar 11, 2012 7:30 am

Code: Select all: #include <windows.h> #include <stdio.h> #include "sd.h" byte Board[81]; //Board CGame G[33]; //Guess Board byte Index; //Guess Index int Finish; //27-bit Finish Bitmap int BlockMask[27]; //Block int BlockMaskSum[3]; //Sum of BlockMask int F[27]; //27-bit Full Mask byte U[27]; //3-bit Unique in Palace int CompF[27]; //Use for Compare byte AllBoard[TotalBoard][81]; //All Boards int TestCaseNumber; //Actual Number of Test Case bool Update(); void Guess(); bool Rollback(); byte Calculate(); void InitSodoku() { Finish = 0; Index = 1; BlockMaskSum[0] = BlockMaskSum[1] = BlockMaskSum[2] = 0; memset(BlockMask, 0, sizeof(BlockMask)); memset(F, -1, sizeof(F)); memset(U, 0, sizeof(U)); //Get Full Mask for (int i = 80; i >= 0; --i) { if (Board[i] == '0') continue; int V = Board[i] - '1'; //Value int B = TblMult3[V] + TblBoard_Block[i]; //Block //Get BlockMask and Sum of BlockMask BlockMask[B] |= TblBoard_BlockMask[i]; BlockMaskSum[TblBoard_Block[i]] |= TblBoard_BlockMask[i]; //Get Full Mask F[B] &= TblSelfMask[i]; F[TblAnother1[B]] &= TblOtherMask[i]; F[TblAnother2[B]] &= TblOtherMask[i]; //Get Grid Uniq Bitmap and Finish Bitmap if ((U[B] |= TblBoard_GridUniq[i]) == 7) Finish |= TblShiftLeft[B]; } for (int B = 26; B >= 0; --B) F[B] &= BlockMaskSum[TblRmder3[B]] ^ BlockMask[B] ^ BIT_SET_27; //Clear CompF, Save F as the G[0] memset(CompF, 0, sizeof(F)); memcpy(G[0].F, F, sizeof(F)); } void Guess() { int Least = 9; for (int i = 0; i < 27; i++) { if (TblUniqFlag[U[i]]) continue; G[Index].Block = i; if (TblNumberOne[LOW_9_BIT(F[i])] == 2) { G[Index].Line = 0; goto FoundLeast; } if (TblNumberOne[MID_9_BIT(F[i])] == 2) { G[Index].Line = 1; goto FoundLeast; } if (TblNumberOne[HIGH_9_BIT(F[i])] == 2) { G[Index].Line = 2; goto FoundLeast; } } Least = 9; for (int i = 0; i < 27; i++) { for (int j = 0; j < 3; j++) { int NumberOne = TblNumberOne[HML_9_BIT(F[i], j)]; if (NumberOne > 1 && Least > NumberOne) { G[Index].Block = i; G[Index].Line = j; if ((Least = NumberOne) == 2) goto FoundLeast; } } } FoundLeast: word Left = HML_9_BIT(F[G[Index].Block], G[Index].Line); word Mask = Left & -Left; //Save Data G[Index].Finish = Finish; G[Index].Mask = Mask; G[Index].Left = Left; memcpy(G[Index].F, F, sizeof(F)); memcpy(CompF, F, sizeof(F)); memcpy(G[Index].U, U, sizeof(U)); F[G[Index].Block] &= TblSelfMask[TblTailZero[Mask] + TblMult9[G[Index].Line]]; Index++; } bool Rollback() { if (Index-- == 1) return false; //Restore Data Finish = G[Index].Finish; byte Block = G[Index].Block; byte Line = G[Index].Line; memcpy(F, G[Index].F, sizeof(F)); memcpy(CompF, F, sizeof(F)); memcpy(U, G[Index].U, sizeof(U)); G[Index].Left ^= G[Index].Mask; G[Index].Mask = G[Index].Left & -G[Index].Left; F[Block] &= TblSelfMask[TblTailZero[G[Index].Mask] + TblMult9[Line]]; //Whether The Last Guess Index += TblNumberOne[G[Index].Left] != 1; return true; } byte Calculate() { bool FoundAnswer = false; while (true) { if (Update()) { if (Finish != BIT_SET_27) { Guess(); continue; } if (FoundAnswer) //Find Answer return MoreAnswer; FoundAnswer = true; } if (!Rollback()) //Backtrack Over return FoundAnswer ? UniqAnswer : NoAnswer; } } bool Update() { bool Change = true; while (Change) { Change = false; for (int B = 0; B < 27; B++) { if (CompF[B] == F[B]) continue; Change = true; //Complex Self Method int Shrink = FULL_TO_SHRINK(F[B]); if (TblComplexMask[Shrink] == 0) return false; if (TblComplexMask[Shrink] != BIT_SET_27) { F[B] &= TblComplexMask[Shrink]; Shrink = FULL_TO_SHRINK(F[B]); } CompF[B] = F[B]; //Complex Friend Method int Column = FULL_TO_COLUMN(F[B]); int C1 = FULL_TO_COLUMN(F[TblAnother1[B]]); int C2 = FULL_TO_COLUMN(F[TblAnother2[B]]); F[TblAnother2[B]] &= TblMaskSingle[Column] & TblMaskDouble[Column | C1]; F[TblAnother1[B]] &= TblMaskSingle[Column] & TblMaskDouble[Column | C2]; //Single Grid Method int Single = (TblRowSingle[Shrink] & TblColumnSingle[Column]) ^ U[B]; if (Single == 0) continue; if ((U[B] |= Single) == 7) Finish |= TblShiftLeft[B]; int S = F[B] & TblPalaceMask[Single]; //Friend Block switch (TblRmder3[B]) { case 0: AN(F[0], S); AN(F[3], S); AN(F[6], S); AN(F[9], S); AN(F[12], S); AN(F[15], S); AN(F[18], S); AN(F[21], S); AN(F[24], S); break; case 1: AN(F[1], S); AN(F[4], S); AN(F[7], S); AN(F[10], S); AN(F[13], S); AN(F[16], S); AN(F[19], S); AN(F[22], S); AN(F[25], S); break; case 2: AN(F[2], S); AN(F[5], S); AN(F[8], S); AN(F[11], S); AN(F[14], S); AN(F[17], S); AN(F[20], S); AN(F[23], S); AN(F[26], S); break; } F[B] = CompF[B]; } } return true; } bool ReadFile() { FILE *file = fopen("TestCase.txt", "r"); if (!file) { printf("Can not open TestCase.txt in current directory"); getchar(); return false; } TestCaseNumber = 0; while (fgets((char *)AllBoard[TestCaseNumber], 1024, file)) { if (++TestCaseNumber == TotalBoard) break; } fclose(file); return true; } bool main() { CreateTable(); if (!ReadFile()) return false; printf("Press Enter to Slove ..."); getchar(); //Set Highest Priority DWORD dwOldProcessP = GetPriorityClass(GetCurrentProcess()); DWORD dwOldThreadP = GetThreadPriority(GetCurrentThread()); SetPriorityClass(GetCurrentProcess(), REALTIME_PRIORITY_CLASS); SetThreadPriority(GetCurrentThread(), THREAD_PRIORITY_TIME_CRITICAL); //Get Frequency LARGE_INTEGER Frequency; ::QueryPerformanceFrequency(&Frequency); //Get Start Time LARGE_INTEGER start; ::QueryPerformanceCounter(&start); byte Answer = 0; //Procedure of Calculate for (int i = 0; i < TestCaseNumber; i++) { memcpy(Board, AllBoard[i], 81); InitSodoku(); if ((Answer = Calculate()) != UniqAnswer) break; } //Get Stop Time LARGE_INTEGER stop; ::QueryPerformanceCounter(&stop); double spend = (double)(stop.QuadPart - start.QuadPart) / (double)Frequency.QuadPart; printf("Spend = %f us\n", spend * 1000 * 1000); printf("Total = %d\n", TestCaseNumber); printf("Average = %f us\n", spend * 1000 * 1000 / TestCaseNumber); if (Answer != UniqAnswer) printf("***************Result: %d ***************\n", Answer); //Restore Priority SetThreadPriority(GetCurrentThread(), dwOldThreadP); SetPriorityClass(GetCurrentProcess(), dwOldProcessP); return true; }

by **Afmob** » Sun Mar 11, 2012 9:00 am

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

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

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

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

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

I merged your new topic into your existing topic. It is better to keep everything together in one place.

by **champagne** » Sun Mar 11, 2012 2:06 pm

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

fss

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

champagne

by **JasonLion** » Sun Mar 11, 2012 5:50 pm

dobrichev's code is in the same general range as JSolve, slightly better with some compilers/puzzles, slightly worse with others. Preliminary tests show that zhouyundong_2012's code is now faster than either of them by roughly 10%. However, I haven't run zhouyundong_2012's code against the complete range of puzzle collections, so there is a small chance of better or worse times on some kinds of puzzles.

The New Sudoku Players' Forum

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

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

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

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

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

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

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

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

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

ZSolver! It maybe the fastest in any case.

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

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

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

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

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