The New Sudoku Players' Forum

by **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(); }

by **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

by **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

by **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.

by **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]

by **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;

by **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.

by **zhouyundong_2012** » Tue Oct 23, 2012 12:49 pm

I think top-1465 will get more improvement because Guess() and RollBack() execute more times.

by **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

by **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.

by **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; }

by **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

by **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(); }

by **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; }

by **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];

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)

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

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

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

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

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

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

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

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

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

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

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