The New Sudoku Players' Forum

[zhouyundong_2012]

OK,,, Uniq Palace to Uniq Row is accomplished.

[zhouyundong_2012]

where to download top1645?

[ronk]

where to download top1645?

A Google search quickly shows it is still available at http://magictour.free.fr/top1465 . Note this list of hardest puzzles was assembled circa 2006. Things have changed considerably since then.

[JasonLion]

I have been slowly working my way through the source code. zhouyundong_2012 uses an array of int where each element holds one chute (three rows) of basically pencil marks for a single digit. I say "basically pencil marks" because I think placed digits are also set. The solver appears to use locked candidates (perhaps incompletely) and hidden singles. I haven't seen anything that appears to be doing naked singles, and I can't quite figure out if it really does column-block locked candidates, or only does row-block locked candidates. The row-block locked candidates code is very very short and fast, quite entertaining reading for bit twiddling wonks like me.

zhouyundong_2012, your AN(v,n) macro negates n each time. Since AN() is always called eight times in a row with the same n, it would be more efficient to negate n outside of AN(). Of course some compilers can figure this out for you, but not all.

[zhouyundong_2012]

I did not do column-block locked canididate. I think column-block can't work well.
Thank you for your comment for this code.

[zhouyundong_2012]

Of course some compilers can figure this out for you, but not all.

Thank you!

[zhouyundong_2012]

Code: Select all

#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 Row
   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_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             TblColumnMask[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


[zhouyundong_2012]

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];
//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_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 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()
{
   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();
   CreateShrinkMask();
   CreateComplexMask();
   CreateTblColumnSingle();
   CreateTblShrinkSingle();
}


[zhouyundong_2012]

Code: Select all

#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 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 = 1;
   BlockMaskSum[0] = BlockMaskSum[1] = BlockMaskSum[2] = 0;
   for (int B = 0; B < 27; B++)
   {
      BlockMask[B] = U[B] = 0;
      CompF[B] = F[B] = BIT_SET_27;
   }
   //Get Full Mask
   for (int i = 0; i < 81; 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];
   }
   for (int B = 0; B < 27; 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++)
      {
         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 = 0; B < 27; 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 = 0; B < 27; 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\tif (TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]] != U[%d])\n", i);
      fputs(str, fp);
      fputs("\t\t\t{\n", fp);
      sprintf(str, "\t\t\t\tU[%d] |= TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]];\n", i);
      fputs(str, fp);
      //Friend Block
      sprintf(str, "\t\t\t\tint S = ~(F[%d] & TblColumnMask[U[%d]]);\n", i, i);
      fputs(str, fp);
      fputs("\t\t\t\t", fp);
      for (int j = TblRmder3[i]; j < 27; j += 3)
      {
         if (j != i)
         {
            sprintf(str, "AN(F[%d], S); ", j);
            fputs(str, fp);
         }
      }
      fputs("\n", fp);
      fputs("\t\t\t}\n", fp);
      fputs("\t\t}\n", fp);
   }
   fputs("\t}\n", fp);
   fputs("\treturn true;\n", fp);
   fputs("}", fp);
   fclose(fp);
}
#endif

bool ReadFile()
{
   FILE *file = fopen("TestCase.txt", "r");
   if (!file)
   {
      printf("Can not open TestCase.txt in current directory");
      getchar();
      return false;
   }
   TestCaseNumber = 0;
   while (fgets((char *)AllBoard[TestCaseNumber], 1024, file))
   {
      if (++TestCaseNumber == TotalBoard)
         break;
   }
   fclose(file);
   return true;
}

bool main()
{
   CreateTable();

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

   if (!ReadFile())
      return false;

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

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

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

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

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

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

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

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

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

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

   return true;
}

#ifdef __ProgramWritter
bool Update()
{
   return true;
}
#else
//open Update.c and copy to here
#endif


[zhouyundong_2012]

This is the last version.

What can do next to improve the speed? I think that will be Guess(). How to guess effeciently, that is the question.

Sorry,Afmob. I will write a new, vast, complex, interesting web game Disaster Empire.
I think a lot lot of people will play it.

So,Afmob, you can use my code, and change everything freedom.

Anybody have the interest to write Disaster Empire with me?

For anyone, you can use this code.

[zhouyundong_2012]

Code: Select all

bool Update()
{
   int Shrink = ~0;
   while (Shrink)
   {
      Shrink = 0;
      if (CompF[0] != F[0])
      {
         Shrink = FULL_TO_SHRINK(F[0]);
         if ((F[0] &= TblComplexMask[Shrink]) == 0)
            return false;
         CompF[0] = F[0];
         int Column = FULL_TO_COLUMN(F[0]);
         int C1 = Column | FULL_TO_COLUMN(F[1]);
         int C2 = Column | FULL_TO_COLUMN(F[2]);
         F[1] &= TblMaskSingle[Column] & TblMaskDouble[C2];
         F[2] &= TblMaskSingle[Column] & TblMaskDouble[C1];
         if (TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]] != U[0])
         {
            U[0] |= TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]];
            int S = ~(F[0] & TblColumnMask[U[0]]);
            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);
         }
      }
      if (CompF[1] != F[1])
      {
         Shrink = FULL_TO_SHRINK(F[1]);
         if ((F[1] &= TblComplexMask[Shrink]) == 0)
            return false;
         CompF[1] = F[1];
         int Column = FULL_TO_COLUMN(F[1]);
         int C1 = Column | FULL_TO_COLUMN(F[0]);
         int C2 = Column | FULL_TO_COLUMN(F[2]);
         F[0] &= TblMaskSingle[Column] & TblMaskDouble[C2];
         F[2] &= TblMaskSingle[Column] & TblMaskDouble[C1];
         if (TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]] != U[1])
         {
            U[1] |= TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]];
            int S = ~(F[1] & TblColumnMask[U[1]]);
            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);
         }
      }
      if (CompF[2] != F[2])
      {
         Shrink = FULL_TO_SHRINK(F[2]);
         if ((F[2] &= TblComplexMask[Shrink]) == 0)
            return false;
         CompF[2] = F[2];
         int Column = FULL_TO_COLUMN(F[2]);
         int C1 = Column | FULL_TO_COLUMN(F[0]);
         int C2 = Column | FULL_TO_COLUMN(F[1]);
         F[0] &= TblMaskSingle[Column] & TblMaskDouble[C2];
         F[1] &= TblMaskSingle[Column] & TblMaskDouble[C1];
         if (TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]] != U[2])
         {
            U[2] |= TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]];
            int S = ~(F[2] & TblColumnMask[U[2]]);
            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);
         }
      }
      if (CompF[3] != F[3])
      {
         Shrink = FULL_TO_SHRINK(F[3]);
         if ((F[3] &= TblComplexMask[Shrink]) == 0)
            return false;
         CompF[3] = F[3];
         int Column = FULL_TO_COLUMN(F[3]);
         int C1 = Column | FULL_TO_COLUMN(F[4]);
         int C2 = Column | FULL_TO_COLUMN(F[5]);
         F[4] &= TblMaskSingle[Column] & TblMaskDouble[C2];
         F[5] &= TblMaskSingle[Column] & TblMaskDouble[C1];
         if (TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]] != U[3])
         {
            U[3] |= TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]];
            int S = ~(F[3] & TblColumnMask[U[3]]);
            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);
         }
      }
      if (CompF[4] != F[4])
      {
         Shrink = FULL_TO_SHRINK(F[4]);
         if ((F[4] &= TblComplexMask[Shrink]) == 0)
            return false;
         CompF[4] = F[4];
         int Column = FULL_TO_COLUMN(F[4]);
         int C1 = Column | FULL_TO_COLUMN(F[3]);
         int C2 = Column | FULL_TO_COLUMN(F[5]);
         F[3] &= TblMaskSingle[Column] & TblMaskDouble[C2];
         F[5] &= TblMaskSingle[Column] & TblMaskDouble[C1];
         if (TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]] != U[4])
         {
            U[4] |= TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]];
            int S = ~(F[4] & TblColumnMask[U[4]]);
            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);
         }
      }
      if (CompF[5] != F[5])
      {
         Shrink = FULL_TO_SHRINK(F[5]);
         if ((F[5] &= TblComplexMask[Shrink]) == 0)
            return false;
         CompF[5] = F[5];
         int Column = FULL_TO_COLUMN(F[5]);
         int C1 = Column | FULL_TO_COLUMN(F[3]);
         int C2 = Column | FULL_TO_COLUMN(F[4]);
         F[3] &= TblMaskSingle[Column] & TblMaskDouble[C2];
         F[4] &= TblMaskSingle[Column] & TblMaskDouble[C1];
         if (TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]] != U[5])
         {
            U[5] |= TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]];
            int S = ~(F[5] & TblColumnMask[U[5]]);
            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);
         }
      }
      if (CompF[6] != F[6])
      {
         Shrink = FULL_TO_SHRINK(F[6]);
         if ((F[6] &= TblComplexMask[Shrink]) == 0)
            return false;
         CompF[6] = F[6];
         int Column = FULL_TO_COLUMN(F[6]);
         int C1 = Column | FULL_TO_COLUMN(F[7]);
         int C2 = Column | FULL_TO_COLUMN(F[8]);
         F[7] &= TblMaskSingle[Column] & TblMaskDouble[C2];
         F[8] &= TblMaskSingle[Column] & TblMaskDouble[C1];
         if (TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]] != U[6])
         {
            U[6] |= TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]];
            int S = ~(F[6] & TblColumnMask[U[6]]);
            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);
         }
      }
      if (CompF[7] != F[7])
      {
         Shrink = FULL_TO_SHRINK(F[7]);
         if ((F[7] &= TblComplexMask[Shrink]) == 0)
            return false;
         CompF[7] = F[7];
         int Column = FULL_TO_COLUMN(F[7]);
         int C1 = Column | FULL_TO_COLUMN(F[6]);
         int C2 = Column | FULL_TO_COLUMN(F[8]);
         F[6] &= TblMaskSingle[Column] & TblMaskDouble[C2];
         F[8] &= TblMaskSingle[Column] & TblMaskDouble[C1];
         if (TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]] != U[7])
         {
            U[7] |= TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]];
            int S = ~(F[7] & TblColumnMask[U[7]]);
            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);
         }
      }
      if (CompF[8] != F[8])
      {
         Shrink = FULL_TO_SHRINK(F[8]);
         if ((F[8] &= TblComplexMask[Shrink]) == 0)
            return false;
         CompF[8] = F[8];
         int Column = FULL_TO_COLUMN(F[8]);
         int C1 = Column | FULL_TO_COLUMN(F[6]);
         int C2 = Column | FULL_TO_COLUMN(F[7]);
         F[6] &= TblMaskSingle[Column] & TblMaskDouble[C2];
         F[7] &= TblMaskSingle[Column] & TblMaskDouble[C1];
         if (TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]] != U[8])
         {
            U[8] |= TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]];
            int S = ~(F[8] & TblColumnMask[U[8]]);
            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);
         }
      }
      if (CompF[9] != F[9])
      {
         Shrink = FULL_TO_SHRINK(F[9]);
         if ((F[9] &= TblComplexMask[Shrink]) == 0)
            return false;
         CompF[9] = F[9];
         int Column = FULL_TO_COLUMN(F[9]);
         int C1 = Column | FULL_TO_COLUMN(F[10]);
         int C2 = Column | FULL_TO_COLUMN(F[11]);
         F[10] &= TblMaskSingle[Column] & TblMaskDouble[C2];
         F[11] &= TblMaskSingle[Column] & TblMaskDouble[C1];
         if (TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]] != U[9])
         {
            U[9] |= TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]];
            int S = ~(F[9] & TblColumnMask[U[9]]);
            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);
         }
      }
      if (CompF[10] != F[10])
      {
         Shrink = FULL_TO_SHRINK(F[10]);
         if ((F[10] &= TblComplexMask[Shrink]) == 0)
            return false;
         CompF[10] = F[10];
         int Column = FULL_TO_COLUMN(F[10]);
         int C1 = Column | FULL_TO_COLUMN(F[9]);
         int C2 = Column | FULL_TO_COLUMN(F[11]);
         F[9] &= TblMaskSingle[Column] & TblMaskDouble[C2];
         F[11] &= TblMaskSingle[Column] & TblMaskDouble[C1];
         if (TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]] != U[10])
         {
            U[10] |= TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]];
            int S = ~(F[10] & TblColumnMask[U[10]]);
            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);
         }
      }
      if (CompF[11] != F[11])
      {
         Shrink = FULL_TO_SHRINK(F[11]);
         if ((F[11] &= TblComplexMask[Shrink]) == 0)
            return false;
         CompF[11] = F[11];
         int Column = FULL_TO_COLUMN(F[11]);
         int C1 = Column | FULL_TO_COLUMN(F[9]);
         int C2 = Column | FULL_TO_COLUMN(F[10]);
         F[9] &= TblMaskSingle[Column] & TblMaskDouble[C2];
         F[10] &= TblMaskSingle[Column] & TblMaskDouble[C1];
         if (TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]] != U[11])
         {
            U[11] |= TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]];
            int S = ~(F[11] & TblColumnMask[U[11]]);
            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);
         }
      }
      if (CompF[12] != F[12])
      {
         Shrink = FULL_TO_SHRINK(F[12]);
         if ((F[12] &= TblComplexMask[Shrink]) == 0)
            return false;
         CompF[12] = F[12];
         int Column = FULL_TO_COLUMN(F[12]);
         int C1 = Column | FULL_TO_COLUMN(F[13]);
         int C2 = Column | FULL_TO_COLUMN(F[14]);
         F[13] &= TblMaskSingle[Column] & TblMaskDouble[C2];
         F[14] &= TblMaskSingle[Column] & TblMaskDouble[C1];
         if (TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]] != U[12])
         {
            U[12] |= TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]];
            int S = ~(F[12] & TblColumnMask[U[12]]);
            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);
         }
      }
      if (CompF[13] != F[13])
      {
         Shrink = FULL_TO_SHRINK(F[13]);
         if ((F[13] &= TblComplexMask[Shrink]) == 0)
            return false;
         CompF[13] = F[13];
         int Column = FULL_TO_COLUMN(F[13]);
         int C1 = Column | FULL_TO_COLUMN(F[12]);
         int C2 = Column | FULL_TO_COLUMN(F[14]);
         F[12] &= TblMaskSingle[Column] & TblMaskDouble[C2];
         F[14] &= TblMaskSingle[Column] & TblMaskDouble[C1];
         if (TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]] != U[13])
         {
            U[13] |= TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]];
            int S = ~(F[13] & TblColumnMask[U[13]]);
            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);
         }
      }
      if (CompF[14] != F[14])
      {
         Shrink = FULL_TO_SHRINK(F[14]);
         if ((F[14] &= TblComplexMask[Shrink]) == 0)
            return false;
         CompF[14] = F[14];
         int Column = FULL_TO_COLUMN(F[14]);
         int C1 = Column | FULL_TO_COLUMN(F[12]);
         int C2 = Column | FULL_TO_COLUMN(F[13]);
         F[12] &= TblMaskSingle[Column] & TblMaskDouble[C2];
         F[13] &= TblMaskSingle[Column] & TblMaskDouble[C1];
         if (TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]] != U[14])
         {
            U[14] |= TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]];
            int S = ~(F[14] & TblColumnMask[U[14]]);
            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);
         }
      }
      if (CompF[15] != F[15])
      {
         Shrink = FULL_TO_SHRINK(F[15]);
         if ((F[15] &= TblComplexMask[Shrink]) == 0)
            return false;
         CompF[15] = F[15];
         int Column = FULL_TO_COLUMN(F[15]);
         int C1 = Column | FULL_TO_COLUMN(F[16]);
         int C2 = Column | FULL_TO_COLUMN(F[17]);
         F[16] &= TblMaskSingle[Column] & TblMaskDouble[C2];
         F[17] &= TblMaskSingle[Column] & TblMaskDouble[C1];
         if (TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]] != U[15])
         {
            U[15] |= TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]];
            int S = ~(F[15] & TblColumnMask[U[15]]);
            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);
         }
      }
      if (CompF[16] != F[16])
      {
         Shrink = FULL_TO_SHRINK(F[16]);
         if ((F[16] &= TblComplexMask[Shrink]) == 0)
            return false;
         CompF[16] = F[16];
         int Column = FULL_TO_COLUMN(F[16]);
         int C1 = Column | FULL_TO_COLUMN(F[15]);
         int C2 = Column | FULL_TO_COLUMN(F[17]);
         F[15] &= TblMaskSingle[Column] & TblMaskDouble[C2];
         F[17] &= TblMaskSingle[Column] & TblMaskDouble[C1];
         if (TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]] != U[16])
         {
            U[16] |= TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]];
            int S = ~(F[16] & TblColumnMask[U[16]]);
            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);
         }
      }
      if (CompF[17] != F[17])
      {
         Shrink = FULL_TO_SHRINK(F[17]);
         if ((F[17] &= TblComplexMask[Shrink]) == 0)
            return false;
         CompF[17] = F[17];
         int Column = FULL_TO_COLUMN(F[17]);
         int C1 = Column | FULL_TO_COLUMN(F[15]);
         int C2 = Column | FULL_TO_COLUMN(F[16]);
         F[15] &= TblMaskSingle[Column] & TblMaskDouble[C2];
         F[16] &= TblMaskSingle[Column] & TblMaskDouble[C1];
         if (TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]] != U[17])
         {
            U[17] |= TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]];
            int S = ~(F[17] & TblColumnMask[U[17]]);
            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);
         }
      }
      if (CompF[18] != F[18])
      {
         Shrink = FULL_TO_SHRINK(F[18]);
         if ((F[18] &= TblComplexMask[Shrink]) == 0)
            return false;
         CompF[18] = F[18];
         int Column = FULL_TO_COLUMN(F[18]);
         int C1 = Column | FULL_TO_COLUMN(F[19]);
         int C2 = Column | FULL_TO_COLUMN(F[20]);
         F[19] &= TblMaskSingle[Column] & TblMaskDouble[C2];
         F[20] &= TblMaskSingle[Column] & TblMaskDouble[C1];
         if (TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]] != U[18])
         {
            U[18] |= TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]];
            int S = ~(F[18] & TblColumnMask[U[18]]);
            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);
         }
      }
      if (CompF[19] != F[19])
      {
         Shrink = FULL_TO_SHRINK(F[19]);
         if ((F[19] &= TblComplexMask[Shrink]) == 0)
            return false;
         CompF[19] = F[19];
         int Column = FULL_TO_COLUMN(F[19]);
         int C1 = Column | FULL_TO_COLUMN(F[18]);
         int C2 = Column | FULL_TO_COLUMN(F[20]);
         F[18] &= TblMaskSingle[Column] & TblMaskDouble[C2];
         F[20] &= TblMaskSingle[Column] & TblMaskDouble[C1];
         if (TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]] != U[19])
         {
            U[19] |= TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]];
            int S = ~(F[19] & TblColumnMask[U[19]]);
            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);
         }
      }
      if (CompF[20] != F[20])
      {
         Shrink = FULL_TO_SHRINK(F[20]);
         if ((F[20] &= TblComplexMask[Shrink]) == 0)
            return false;
         CompF[20] = F[20];
         int Column = FULL_TO_COLUMN(F[20]);
         int C1 = Column | FULL_TO_COLUMN(F[18]);
         int C2 = Column | FULL_TO_COLUMN(F[19]);
         F[18] &= TblMaskSingle[Column] & TblMaskDouble[C2];
         F[19] &= TblMaskSingle[Column] & TblMaskDouble[C1];
         if (TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]] != U[20])
         {
            U[20] |= TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]];
            int S = ~(F[20] & TblColumnMask[U[20]]);
            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);
         }
      }
      if (CompF[21] != F[21])
      {
         Shrink = FULL_TO_SHRINK(F[21]);
         if ((F[21] &= TblComplexMask[Shrink]) == 0)
            return false;
         CompF[21] = F[21];
         int Column = FULL_TO_COLUMN(F[21]);
         int C1 = Column | FULL_TO_COLUMN(F[22]);
         int C2 = Column | FULL_TO_COLUMN(F[23]);
         F[22] &= TblMaskSingle[Column] & TblMaskDouble[C2];
         F[23] &= TblMaskSingle[Column] & TblMaskDouble[C1];
         if (TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]] != U[21])
         {
            U[21] |= TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]];
            int S = ~(F[21] & TblColumnMask[U[21]]);
            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);
         }
      }
      if (CompF[22] != F[22])
      {
         Shrink = FULL_TO_SHRINK(F[22]);
         if ((F[22] &= TblComplexMask[Shrink]) == 0)
            return false;
         CompF[22] = F[22];
         int Column = FULL_TO_COLUMN(F[22]);
         int C1 = Column | FULL_TO_COLUMN(F[21]);
         int C2 = Column | FULL_TO_COLUMN(F[23]);
         F[21] &= TblMaskSingle[Column] & TblMaskDouble[C2];
         F[23] &= TblMaskSingle[Column] & TblMaskDouble[C1];
         if (TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]] != U[22])
         {
            U[22] |= TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]];
            int S = ~(F[22] & TblColumnMask[U[22]]);
            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);
         }
      }
      if (CompF[23] != F[23])
      {
         Shrink = FULL_TO_SHRINK(F[23]);
         if ((F[23] &= TblComplexMask[Shrink]) == 0)
            return false;
         CompF[23] = F[23];
         int Column = FULL_TO_COLUMN(F[23]);
         int C1 = Column | FULL_TO_COLUMN(F[21]);
         int C2 = Column | FULL_TO_COLUMN(F[22]);
         F[21] &= TblMaskSingle[Column] & TblMaskDouble[C2];
         F[22] &= TblMaskSingle[Column] & TblMaskDouble[C1];
         if (TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]] != U[23])
         {
            U[23] |= TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]];
            int S = ~(F[23] & TblColumnMask[U[23]]);
            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);
         }
      }
      if (CompF[24] != F[24])
      {
         Shrink = FULL_TO_SHRINK(F[24]);
         if ((F[24] &= TblComplexMask[Shrink]) == 0)
            return false;
         CompF[24] = F[24];
         int Column = FULL_TO_COLUMN(F[24]);
         int C1 = Column | FULL_TO_COLUMN(F[25]);
         int C2 = Column | FULL_TO_COLUMN(F[26]);
         F[25] &= TblMaskSingle[Column] & TblMaskDouble[C2];
         F[26] &= TblMaskSingle[Column] & TblMaskDouble[C1];
         if (TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]] != U[24])
         {
            U[24] |= TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]];
            int S = ~(F[24] & TblColumnMask[U[24]]);
            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);
         }
      }
      if (CompF[25] != F[25])
      {
         Shrink = FULL_TO_SHRINK(F[25]);
         if ((F[25] &= TblComplexMask[Shrink]) == 0)
            return false;
         CompF[25] = F[25];
         int Column = FULL_TO_COLUMN(F[25]);
         int C1 = Column | FULL_TO_COLUMN(F[24]);
         int C2 = Column | FULL_TO_COLUMN(F[26]);
         F[24] &= TblMaskSingle[Column] & TblMaskDouble[C2];
         F[26] &= TblMaskSingle[Column] & TblMaskDouble[C1];
         if (TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]] != U[25])
         {
            U[25] |= TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]];
            int S = ~(F[25] & TblColumnMask[U[25]]);
            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);
         }
      }
      if (CompF[26] != F[26])
      {
         Shrink = FULL_TO_SHRINK(F[26]);
         if ((F[26] &= TblComplexMask[Shrink]) == 0)
            return false;
         CompF[26] = F[26];
         int Column = FULL_TO_COLUMN(F[26]);
         int C1 = Column | FULL_TO_COLUMN(F[24]);
         int C2 = Column | FULL_TO_COLUMN(F[25]);
         F[24] &= TblMaskSingle[Column] & TblMaskDouble[C2];
         F[25] &= TblMaskSingle[Column] & TblMaskDouble[C1];
         if (TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]] != U[26])
         {
            U[26] |= TblShrinkLow[TblShrinkSingle[Shrink] & TblColumnSingle[Column]];
            int S = ~(F[26] & TblColumnMask[U[26]]);
            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);
         }
      }
   }
   return true;
}

[zhouyundong_2012]

Code: Select all

void                GenerateSixteenClues();

int PalaceGrid[9][9] = {
   {0, 1, 2, 9, 10, 11, 18, 19, 20 },
   {3, 4, 5, 12, 13, 14, 21, 22, 23 },
   {6, 7, 8, 15, 16, 17, 24, 25, 26 },
   {27, 28, 29, 36, 37, 38, 45, 46, 47 },
   {30, 31, 32, 39, 40, 41, 48, 49, 50 },
   {33, 34, 35, 42, 43, 44, 51, 52, 53 },
   {54, 55, 56, 63, 64, 65, 72, 73, 74 },
   {57, 58, 59, 66, 67, 68, 75, 76, 77 },
   {60, 61, 62, 69, 70, 71, 78, 79, 80 },
};



void WriteFile()
{
   char str[1024] = { '\0' };

   FILE *fp = fopen("16.txt", "w+");
   for (int i = 0; i < 81; i++)
      sprintf(str, "%s%c", str, Board[i]);
   fputs(str, fp);
   fclose(fp);
}

void GenerateSixteenClues()
{
   memset(Board, '0', sizeof(Board));
   for (int X0 = 0; X0 < 9; X0++)
   {
      Board[PalaceGrid[0][X0]] = '1';
      for (int X1 = 3; X1 < 9; X1++)
      {
         Board[PalaceGrid[1][X1]] = '2';
         for (int X2 = 6; X2 < 9; X2++)
         {
            Board[PalaceGrid[2][X2]] = '3';
            for (int X3 = 0; X3 < 9; X3++)
            {
               printf("X3 = %d\n", X3);
               Board[PalaceGrid[3][X3]] = '4';
               for (int X4 = 0; X4 < 9; X4++)
               {
                  printf("X4 = %d\n", X4);
                  Board[PalaceGrid[4][X4]] = '5';
                  for (int X5 = 0; X5 < 9; X5++)
                  {
                     printf("X5 = %d\n", X5);
                     Board[PalaceGrid[5][X5]] = '6';
                     for (int X6 = 0; X6 < 9; X6++)
                     {
                        printf("X6 = %d\n", X6);
                        Board[PalaceGrid[6][X6]] = '7';
                        for (int X7 = 0; X7 < 9; X7++)
                        {
                           printf("X7 = %d\n", X7);
                           Board[PalaceGrid[7][X7]] = '8';
                           for (int X8 = 0; X8 < 9; X8++)
                           {
                              printf("X8 = %d\n", X8);
                              Board[PalaceGrid[8][X8]] = '9';
                              for (int Y0 = 0; Y0 < 9; Y0++)
                              {
                                 if (Board[PalaceGrid[4][Y0]] != '0')
                                    continue;
                                 Board[PalaceGrid[4][Y0]] = '1';
                                 for (int Y1 = 0; Y1 < 9; Y1++)
                                 {
                                    if (Board[PalaceGrid[5][Y1]] != '0')
                                       continue;
                                    Board[PalaceGrid[5][Y1]] = '2';
                                    for (int Y2 = 0; Y2 < 9; Y2++)
                                    {
                                       if (Board[PalaceGrid[3][Y2]] != '0')
                                          continue;
                                       Board[PalaceGrid[3][Y2]] = '3';
                                       for (int Y3 = 0; Y3 < 9; Y3++)
                                       {
                                          if (Board[PalaceGrid[7][Y3]] != '0')
                                             continue;
                                          Board[PalaceGrid[7][Y3]] = '4';
                                          for (int Y4 = 0; Y4 < 9; Y4++)
                                          {
                                             if (Board[PalaceGrid[8][Y4]] != '0')
                                                continue;
                                             Board[PalaceGrid[8][Y4]] = '5';
                                             for (int Y5 = 0; Y5 < 9; Y5++)
                                             {
                                                if (Board[PalaceGrid[8][Y5]] != '0')
                                                   continue;
                                                Board[PalaceGrid[8][Y5]] = '1';
                                                for (int Y6 = 0; Y6 < 9; Y6++)
                                                {
                                                   if (Board[PalaceGrid[6][Y6]] != '0')
                                                      continue;
                                                   Board[PalaceGrid[6][Y6]] = '2';
                                                   InitSodoku();
                                                   if (Calculate() == UniqAnswer)
                                                   {
                                                      WriteFile();
                                                      return;
                                                   }
                                                   Board[PalaceGrid[6][Y6]] = '0';
                                                }
                                                Board[PalaceGrid[8][Y5]] = '0';
                                             }
                                             Board[PalaceGrid[8][Y4]] = '0';
                                          }
                                          Board[PalaceGrid[7][Y3]] = '0';
                                       }
                                       Board[PalaceGrid[3][Y2]] = '0';
                                    }
                                    Board[PalaceGrid[5][Y1]] = '0';
                                 }
                                 Board[PalaceGrid[4][Y0]] = '0';
                              }
                              Board[PalaceGrid[8][X8]] = '0';
                           }
                           Board[PalaceGrid[7][X7]] = '0';
                        }
                        Board[PalaceGrid[6][X6]] = '0';
                     }
                     Board[PalaceGrid[5][X5]] = '0';
                  }
                  Board[PalaceGrid[4][X4]] = '0';
               }
               Board[PalaceGrid[3][X3]] = '0';
            }
            Board[PalaceGrid[2][X2]] = '0';
         }
         Board[PalaceGrid[1][X1]] = '0';
      }
      Board[PalaceGrid[0][X0]] = '0';
   }
}



[zhouyundong_2012]

I have found a 16-Clues sudoku.

[ronk]

I have found a 16-Clues sudoku.

April fool ... not!

[zhouyundong_2012]

Update in April 8: It seems nothing to speed up except initialize and guess. 5% improved(17 sudoku). So it works in 2.8G CPU: 3.97us average 17sudoku.

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)
#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)    ((TblShrinkMask[(v) >> 15] << 5) | TblShrinkMask[(v) & 0x7FFF]) //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 Row
   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_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             TblColumnMask[8];
extern bool             TblUniqFlag[8];
//Complex Method
extern byte             TblShrinkMask[32768];
extern int             TblComplexMask[512];
extern int             TblColumnSingle[512];
extern int             TblShrinkSingle[512];

extern void             CreateTable();

#endif