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

Programs which generate, solve, and analyze Sudoku puzzles

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

Postby zhouyundong_2012 » Wed Mar 14, 2012 3:57 pm

thanks, Afmob,
Two bugs have been fixed.
000000000000000000000000000000000000000000000000000000000000000000000000000000000
111111111111111111111111111111111111111111111111111111111111111111111111111111111
zhouyundong_2012
 
Posts: 148
Joined: 10 February 2012

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

Postby zhouyundong_2012 » Wed Mar 14, 2012 4:00 pm

After bugfix: I hope it is the last version. it doesn't affect speed. just G[33] to G[50] and CompF should be initialized to -1
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 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
zhouyundong_2012
 
Posts: 148
Joined: 10 February 2012

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

Postby zhouyundong_2012 » Wed Mar 14, 2012 4:01 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_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();
}
zhouyundong_2012
 
Posts: 148
Joined: 10 February 2012

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

Postby zhouyundong_2012 » Wed Mar 14, 2012 4:02 pm

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 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
zhouyundong_2012
 
Posts: 148
Joined: 10 February 2012

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

Postby JasonLion » Wed Mar 14, 2012 9:05 pm

WOW! Now 30% faster than JSolve on top1465.
User avatar
JasonLion
2017 Supporter
 
Posts: 642
Joined: 25 October 2007
Location: Silver Spring, MD, USA

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

Postby brit » Thu Mar 15, 2012 4:03 am

Greetings all,

First, sorry if I am annoying, I did try to share all my code.

Second, though I am in still semi-retirement due to my job taking too many hours a week, but I wanted to see Zhou's latest program. If Jason says it is 30% faster, than that is quite a feat. I have not had time to test it myself yet, maybe over the weekend.

briturner
brit
 
Posts: 1
Joined: 15 March 2012

Postby Afmob » Thu Mar 15, 2012 8:40 pm

Thank you for fixing those bugs. I've also tested your solver against the gen500k test set and it worked.

Of course, if one wants to use it for more general problems some modifications (I mentioned them before) have to be made and the cumbersome compiling procedure with Update.c should be removed.
Afmob
 
Posts: 132
Joined: 28 June 2011

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

Postby zhouyundong_2012 » Sat Mar 17, 2012 6:23 am

sorry, I don't know your means.
zhouyundong_2012
 
Posts: 148
Joined: 10 February 2012

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

Postby zhouyundong_2012 » Sat Mar 17, 2012 6:34 am

If you change code in Update.c, recompile is the better way than rewrite each place.
and if you change other code, you needn't open __ProgramWritter.
For example, you want write
Code: Select all
   for (int i = 0; i < TestCaseNumber; i++)
   {
      memcpy(Board, AllBoard[i], 81);
      InitSodoku();
      if ((Answer = Calculate()) != UniqAnswer)
         continue;
   }

you needn't redo the 3 steps.
zhouyundong_2012
 
Posts: 148
Joined: 10 February 2012

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

Postby zhouyundong_2012 » Sat Mar 17, 2012 6:36 am

1 where to download top1465? you can send to my e-mail lao_zhouxi9@163.com 3Q
2 is top1465 the most difficult?
zhouyundong_2012
 
Posts: 148
Joined: 10 February 2012

Postby Afmob » Sat Mar 17, 2012 7:39 am

Usually the solver is just a small (but important) part of a larger program where the solver is just one tool you use. So you won't rewrite the solver that often. For example, I've been using JSolve for over 2 years and I probably changed it only 4 or 5 times. It can be easily modified to solve Sudokus of abitrary size, it's easy to compile and works on Windows and Linux.

Your solver is fast but currently it's just written too specifically for a certain problem, is tedious to compile and it works only for a fixed number of Sudokus but usually you want to solve millions, billions or trillions of Sudokus but that problem shouldn't be too hard to fix.
Afmob
 
Posts: 132
Joined: 28 June 2011

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

Postby zhouyundong_2012 » Sat Mar 17, 2012 7:42 am

I find a new way to Guess, I think it will be more fast for difficult case, but some slower for easy case.

I think hard to let U means Uniq in a row not a 3*3grid. I at last find a way.
zhouyundong_2012
 
Posts: 148
Joined: 10 February 2012

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

Postby zhouyundong_2012 » Sat Mar 17, 2012 7:46 am

Yes ,that is not hard to fix. But I haven't time to do it for I am thinking how to Guess effeciently. And I think I got it now.
zhouyundong_2012
 
Posts: 148
Joined: 10 February 2012

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

Postby zhouyundong_2012 » Sat Mar 17, 2012 7:50 am

I have also made a visible software,it includes Killer, GT/LT, Extra, and Mix of them.
But I don't know how to post it here.
zhouyundong_2012
 
Posts: 148
Joined: 10 February 2012

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

Postby zhouyundong_2012 » Sat Mar 17, 2012 8:21 am

I am happy to get this conclusion:

111 110 000
000 000 010
011 001 000

//Shrink
011 100 011 => 000 100 000 (TblShrinkSingle)
//Column
111 111 010 => 100 100 100 (TblColumnSingle)

And of them
===> 000 100 000

000 100 000 => 010 (TblShrinkLow)

010 means the second Row is Uniq
zhouyundong_2012
 
Posts: 148
Joined: 10 February 2012

PreviousNext

Return to Software