thanks, Afmob,
Two bugs have been fixed.
000000000000000000000000000000000000000000000000000000000000000000000000000000000
111111111111111111111111111111111111111111111111111111111111111111111111111111111
#ifndef __sd_h__
#define __sd_h__
#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_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 F[27]; //27-bit Full Mask
int U[27]; //3-bit Unique in Palace
int Block; //The Block Number of guess [0, 27)
int Line; //The Line Number of guess [0, 3)
int Mask; //The 9-bit Mask of guess
int 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];
//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 TblShrinkSingle[512];
extern void CreateTable();
#endif
#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 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_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++)
{
TblShrinkSingle[i] = 7;
int j = i & FULL_TO_SHRINK(TblComplexMask[i]);
int v = j & 0x49;
if (v != 1 && v != 8 && v != 64)
TblShrinkSingle[i] &= 0x6;
v = j & 0x92;
if (v != 2 && v != 16 && v != 128)
TblShrinkSingle[i] &= 0x5;
v = j & 0x124;
if (v != 4 && v != 32 && v != 256)
TblShrinkSingle[i] &= 0x3;
}
}
void CreateTable()
{
CreateTblCommon();
CreateTblBasis();
CreateTblBoard();
CreateTblSelfMask();
CreateTblOtherMask();
CreateTblMaskSingle();
CreateTblMaskDouble();
CreateTblPalaceMask();
CreateTblUniqFlag();
CreateShrinkMask();
CreateComplexMask();
CreateTblColumnSingle();
}
#include <windows.h>
#include <stdio.h>
#include "sd.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 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()
{
Index = 1;
BlockMaskSum[0] = BlockMaskSum[1] = BlockMaskSum[2] = 0;
for (int B = 26; B >= 0; --B)
{
BlockMask[B] = U[B] = 0;
CompF[B] = F[B] = -1;
}
//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
BlockMask[B] |= TblBoard_BlockMask[i];
BlockMaskSum[TblBoard_Block[i]] |= BlockMask[B];
//Get Full Mask
F[B] &= TblSelfMask[i];
F[TblAnother1[B]] &= TblOtherMask[i];
F[TblAnother2[B]] &= TblOtherMask[i];
U[B] |= TblBoard_GridUniq[i];
}
for (int B = 26; B >= 0; --B)
F[B] &= BlockMaskSum[TblRmder3[B]] ^ BlockMask[B] ^ BIT_SET_27;
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:
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-- == 1)
return false;
//Restore Data
int Block = G[Index].Block;
int Line = G[Index].Line;
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[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 (U[0] + U[1] + U[2] != 21 || U[3] + U[4] + U[5] != 21 || U[6] + U[7] + U[8] != 21
|| U[9] + U[10] + U[11] != 21 || U[12] + U[13] + U[14] != 21 || U[15] + U[16] + U[17] != 21
|| U[18] + U[19] + U[20] != 21 || U[21] + U[22] + U[23] != 21 || U[24] + U[25] + U[26] != 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\tint Single = (TblShrinkSingle[Shrink] & TblColumnSingle[Column]) ^ U[%d];\n", i);
fputs(str, fp);
fputs("\t\t\tif (Single)\n", fp);
fputs("\t\t\t{\n", fp);
sprintf(str, "\t\t\t\tU[%d] |= Single;\n", i);
fputs(str, fp);
//Friend Block
sprintf(str, "\t\t\t\tint S = F[%d] & TblPalaceMask[Single];\n", 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
for (int i = 0; i < TestCaseNumber; i++)
{
memcpy(Board, AllBoard[i], 81);
InitSodoku();
if ((Answer = Calculate()) != UniqAnswer)
continue;
}