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

Programs which generate, solve, and analyze Sudoku puzzles

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

Postby zhouyundong_2012 » Fri Sep 02, 2016 11:11 am

#include "StdAfx.h"
#include "NewtonCDS.h"

CNewtonCDS::CNewtonCDS(int N, const CComplex& C0) : N(N), C0(C0)
{
}

CNewtonCDS::~CNewtonCDS()
{
}

int CNewtonCDS::IterBrief(CComplex cinit, CComplex& ret, double dL[4])
{
CComplex c1(cinit);
CComplex c2;

int i, t = 0;
for (i = 1; i <= m_nMaxIter; i++)
{
//调用牛顿迭代公式
IterFormula(c1, c2);

double product = (c2 - c1).GetProduct();
if (product < 0.00001)
{
if (++t > 2) dL[3] = product / 0.00001; //找到近似解
if (i > m_nMinIter) break;
}
if (i == 1)
{
ret = c2 - c1;
dL[0] = ret.GetModule();
}
if (i == m_nMinIter)
{
dL[1] = (c2 - c1).GetModule();
dL[2] = c2.GetModule();
}
c1 = c2;
}
return i - m_nMaxIter / N;
}

void CNewtonCDS::Draw(CCanvas *pCanvas)
{
CImage *pImage = pCanvas->GetImage();
CComplex cinit; //迭代的初值

//从中间开始向两边绘制时使用的变量
for (int n = 1; n < pImage->Height(); n++)
{
int B = pImage->Height() / 2 - (1 - (n % 2) * 2) * n / 2;
for (int A = 0; A < pImage->Width(); A++)
{
cinit.a = (m_end.a - m_start.a) * A / pImage->Width() + m_start.a;
cinit.b = (m_end.b - m_start.b) * B / pImage->Height() + m_start.b;
//防止出现(0, 0)点
if (cinit.a == 0) cinit.a = 1.0E-150;
if (cinit.b == 0) cinit.b = 1.0E-150;

COLORREF color = GetColor(cinit);
pImage->SetPixel(A, B, color);
}
}
}

COLORREF CNewtonCDS::GetColor(CComplex cinit)
{
byte b = GetBValue(m_color);
byte g = GetGValue(m_color);
byte r = GetRValue(m_color);

CComplex ret;
double dL[4] = { 0 };

//计算迭代后的点
int i = IterBrief(cinit, ret, dL);

int newb = 256 - abs((int)abs(b - (2 * r - 256) * (log(abs(ret.a))) * m_fFactor) % 512 - 256);
int newg = 256 - abs((int)abs(g - (2 * b - 256) * (log(abs(dL[0]))) * m_fFactor) % 512 - 256);
int newr = 256 - abs((int)abs(r - (2 * g - 256) * (log(abs(ret.b))) * m_fFactor) % 512 - 256);

return BGRA(max(0, min(255, newb)), max(0, min(255, newg)), max(0, min(255, newr)), 255);
}
zhouyundong_2012
 
Posts: 148
Joined: 10 February 2012

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

Postby zhouyundong_2012 » Fri Sep 02, 2016 11:12 am

#include "StdAfx.h"

CPolygonShape::CPolygonShape(int nCount, LPPOINT lpPoints)
: m_nCount(nCount), lpPoints(lpPoints)
{
}

CPolygonShape::~CPolygonShape()
{
}

void CPolygonShape::_Draw(CCanvas *pCanvas)
{
for (int i = 0; i < m_nCount; i++)
{
int j = (i + 1) % m_nCount;
CLineShape tLineShape(lpPoints[i].x, lpPoints[i].y, lpPoints[j].x, lpPoints[j].y);
tLineShape.SetColor(m_color); //继承多边形的颜色
tLineShape.Draw(pCanvas);
}
g_pZ2coo->Redraw(pCanvas);
}

void CPolygonShape::_Fill(CCanvas *pCanvas)
{
int y0, y1; //扫描线的最大和最小y坐标
LPEdge pAET; //活化边表头指针
LPEdge *pET; //边表头指针
pAET = new Edge; //初始化表头指针
pAET->pNext = NULL; //获取y方向扫描线边界
y0 = y1 = lpPoints[0].y;
for (int i = 1; i < m_nCount; i++)
{
if (lpPoints[i].y < y0)
y0 = lpPoints[i].y;
else if (lpPoints[i].y > y1)
y1 = lpPoints[i].y;
}
if (y0 >= y1)
return;

//初始化边表,第一个结点不用,这样可以保证pET[i]非空
pET = new LPEdge[y1 - y0 + 1];
for (int i = 0; i <= y1 - y0; i++)
{
pET[i] = new Edge;
pET[i]->pNext = NULL;
}
_BuildET(pET, y0, y1);
//扫描
for (int i = y0; i <= y1; i++)
{
LPEdge peg0 = pET[i-y0]->pNext;
LPEdge peg1 = pET[i-y0];
if (peg0) //有新边加入
{
while (peg1->pNext)
peg1 = peg1->pNext;
peg1->pNext = pAET->pNext;
pAET->pNext = peg0;
}
_SortAET(pAET);
//遍历活边表,画线
peg0 = pAET;
while (peg0->pNext && peg0->pNext->pNext)
{
FillLine(ROUND(peg0->pNext->x), ROUND(peg0->pNext->pNext->x), i);
peg0 = peg0->pNext->pNext;
}
//把ymax = i的节点从活边表删除并把每个节点的x值递增dx
peg0 = pAET;
while (peg0->pNext)
{
if (peg0->pNext->ymax < i + 2)
{
peg1 = peg0->pNext;
peg0->pNext = peg0->pNext->pNext;
//删除
delete peg1;
continue;
}
peg0->pNext->x += peg0->pNext->dx; //把每个节点的x值递增dx
peg0 = peg0->pNext;
}
}
//删除边表
for (int i = 0; i < y1 - y0 + 1; i++)
if (pET[i])
delete pET[i];
if (pAET)
delete pAET;
if (pET)
delete[] pET;

//镶边以防止边界损失
Draw(pCanvas);

g_pZ2coo->Redraw(pCanvas);
}

void CPolygonShape::_BuildET(LPEdge *pET, int y0, int y1)
{
for(int i = 0;i < m_nCount;i++)
{
int j = (i + 1) % m_nCount;
if (lpPoints[i].y != lpPoints[j].y) //加入非水平边
{
LPEdge peg; //指向该边的指针
LPEdge ppeg; //指向边指针的指针
//构造边
peg = new Edge;
int k = (lpPoints[i].y > lpPoints[j].y) ? i : j;
peg->ymax = lpPoints[k].y; //该边最大y坐标
k = (k == j) ? i : j;
peg->x = (double)lpPoints[k].x; //该边与扫描线焦点x坐标
peg->dx = (double)(lpPoints[i].x - lpPoints[j].x) / (lpPoints[i].y - lpPoints[j].y); //该边斜率的倒数
peg->pNext = NULL; //插入边
ppeg = pET[lpPoints[k].y-y0];
while (ppeg->pNext)
ppeg = ppeg->pNext;
ppeg->pNext = peg;
}
}
}

void CPolygonShape::_SortAET(LPEdge pAET)
{
LPEdge peg0 = pAET;
while (peg0->pNext)
{
LPEdge pegmax = peg0;
LPEdge peg1 = peg0;
LPEdge pegi = NULL;
while (peg1->pNext)
{
if (peg1->pNext->x > pegmax->pNext->x)
pegmax = peg1;
peg1 = peg1->pNext;
}
pegi = pegmax->pNext;
pegmax->pNext = pegi->pNext;
pegi->pNext = pAET->pNext;
pAET->pNext = pegi;
if (peg0 == pAET)
peg0 = pegi;
}
}
zhouyundong_2012
 
Posts: 148
Joined: 10 February 2012

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

Postby zhouyundong_2012 » Fri Sep 02, 2016 11:12 am

#include "PRIVATE_NAMESPACE_BEGIN"

#ifndef __Move_h__
#define __Move_h__

static TMove *MoveList[MaxCrackDepth][MaxMove] = { 0 };

static int Trial[MaxCrackDepth];
static int Taken[MaxCrackDepth];
static int trial[MaxCrackDepth];

static std::vector<TMove> vecTestMove;


static bool CreateMoveList();
static void DeleteMoveList();

static void AddMoveRed(int src, int dest, int check, int bian = 0);
static void AddKillRed(int src, int dest, int check, int bian = 0);
static void AddMoveBlk(int src, int dest, int bian = 0);
static void AddKillBlk(int src, int dest, int bian = 0);

#include "MoveList.cpp"

#endif

#include "PRIVATE_NAMESPACE_END"
zhouyundong_2012
 
Posts: 148
Joined: 10 February 2012

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

Postby zhouyundong_2012 » Fri Sep 02, 2016 11:13 am

#ifndef __WChessAI_h__
#define __WChessAI_h__

#define VBW 8 //棋盘宽度
#define VBH 8 //棋盘高度

enum EPieceKind { NONE,
R_ROOK, R_HORSE, R_BISHOP, R_QUEEN, R_PAWN, R_KING,
B_ROOK, B_HORSE, B_BISHOP, B_QUEEN, B_PAWN, B_KING,
};

#define MaxCrackDepth 100

//破解结果公共定义
#define NOANSWER 0
#define REDLOSE 1
#define BLKLOSE 2
#define NOLOSE 3
#define INTERRUPT 4
#define FURTHER 5
#define NOFURTHER 6
#define FULLASTODE 7
#define TIMEOUT 8
#define BADFILE 9

struct TPiece {
int kind;
int pos;
TPiece *next;
TPiece *prev;
};

struct TCrackParam {
int *board;
bool bPesudo;
int nMaxDepth;
int nFurther;
int src;
int dest;
int bian;
};

struct TCrackResult {
int nRound;
int nAstodeSize;
int nSpendTime;
int src;
int dest;
int bian;
};

bool WChess_Initial();
void WChess_Release();
void WChess_SetWindow(CWindow *_window);
void WChess_SetMsgId(UINT uMsgId);


bool WChess_InitThreadRFCrack(TCrackParam *pCrackParam);
bool WChess_InitThreadBFCrack(TCrackParam *pCrackParam);
void WChess_WaitForThreadCrack();
void WChess_ExitThreadCrack();

int WChess_GetThinkDepth();
int WChess_GetAstodeSize();
int WChess_GetSpendTime();
TCrackResult& WChess_GetCrackResult();

#endif
zhouyundong_2012
 
Posts: 148
Joined: 10 February 2012

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

Postby zhouyundong_2012 » Fri Sep 02, 2016 11:13 am

#include "StdAfx.h"
#include "Table.h"

static void CreateTblBitIndex()
{
TblBitIndex = new int[67];
memset(TblBitIndex, 0, sizeof(int[67]));

qword T[67] = { 0 };
for (int i = 0; i < 64; i++)
{
T[i] = 1;
for (int j = 0; j < i; j++)
T[i] = (T[i] << 1) % 67;
}

for (int i = 0; i < 67; i++)
{
if (T[i] == 0)
continue;
TblBitIndex[T[i]] = i;
}
}

static void CreateTblPieceBitmap()
{
int RHBQKMask = (1 << R_ROOK) | (1 << R_HORSE) | (1 << R_BISHOP) | (1 << R_QUEEN) | (1 << R_KING)
| (1 << B_ROOK) | (1 << B_HORSE) | (1 << B_BISHOP) | (1 << B_QUEEN) | (1 << B_KING);

TblPieceBitmap = new int[64];
memset(TblPieceBitmap, 0, sizeof(int [64]));

for (int i = 0; i < 64; i++)
{
if ((i >> 3) != 0 && (i >> 3) != 7)
{
TblPieceBitmap[i] |= 1 << R_PAWN;
TblPieceBitmap[i] |= 1 << B_PAWN;
}
TblPieceBitmap[i] |= RHBQKMask; //车马相后王
}
}

static void CreateTblCharToPiece()
{
TblCharToPiece = new byte[256];
memset(TblCharToPiece, 0, sizeof(byte [256]));

TblCharToPiece['R'] = R_ROOK;
TblCharToPiece['N'] = R_HORSE;
TblCharToPiece['B'] = R_BISHOP;
TblCharToPiece['Q'] = R_QUEEN;
TblCharToPiece['P'] = R_PAWN;
TblCharToPiece['K'] = R_KING;
TblCharToPiece['r'] = B_ROOK;
TblCharToPiece['n'] = B_HORSE;
TblCharToPiece['b'] = B_BISHOP;
TblCharToPiece['q'] = B_QUEEN;
TblCharToPiece['p'] = B_PAWN;
TblCharToPiece['k'] = B_KING;
}

static void CreateTblPieceToChar()
{
TblPieceToChar = new char[15];

TblPieceToChar[0] = 0;
TblPieceToChar[R_ROOK] = 'R';
TblPieceToChar[R_HORSE] = 'N';
TblPieceToChar[R_BISHOP] = 'B';
TblPieceToChar[R_QUEEN] = 'Q';
TblPieceToChar[R_PAWN] = 'P';
TblPieceToChar[R_KING] = 'K';
TblPieceToChar[B_ROOK] = 'r';
TblPieceToChar[B_HORSE] = 'n';
TblPieceToChar[B_BISHOP] = 'b';
TblPieceToChar[B_QUEEN] = 'q';
TblPieceToChar[B_PAWN] = 'p';
TblPieceToChar[B_KING] = 'k';
}

static void CreateTblQueenPath()
{
TblQueenPath = new qword[4096];
memset(TblQueenPath, 0, sizeof(qword[4096]));

for (int i = 0; i < 64; i++)
{
int x1 = i & 7;
int y1 = i >> 3;
for (int j = 0; j < 64; j++)
{
int x2 = j & 7;
int y2 = j >> 3;

if (x1 == x2 && y1 == y2)
continue;
//在同一水平线上
else if (y1 == y2)
{
for (int k = min(x1, x2) + 1; k < max(x1, x2); k++)
TblQueenPath[(i << 6) + j] |= (qword)1 << ((y1 << 3) + k);
}
//在同一垂直线上
else if (x1 == x2)
{
for (int k = min(y1, y2) + 1; k < max(y1, y2); k++)
TblQueenPath[(i << 6) + j] |= (qword)1 << ((k << 3) + x1);
}
//在同一斜线上
else if (x1 - x2 == y1 - y2)
{
for (int k = min(x1, x2) + 1; k < max(x1, x2); k++)
TblQueenPath[(i << 6) + j] |= (qword)1 << (((min(y1, y2) + k - min(x1, x2)) << 3) + k);
}
//在同一反斜线上
else if (x1 - x2 == y2 - y1)
{
for (int k = min(x1, x2) + 1; k < max(x1, x2); k++)
TblQueenPath[(i << 6) + j] |= (qword)1 << (((max(y1, y2) - k + min(x1, x2)) << 3) + k);
}
else
TblQueenPath[(i << 6) + j] = (qword)-1;
}
}
}

static void CreateTblRookPath()
{
TblRookPath = new qword[4096];
memset(TblRookPath, 0, sizeof(qword[4096]));

for (int i = 0; i < 64; i++)
{
int x1 = i & 7;
int y1 = i >> 3;
for (int j = 0; j < 64; j++)
{
int x2 = j & 7;
int y2 = j >> 3;

if (x1 == x2 && y1 == y2)
continue;
//在同一水平线上
else if (y1 == y2)
{
for (int k = min(x1, x2) + 1; k < max(x1, x2); k++)
TblRookPath[(i << 6) + j] |= (qword)1 << ((y1 << 3) + k);
}
//在同一垂直线上
else if (x1 == x2)
{
for (int k = min(y1, y2) + 1; k < max(y1, y2); k++)
TblRookPath[(i << 6) + j] |= (qword)1 << ((k << 3) + x1);
}
else
TblRookPath[(i << 6) + j] = (qword)-1;
}
}
}

static void CreateTblBishopPath()
{
TblBishopPath = new qword[4096];
memset(TblBishopPath, 0, sizeof(qword[4096]));

for (int i = 0; i < 64; i++)
{
int x1 = i & 7;
int y1 = i >> 3;
for (int j = 0; j < 64; j++)
{
int x2 = j & 7;
int y2 = j >> 3;

if (x1 == x2 && y1 == y2)
continue;
//在同一斜线上
else if (x1 - x2 == y1 - y2)
{
for (int k = min(x1, x2) + 1; k < max(x1, x2); k++)
TblBishopPath[(i << 6) + j] |= (qword)1 << (((min(y1, y2) + k - min(x1, x2)) << 3) + k);
}
//在同一反斜线上
else if (x1 - x2 == y2 - y1)
{
for (int k = min(x1, x2) + 1; k < max(x1, x2); k++)
TblBishopPath[(i << 6) + j] |= (qword)1 << (((max(y1, y2) - k + min(x1, x2)) << 3) + k);
}
else
TblBishopPath[(i << 6) + j] = (qword)-1;
}
}
}

static void CreateTblDirection()
{
TblDirection = new int[4096];
memset(TblDirection, 0, sizeof(int[4096]));

for (int i = 0; i < 64; i++)
{
int x1 = i & 7;
int y1 = i >> 3;
for (int j = 0; j < 64; j++)
{
int x2 = j & 7;
int y2 = j >> 3;

if (y1 == y2)
TblDirection[(i << 6) + j] = 1;
if (x1 == x2)
TblDirection[(i << 6) + j] = 2;
if (x1 - x2 == y1 - y2)
TblDirection[(i << 6) + j] = 3;
if (x1 - x2 == y2 - y1)
TblDirection[(i << 6) + j] = 4;
}
}
}

static void CreateTblRookCrossGrid()
{
for (int i = 0; i < 2; i++)
{
TblRookCrossGrid[i] = new byte[4096];
memset(TblRookCrossGrid[i], 0x40, sizeof(byte[4096]));
}

for (int i = 0; i < 64; i++)
{
int x1 = i & 7;
int y1 = i >> 3;
for (int j = 0; j < 64; j++)
{
int x2 = j & 7;
int y2 = j >> 3;
TblRookCrossGrid[0][(i << 6) + j] = (y1 << 3) + x2;
TblRookCrossGrid[1][(i << 6) + j] = (y2 << 3) + x1;
}
}
}

static void CreateTblBishopCrossGrid()
{
for (int i = 0; i < 2; i++)
{
TblBishopCrossGrid[i] = new byte[4096];
memset(TblBishopCrossGrid[i], 0x40, sizeof(byte[4096]));
}

for (int i = 0; i < 64; i++)
{
int x1 = i & 7;
int y1 = i >> 3;
for (int j = 0; j < 64; j++)
{
int x2 = j & 7;
int y2 = j >> 3;

for (int k = 0; k < 64; k++)
{
int xk = k & 7;
int yk = k >> 3;
if (abs(x1 - xk) == abs(y1 - yk) && abs(x2 - xk) == abs(y2 - yk))
{
if (TblBishopCrossGrid[0][(i << 6) + j] == 0x40)
TblBishopCrossGrid[0][(i << 6) + j] = k;
else
TblBishopCrossGrid[1][(i << 6) + j] = k;
}
}
}
}
}

static void CreateTblRookCrossPath()
{
for (int i = 0; i < 2; i++)
{
TblRookCrossPath[i] = new qword[4096];
memset(TblRookCrossPath[i], 0xFF, sizeof(qword[4096]));
}

for (int i = 0; i < 64; i++)
{
int x1 = i & 7;
int y1 = i >> 3;
for (int j = 0; j < 64; j++)
{
int x2 = j & 7;
int y2 = j >> 3;
if (x1 == x2 || y1 == y2)
continue;
//不在同一直线上
int intersect1 = TblRookCrossGrid[0][(i << 6) + j];
if (intersect1 != 0x40)
{
TblRookCrossPath[0][(i << 6) + j] = TblRookPath[(i << 6) + intersect1]
| TblRookPath[(j << 6) + intersect1];
}
//不在同一直线上
int intersect2 = TblRookCrossGrid[1][(i << 6) + j];
if (intersect2 != 0x40)
{
TblRookCrossPath[1][(i << 6) + j] = TblRookPath[(i << 6) + intersect2]
| TblRookPath[(j << 6) + intersect2];
}
}
}
}

static void CreateTblBishopCrossPath()
{
for (int i = 0; i < 2; i++)
{
TblBishopCrossPath[i] = new qword[4096];
memset(TblBishopCrossPath[i], 0xFF, sizeof(qword[4096]));
}

for (int i = 0; i < 64; i++)
{
int x1 = i & 7;
int y1 = i >> 3;
for (int j = 0; j < 64; j++)
{
int x2 = j & 7;
int y2 = j >> 3;
if (x1 - x2 == y1 - y2 || x1 - x2 == y2 - y1)
continue;
//不在同一斜线上
int intersect3 = TblBishopCrossGrid[0][(i << 6) + j];
if (intersect3 != 0x40)
{
TblBishopCrossPath[0][(i << 6) + j] = TblBishopPath[(i << 6) + intersect3]
| TblBishopPath[(j << 6) + intersect3];
}
//不在同一斜线上
int intersect4 = TblBishopCrossGrid[1][(i << 6) + j];
if (intersect4 != 0x40)
{
TblBishopCrossPath[1][(i << 6) + j] = TblBishopPath[(i << 6) + intersect4]
| TblBishopPath[(j << 6) + intersect4];
}
}
}
}

static void CreateTblQueenCrossGridBtmp()
{
TblQueenCrossGridBtmp = new qword[4096];
memset(TblQueenCrossGridBtmp, 0, sizeof(qword[4096]));

for (int i = 0; i < 64; i++)
{
for (int j = 0; j < 64; j++)
{
for (int k = 0; k < 64; k++)
{
if (TblQueenPath[(i << 6) + k] != (qword)-1 && TblQueenPath[(j << 6) + k] != (qword)-1)
{
if (TblQueenPath[(i << 6) + j] != (qword)-1)
{
//同一直线上必须离开直线
if ((TblQueenPath[(i << 6) + j] & ((qword)1 << k)) != 0
|| (TblQueenPath[(i << 6) + k] & ((qword)1 << j)) != 0
|| (TblQueenPath[(j << 6) + k] & ((qword)1 << i)) != 0)
continue;
}
TblQueenCrossGridBtmp[(i << 6) + j] |= (qword)1 << k;
}
}
}
}
}

static void CreateTblHorseCheck()
{
TblHorseChkGrid1 = new byte[4096];
memset(TblHorseChkGrid1, 0x40, sizeof(byte [4096]));
TblHorseChkGrid2 = new byte[4096];
memset(TblHorseChkGrid2, 0x40, sizeof(byte [4096]));

for (int i = 0; i < 64; i++)
{
int x1 = i & 7;
int y1 = i >> 3;
for (int j = 0; j < 64; j++)
{
int x2 = j & 7;
int y2 = j >> 3;
for (int pos = 0; pos < 64; pos++)
{
int px = pos & 7;
int py = pos >> 3;
if ((abs(x1 - px) == 2 && abs(y1 - py) == 1 || abs(x1 - px) == 1 && abs(y1 - py) == 2)
&& (abs(x2 - px) == 2 && abs(y2 - py) == 1 || abs(x2 - px) == 1 && abs(y2 - py) == 2))
{
if (TblHorseChkGrid1[(i << 6) + j] == 0x40)
TblHorseChkGrid1[(i << 6) + j] = pos;
else
TblHorseChkGrid2[(i << 6) + j] = pos;
}
}
}
}
}

static void CreateTblHorseChkIdx()
{
TblHorseChkIdx = new byte[4096];
memset(TblHorseChkIdx, 0, sizeof(byte [4096]));

for (int i = 0; i < 64; i++)
{
int x1 = i & 7;
int y1 = i >> 3;
for (int j = 0; j < 64; j++)
{
int x2 = j & 7;
int y2 = j >> 3;
if (abs(x1 - x2) == 2 && abs(y1 - y2) == 1 || abs(x1 - x2) == 1 && abs(y1 - y2) == 2)
TblHorseChkIdx[(i << 6) + j] = 1;
}
}
}

static void CreateTblKingChkIdx()
{
TblKingChkIdx = new byte[4096];
memset(TblKingChkIdx, 0, sizeof(byte[4096]));

for (int i = 0; i < 64; i++)
{
int x1 = i & 7;
int y1 = i >> 3;
for (int j = 0; j < 64; j++)
{
int x2 = j & 7;
int y2 = j >> 3;
if (abs(x1 - x2) <= 1 && abs(y1 - y2) <= 1)
TblKingChkIdx[(i << 6) + j] = 1;
}
}
}

static void CreateTblEludeChkIdx()
{
TblEludeChkIdx = new byte[4096];
memset(TblEludeChkIdx, 0, sizeof(byte[4096]));

for (int i = 0; i < 64; i++)
{
int x1 = i & 7;
int y1 = i >> 3;
for (int j = 0; j < 64; j++)
{
int x2 = j & 7;
int y2 = j >> 3;
if (y1 == y2)
{
if (abs(x1 - x2) > 1)
TblEludeChkIdx[(i << 6) + j] = 1;
}
else if (x1 == x2)
{
if (abs(y1 - y2) > 1)
TblEludeChkIdx[(i << 6) + j] = 2;
}
else if (x1 - x2 == y1 - y2)
{
if (abs(x1 - x2) > 1)
TblEludeChkIdx[(i << 6) + j] = 3;
}
else if (x1 - x2 == y2 - y1)
{
if (abs(x1 - x2) > 1)
TblEludeChkIdx[(i << 6) + j] = 4;
}
if (TblKingChkIdx[(i << 6) + j] == 1)
{
if (x2 - x1 == 1 && y2 - y1 == 1)
TblEludeChkIdx[(i << 6) + j] = 0 + 5;
if (x2 - x1 == 1 && y2 - y1 == 0)
TblEludeChkIdx[(i << 6) + j] = 1 + 5;
if (x2 - x1 == 1 && y2 - y1 == -1)
TblEludeChkIdx[(i << 6) + j] = 2 + 5;
if (x2 - x1 == 0 && y2 - y1 == -1)
TblEludeChkIdx[(i << 6) + j] = 3 + 5;
if (x2 - x1 == -1 && y2 - y1 == -1)
TblEludeChkIdx[(i << 6) + j] = 4 + 5;
if (x2 - x1 == -1 && y2 - y1 == 0)
TblEludeChkIdx[(i << 6) + j] = 5 + 5;
if (x2 - x1 == -1 && y2 - y1 == 1)
TblEludeChkIdx[(i << 6) + j] = 6 + 5;
if (x2 - x1 == 0 && y2 - y1 == 1)
TblEludeChkIdx[(i << 6) + j] = 7 + 5;
}
}
}
}

static void CreateTblRookBlock()
{
TblRookBlock1 = new byte[262144];
memset(TblRookBlock1, 0x40, sizeof(byte[262144]));
TblRookBlock2 = new byte[262144];
memset(TblRookBlock2, 0x40, sizeof(byte[262144]));

for (int i = 0; i < 64; i++)
{
for (int j = 0; j < 64; j++)
{
if (TblRookPath[(i << 6) + j] != (qword)-1)
{
for(int k = 0; k < 64; k++)
{
if ((TblRookPath[(i << 6) + j] & ((qword)1 << k)) == 0)
continue;
for (int pos = 0; pos < 64; pos++)
{
if (TblRookPath[(k << 6) + pos] == (qword)-1)
continue;
TblRookBlock1[(((i << 6) + j) << 6) + pos] = k;
}
}
}
if (TblBishopPath[(i << 6) + j] != (qword)-1)
{
for(int k = 0; k < 64; k++)
{
if ((TblBishopPath[(i << 6) + j] & ((qword)1 << k)) == 0)
continue;
for (int pos = 0; pos < 64; pos++)
{
if (TblRookPath[(k << 6) + pos] == (qword)-1)
continue;
if (TblRookBlock1[(((i << 6) + j) << 6) + pos] == 0x40)
TblRookBlock1[(((i << 6) + j) << 6) + pos] = k;
else
TblRookBlock2[(((i << 6) + j) << 6) + pos] = k;
}
}
}
}
}
}

static void CreateTblHorseBlock()
{
TblHorseBlock1 = new byte[262144];
memset(TblHorseBlock1, 0x40, sizeof(byte[262144]));
TblHorseBlock2 = new byte[262144];
memset(TblHorseBlock2, 0x40, sizeof(byte[262144]));

for (int i = 0; i < 64; i++)
{
for (int j = 0; j < 64; j++)
{
if (TblRookPath[(i << 6) + j] != (qword)-1)
{
for(int k = 0; k < 64; k++)
{
if ((TblRookPath[(i << 6) + j] & ((qword)1 << k)) == 0)
continue;
for (int pos = 0; pos < 64; pos++)
{
if (TblHorseChkIdx[(pos << 6) + k] == 0)
continue;
if (TblHorseBlock1[(((i << 6) + j) << 6) + pos] == 0x40)
TblHorseBlock1[(((i << 6) + j) << 6) + pos] = k;
else
TblHorseBlock2[(((i << 6) + j) << 6) + pos] = k;
}
}
}
if (TblBishopPath[(i << 6) + j] != (qword)-1)
{
for(int k = 0; k < 64; k++)
{
if ((TblBishopPath[(i << 6) + j] & ((qword)1 << k)) == 0)
continue;
for (int pos = 0; pos < 64; pos++)
{
if (TblHorseChkIdx[(pos << 6) + k] == 0)
continue;
if (TblHorseBlock1[(((i << 6) + j) << 6) + pos] == 0x40)
TblHorseBlock1[(((i << 6) + j) << 6) + pos] = k;
else
TblHorseBlock2[(((i << 6) + j) << 6) + pos] = k;
}
}
}
}
}
}

static void CreateTblBishopBlock()
{
TblBishopBlock1 = new byte[262144];
memset(TblBishopBlock1, 0x40, sizeof(byte[262144]));
TblBishopBlock2 = new byte[262144];
memset(TblBishopBlock2, 0x40, sizeof(byte[262144]));

for (int i = 0; i < 64; i++)
{
for (int j = 0; j < 64; j++)
{
if (TblRookPath[(i << 6) + j] != (qword)-1)
{
for(int k = 0; k < 64; k++)
{
if ((TblRookPath[(i << 6) + j] & ((qword)1 << k)) == 0)
continue;
for (int pos = 0; pos < 64; pos++)
{
if (TblBishopPath[(k << 6) + pos] == (qword)-1)
continue;
if (TblBishopBlock1[(((i << 6) + j) << 6) + pos] == 0x40)
TblBishopBlock1[(((i << 6) + j) << 6) + pos] = k;
else
TblBishopBlock2[(((i << 6) + j) << 6) + pos] = k;
}
}
}
if (TblBishopPath[(i << 6) + j] != (qword)-1)
{
for(int k = 0; k < 64; k++)
{
if ((TblBishopPath[(i << 6) + j] & ((qword)1 << k)) == 0)
continue;
for (int pos = 0; pos < 64; pos++)
{
if (TblBishopPath[(k << 6) + pos] == (qword)-1)
continue;
TblBishopBlock1[(((i << 6) + j) << 6) + pos] = k;
}
}
}
}
}
}

static void CreateTblBlkPawnBlock()
{
TblBlkPawnBlock = new byte[262144];
memset(TblBlkPawnBlock, 0x40, sizeof(byte[262144]));

for (int i = 0; i < 64; i++)
{
for (int j = 0; j < 64; j++)
{
if (TblRookPath[(i << 6) + j] != (qword)-1)
{
for(int k = 0; k < 64; k++)
{
if ((TblRookPath[(i << 6) + j] & ((qword)1 << k)) == 0)
continue;
for (int pos = 0; pos < 64; pos++)
{
if (pos - 8 != k)
continue;
TblBlkPawnBlock[(((i << 6) + j) << 6) + pos] = k;
}
}
}
if (TblBishopPath[(i << 6) + j] != (qword)-1)
{
for(int k = 0; k < 64; k++)
{
if ((TblBishopPath[(i << 6) + j] & ((qword)1 << k)) == 0)
continue;
for (int pos = 0; pos < 64; pos++)
{
if (pos - 8 != k)
continue;
TblBlkPawnBlock[(((i << 6) + j) << 6) + pos] = k;
}
}
}
}
}
}

static void CreateTblBlkPawnBlock2()
{
TblBlkPawnBlock2 = new byte[262144];
memset(TblBlkPawnBlock2, 0x40, sizeof(byte[262144]));

for (int i = 0; i < 64; i++)
{
for (int j = 0; j < 64; j++)
{
if (TblRookPath[(i << 6) + j] != (qword)-1)
{
for(int k = 0; k < 64; k++)
{
if ((TblRookPath[(i << 6) + j] & ((qword)1 << k)) == 0)
continue;
for (int pos = 0; pos < 64; pos++)
{
if (pos < 48 || pos - 16 != k)
continue;
TblBlkPawnBlock2[(((i << 6) + j) << 6) + pos] = k;
}
}
}
if (TblBishopPath[(i << 6) + j] != (qword)-1)
{
for(int k = 0; k < 64; k++)
{
if ((TblBishopPath[(i << 6) + j] & ((qword)1 << k)) == 0)
continue;
for (int pos = 0; pos < 64; pos++)
{
if (pos < 48 || pos - 16 != k)
continue;
TblBlkPawnBlock2[(((i << 6) + j) << 6) + pos] = k;
}
}
}
}
}
}

static void CreateTblHorseMove()
{
TblHorseMove = new byte[64];
memset(TblHorseMove, 0, sizeof(byte[64]));

int T[8] = { +17, +10, -6, -15, -17, -10, +6, +15, };
for (int i = 0; i < 64; i++)
{
for (int j = 0; j < 8; j++)
{
if (i + T[j] >= 0 && i + T[j] < 64)
{
int dest = i + T[j];
if (abs((dest & 7) - (i & 7)) <= 2 && abs((dest >> 3) - (i >> 3)) <= 2)
TblHorseMove[i] |= 1 << j;
}
}
}
}

static void CreateTblKingMove()
{
TblKingMove = new byte[64];
memset(TblKingMove, 0, sizeof(byte[64]));

int T[8] = { +9, +1, -7, -8, -9, -1, +7, +8, };
for (int i = 0; i < 64; i++)
{
for (int j = 0; j < 8; j++)
{
if (i + T[j] >= 0 && i + T[j] < 64)
{
int dest = i + T[j];
if (abs((dest & 7) - (i & 7)) <= 1 && abs((dest >> 3) - (i >> 3)) <= 1)
TblKingMove[i] |= 1 << j;
}
}
}
}

static void CreateTblKingAway()
{
TblKingAway = new byte[4096];
memset(TblKingAway, 0, sizeof(byte[4096]));

for (int i = 0; i < 64; i++)
{
int x1 = i & 7;
int y1 = i >> 3;
for (int j = 0; j < 64; j++)
{
int x2 = j & 7;
int y2 = j >> 3;
TblKingAway[(i << 6) + j] = max(abs(x1 - x2), abs(y1 - y2));
}
}
}

static void CreateTblMaxKingAway()
{
TblMaxKingAway = new byte[64];
memset(TblMaxKingAway, 0, sizeof(byte[64]));

for (int i = 0; i < 64; i++)
{
TblMaxKingAway[i] = max(TblMaxKingAway[i], TblKingAway[(i << 6) + 0]);
TblMaxKingAway[i] = max(TblMaxKingAway[i], TblKingAway[(i << 6) + 7]);
TblMaxKingAway[i] = max(TblMaxKingAway[i], TblKingAway[(i << 6) + 54]);
TblMaxKingAway[i] = max(TblMaxKingAway[i], TblKingAway[(i << 6) + 63]);
}
}

void CreateAllTable()
{
::CreateTblBitIndex();
::CreateTblPieceBitmap();
::CreateTblCharToPiece();
::CreateTblPieceToChar();
::CreateTblQueenPath();
::CreateTblRookPath();
::CreateTblBishopPath();
::CreateTblDirection();
::CreateTblRookCrossGrid();
::CreateTblBishopCrossGrid();
::CreateTblRookCrossPath();
::CreateTblBishopCrossPath();
::CreateTblQueenCrossGridBtmp();
::CreateTblHorseChkIdx();
::CreateTblKingChkIdx();
::CreateTblEludeChkIdx();
::CreateTblHorseCheck();
::CreateTblRookBlock();
::CreateTblHorseBlock();
::CreateTblBishopBlock();
::CreateTblBlkPawnBlock();
::CreateTblBlkPawnBlock2();
::CreateTblHorseMove();
::CreateTblKingMove();
::CreateTblKingAway();
::CreateTblMaxKingAway();
}

void DeleteAllTable()
{
delete TblBitIndex;
delete TblPieceBitmap;
delete TblCharToPiece;
delete TblPieceToChar;
delete TblQueenPath;
delete TblRookPath;
delete TblBishopPath;
delete TblDirection;
for (int i = 0; i < 2; i++)
{
delete TblRookCrossGrid[i];
delete TblBishopCrossGrid[i];
delete TblRookCrossPath[i];
delete TblBishopCrossPath[i];
}
delete TblQueenCrossGridBtmp;
delete TblHorseChkGrid1;
delete TblHorseChkGrid2;
delete TblHorseChkIdx;
delete TblKingChkIdx;
delete TblEludeChkIdx;
delete TblRookBlock1;
delete TblRookBlock2;
delete TblHorseBlock1;
delete TblHorseBlock2;
delete TblBishopBlock1;
delete TblBishopBlock2;
delete TblBlkPawnBlock;
delete TblBlkPawnBlock2;
delete TblHorseMove;
delete TblKingMove;
delete TblKingAway;
delete TblMaxKingAway;
}
zhouyundong_2012
 
Posts: 148
Joined: 10 February 2012

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

Postby zhouyundong_2012 » Fri Sep 02, 2016 11:14 am

#include "StdAfx.h"
#include "Traversal.h"
#include "Generate\Generate.h"
#include "MoveList\MoveList.h"
#include "Astode\Astode.h"

#define GetAstode(n) (n < MaxBufferSize ? AstodeBuffer[n] : AstodeStore[n - MaxBufferSize])

void ForwardsRed()
{
int nTrial = trial[nStep];
TMove *pMove = MoveList[nStep][nTrial];

int src = pMove->src;
int dest = pMove->dest;

if (pMove->pDeath)
g_pZDeposit->Impawn((char *)pMove->pDeath);

if (board[src] == R_KING)
rkpos = dest;

board[dest] = pMove->bian ? pMove->bian : board[src];
board[src] = 0;
g_hPBoard[dest] = g_hPBoard[src];
g_hPBoard[src] = NULL;
g_hPBoard[dest]->pos = dest;
if (pMove->bian)
g_hPBoard[dest]->kind = pMove->bian;

Z &= ~((qword)1 << src);
Z |= (qword)1 << dest;

trial[nStep++]++;
}

void ForwardsBlk()
{
int nTrial = trial[nStep];
TMove *pMove = MoveList[nStep][nTrial];

int src = pMove->src;
int dest = pMove->dest;

if (pMove->pDeath)
g_pZDeposit->Impawn((char *)pMove->pDeath);

if (board[src] == B_KING)
kpos = dest;

board[dest] = pMove->bian ? pMove->bian : board[src];
board[src] = 0;
g_hPBoard[dest] = g_hPBoard[src];
g_hPBoard[src] = NULL;
g_hPBoard[dest]->pos = dest;
if (pMove->bian)
g_hPBoard[dest]->kind = pMove->bian;

Z &= ~((qword)1 << src);
Z |= (qword)1 << dest;

trial[nStep++]++;
}

void BackwardsRed()
{
int nTrial = trial[--nStep] - 1;
TMove *pMove = MoveList[nStep][nTrial];

int src = pMove->src;
int dest = pMove->dest;

if (pMove->pDeath)
g_pZDeposit->Redeem((char *)pMove->pDeath);

if (board[dest] == R_KING)
rkpos = src;

board[src] = pMove->bian ? R_PAWN : board[dest];
board[dest] = pMove->pDeath ? pMove->pDeath->kind : 0;
g_hPBoard[src] = g_hPBoard[dest];
g_hPBoard[dest] = pMove->pDeath;
g_hPBoard[src]->pos = src;
if (pMove->bian)
g_hPBoard[src]->kind = R_PAWN;

if (board[dest] == 0)
Z &= ~((qword)1 << dest);

Z |= (qword)1 << src;
}

void BackwardsBlk()
{
int nTrial = trial[--nStep] - 1;
TMove *pMove = MoveList[nStep][nTrial];

int src = pMove->src;
int dest = pMove->dest;

if (pMove->pDeath)
g_pZDeposit->Redeem((char *)pMove->pDeath);

if (board[dest] == B_KING)
kpos = src;

board[src] = pMove->bian ? B_PAWN : board[dest];
board[dest] = pMove->pDeath ? pMove->pDeath->kind : 0;
g_hPBoard[src] = g_hPBoard[dest];
g_hPBoard[dest] = pMove->pDeath;
g_hPBoard[src]->pos = src;
if (pMove->bian)
g_hPBoard[src]->kind = B_PAWN;

if (board[dest] == 0)
Z &= ~((qword)1 << dest);

Z |= (qword)1 << src;
}

static int RedMove(bool bGenerate)
{
if (bGenerate)
{
::GenerateRed(!g_bAstable[nStep]);
//非稳定节点排除红必负着法
if (g_bAstable[nStep])
{
TAstode *pAstode = GetAstode(g_nBSIndex[nStep]);
if (Trial[nStep] > 32)
nStep = nStep;
pAstode->tag2 &= (1 << Trial[nStep]) - 1;
if (pAstode->tag2 == 0)
pAstode->tag1 = NOFURTHER;
}
}
_a: while (trial[nStep] < Trial[nStep] && !MoveList[nStep][trial[nStep]]->bValid)
trial[nStep]++;
if (trial[nStep] == Trial[nStep])
{
if (nStep == g_nBoundLower)
return REDLOSE;
::BackwardsBlk();
::BackwardsRed();
goto _a;
}
//专为小倒推使用
if (nStep == 0)
{
TMove *move = MoveList[nStep][trial[nStep]];
if (move->src == g_tCrackParam.src && move->dest == g_tCrackParam.dest)
{
trial[nStep]++;
goto _a;
}
}
if (g_bAstable[nStep])
{
if ((GetAstode(g_nBSIndex[nStep])->tag2 & (1 << trial[nStep])) == 0)
{
trial[nStep]++;
goto _a;
}
}
::ForwardsRed();
if (InCheckRed())
{
::BackwardsRed();
goto _a;
}

return NOLOSE;
}

static int BlackMove(bool bGenerate, int away)
{
if (bGenerate)
::GenerateBlk(MoveList[nStep - 1][trial[nStep - 1] - 1]->check, away);

_a: if (trial[nStep] == Trial[nStep])
{
if (nStep == g_nBoundLower + 1)
{
::BackwardsRed();
return BLKLOSE;
}
::BackwardsRed();
//Astode相关处理
if (g_bAstable[nStep])
{
TAstode *pAstode = GetAstode(g_nBSIndex[nStep]);
pAstode->nWinD = pAstode->nLoseD;
pAstode->nLoseD = pAstode->nVagueD;
}
::BackwardsBlk();
goto _a;
}
::ForwardsBlk();
if (InCheckBlk())
{
::BackwardsBlk();
goto _a;
}
return NOLOSE;
}

static int CallBound(int nBoundUpper, int away)
{
g_nBoundLower = nStep;
nDepth = nStep + 2;

while (nDepth <= nBoundUpper)
{
int nResult = Traversal(away);
if (nResult == INTERRUPT)
return INTERRUPT;
if (nResult == FULLASTODE)
return FULLASTODE;
if (nResult == REDLOSE)
nDepth += 2;
else
{
//红赢
if (g_bAstable[nStep])
{
TAstode *pAstode = GetAstode(g_nBSIndex[nStep]);
pAstode->nWinD = pAstode->nLoseD;
pAstode->nLoseD = pAstode->nVagueD;
}
return BLKLOSE;
}
}
return NOLOSE;
}

int Traversal(int away)
{
static TAstode tAstode = { 0 };
while (!g_bInterrupt)
{
bool bGenerate = nStep < nDepth;
if (nStep >= nDepth)
{
::BackwardsBlk();
::BackwardsRed();
}
//到达思考最大深度导致的回退,此时红方已经生成过着法
_rm: if (::RedMove(bGenerate) == REDLOSE)
return REDLOSE;
bGenerate = true;
_bm: if (::BlackMove(bGenerate, away) == BLKLOSE)
return BLKLOSE;

g_bAstable[nStep] = false;
int check = MoveList[nStep - 2][trial[nStep - 2] - 1]->check;
int dest = MoveList[nStep - 1][trial[nStep - 1] - 1]->dest;
if (nStep < g_nFurtherEnd)
{
g_bAstable[nStep] = true;
ShrinkAstode(tAstode.data);
int nResult = CallAstode(tAstode, nStep, nDepth - nStep);
if (nResult == REDLOSE)
{
::BackwardsBlk();
::BackwardsRed();
bGenerate = false;
goto _rm;
}
else if (nResult == NOFURTHER)
{
if (nStep >= 4 && g_bAstable[nStep - 2])
GetAstode(g_nBSIndex[nStep - 2])->tag2 &= ~(1 << (trial[nStep - 2] - 1));
::BackwardsBlk();
::BackwardsRed();
bGenerate = false;
goto _rm;
}
else if (nResult == BLKLOSE)
{
::BackwardsBlk();
bGenerate = false;
goto _bm;
}
else if (nResult == FULLASTODE)
{
g_bAstable[nStep] = false;
if (g_bFullAstode == false)
{
g_bFullAstode = true;
return FULLASTODE;
}
}
}
if (g_bAddAstode && nStep < g_nFurtherEnd && nStep < nDepth)
{
//记录上下限
int nBoundUpper = nDepth;
int nLastLower = g_nBoundLower;

int nResult = ::CallBound(nBoundUpper, away);
if (nResult == INTERRUPT)
return INTERRUPT;

nDepth = nBoundUpper;
g_nBoundLower = nLastLower;

if (nResult == FULLASTODE)
return FULLASTODE;

if (nResult == BLKLOSE)
{
::BackwardsBlk();
bGenerate = false;
goto _bm;
}
}
}
return INTERRUPT;
}
zhouyundong_2012
 
Posts: 148
Joined: 10 February 2012

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

Postby zhouyundong_2012 » Fri Sep 02, 2016 11:14 am

#include "StdAfx.h"
#include "Generate\Generate.h"
#include "MoveList\MoveList.h"

static void BlockByRookBlk(int pos, int check)
{
byte block1 = TblRookBlock1[(((check << 6) + kpos) << 6) + pos];
if (block1 != 0x40)
{
if ((Z & TblRookPath[(block1 << 6) + pos]) == 0)
::AddMoveBlk(pos, block1);
}
byte block2 = TblRookBlock2[(((check << 6) + kpos) << 6) + pos];
if (block2 != 0x40)
{
if ((Z & TblRookPath[(block2 << 6) + pos]) == 0)
::AddMoveBlk(pos, block2);
}
}

static void BlockByHorseBlk(int pos, int check)
{
byte block1 = TblHorseBlock1[(((check << 6) + kpos) << 6) + pos];
if (block1 != 0x40)
::AddMoveBlk(pos, block1);

byte block2 = TblHorseBlock2[(((check << 6) + kpos) << 6) + pos];
if (block2 != 0x40)
::AddMoveBlk(pos, block2);
}

static void BlockByBishopBlk(int pos, int check)
{
byte block1 = TblBishopBlock1[(((check << 6) + kpos) << 6) + pos];
if (block1 != 0x40)
{
if ((Z & TblBishopPath[(block1 << 6) + pos]) == 0)
::AddMoveBlk(pos, block1);
}
byte block2 = TblBishopBlock2[(((check << 6) + kpos) << 6) + pos];
if (block2 != 0x40)
{
if ((Z & TblBishopPath[(block2 << 6) + pos]) == 0)
::AddMoveBlk(pos, block2);
}
}

static void BlockByPawnBlk(int pos, int check)
{
byte block = TblBlkPawnBlock[(((check << 6) + kpos) << 6) + pos];
if (block != 0x40)
{
if (check >= 8 || kpos >= 8)
::AddMoveBlk(pos, block);
else
{
//直走升变
::BlkBian(pos, block);
}
}
byte block2 = TblBlkPawnBlock2[(((check << 6) + kpos) << 6) + pos];
if (block != 0x40)
{
if (board[pos - 8] == 0)
::AddMoveBlk(pos, block);
}
}

void GenBlockLine(int check)
{
TPiece *Piece = PieceBlkB;
while (Piece)
{
int pos = Piece->pos;
switch (Piece->kind)
{
case B_ROOK:
::BlockByRookBlk(pos, check);
break;
case B_HORSE:
::BlockByHorseBlk(pos, check);
break;
case B_BISHOP:
::BlockByBishopBlk(pos, check);
break;
case B_QUEEN:
::BlockByRookBlk(pos, check);
::BlockByBishopBlk(pos, check);
break;
case B_PAWN:
::BlockByPawnBlk(pos, check);
break;
}
Piece = Piece->next;
}
}
zhouyundong_2012
 
Posts: 148
Joined: 10 February 2012

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

Postby zhouyundong_2012 » Fri Sep 02, 2016 11:15 am

#include "StdAfx.h"
#include <memory>

CZDeposit::CZDeposit()
{
m_pHead = NULL;
}

CZDeposit::~CZDeposit()
{
SAFE_DELETE(m_pHead);
}

bool CZDeposit::Alloc(int nSize, int nCount, int nNext, int nPrev)
{
m_nSize = (nSize + 3) & 0xFFFFFFFC;
m_nCount = nCount;
m_nNext = nNext;
m_nPrev = nPrev;
m_nFlag = ((_int64)1 << m_nCount) - 1;
//申请空间
m_pHead = new char[m_nSize * m_nCount + sizeof(int)];
return m_pHead != NULL;
}

void CZDeposit::MemFill(void *pBuffer)
{
char *pTemp = m_pHead;
for (int i = 0; i < m_nCount; i++)
{
memcpy(pTemp, pBuffer, m_nSize);
pTemp += m_nSize;
}
}

void* CZDeposit::GetNode()
{
static int T[37] = { 0, 0, 1, 26, 2, 23, 27, 0, 3, 16, 24, 30, 28, 11, 0, 13, 4, 7, 17,
0, 25, 22, 31, 15, 29, 10, 12, 6, 0, 21, 14, 9, 5, 20, 8, 19, 18 };
int nIndex = T[(m_nFlag & -m_nFlag) % 37];
m_nFlag &= m_nFlag - 1;
return m_pHead + nIndex * m_nSize;
}

void CZDeposit::RtnNode(char *pNode)
{
int nIndex = (pNode - m_pHead) / m_nSize;
m_nFlag |= (_int64)1 << nIndex;
}

void CZDeposit::Impawn(char *pNode)
{
//队头前向指针指向对头指针的地址
int nNextAddr = *(int *)(pNode + m_nNext);
int nPrevAddr = *(int *)(pNode + m_nPrev);

if (*(int *)nPrevAddr == (int)pNode)
*(int *)nPrevAddr = nNextAddr;
else
*(int *)(nPrevAddr + m_nNext) = nNextAddr;

if (nNextAddr != 0)
*(int *)(nNextAddr + m_nPrev) = nPrevAddr;
}

void CZDeposit::Redeem(char *pNode)
{
//队头前向指针指向对头指针的地址
int nNextAddr = *(int *)(pNode + m_nNext);
int nPrevAddr = *(int *)(pNode + m_nPrev);

if (*(int *)nPrevAddr == nNextAddr)
*(int *)nPrevAddr = (int)pNode;
else
*(int *)(nPrevAddr + m_nNext) = (int)pNode;

if (nNextAddr != 0)
*(int *)(nNextAddr + m_nPrev) = (int)pNode;
}

void CZDeposit::Reclaim()
{
m_nFlag = ((_int64)1 << m_nCount) - 1;
}
zhouyundong_2012
 
Posts: 148
Joined: 10 February 2012

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

Postby zhouyundong_2012 » Fri Sep 02, 2016 11:17 am

If you need this and another lib, please visit my git hub.
Send email to me, I will give you git hub address.
zhouyundong_2012
 
Posts: 148
Joined: 10 February 2012

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

Postby zhouyundong_2012 » Fri Sep 02, 2016 11:21 am

these and other, not this and another.
What I do not is Web and Web Test, Wawt: C++, WebPage, AutoAction and AutoTest, with record and replay. ZSafe db, ZML, Net, all are prefixed with Z(Zhou Yundong).

With it, debug web program will never difficult .
zhouyundong_2012
 
Posts: 148
Joined: 10 February 2012

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

Postby JasonLion-Admin » Fri Sep 02, 2016 1:21 pm

What is all of this code?

On casual inspection, it doesn't appear to have anything to do with Sudoku.
User avatar
JasonLion-Admin
Site Admin
Site Admin
 
Posts: 89
Joined: 17 April 2010
Location: Silver Spring, MD, USA

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

Postby Mathimagics » Mon Sep 12, 2016 5:27 pm

Hmmm ... it looks like a C++ app that plays WarCraft, or Chess, or Mah Jong, or Go, or um, er ... 8-)
User avatar
Mathimagics
2017 Supporter
 
Posts: 1926
Joined: 27 May 2015
Location: Canberra

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

Postby zhouyundong_2012 » Wed Nov 23, 2016 9:24 am

I don't think so.
Research of this code is just starting.
Don't give up.
Update is not the most effecient, Guess is not the most effecint.


Now,Update seems to be the most effecient, but Guess maybe is not most effecient.
zhouyundong_2012
 
Posts: 148
Joined: 10 February 2012

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

Postby zhouyundong_2012 » Sat Jan 07, 2017 2:20 pm

class CImage;
class CObject {
public:
CObject();
CObject(CPoint xDrawPos, CSize xSize, int nDepth);
virtual ~CObject();

public:
virtual void Rebuild();
virtual void SetObjId(int nObjId);
virtual int GetObjId() const;
virtual void SetDrawPos(CPoint xDrawPos);
virtual void SetDrawPos(int x, int y);
virtual CPoint GetDrawPos() const;
virtual void Offset(CPoint point);
virtual void Offset(int x, int y);
virtual CPoint GetOffset() const;
virtual void UpdateOffset(CPoint point);
virtual void SetSize(CSize xSize);
virtual void SetSize(int cx, int cy);
virtual CSize GetSize() const;
virtual void GetRect(CRect *rect) const;
virtual BOOL PtIn(CPoint point);
virtual void SetDepth(int nDepth);
virtual int GetDepth() const;
virtual void SetCease(bool bCease = true);
virtual void Show(bool bShow = true);
virtual bool IsShow() const;
virtual bool IsExist() const;
virtual bool IsFocusable() const;
void SetHome(CObject *pHome);
CObject *GetHome() const;
CObject *GetParent() const;

public:
virtual void AdjustAnchor(CPoint point, const CRect& rect);
virtual void AdjustCenter(const CRect& rect, byte byFlag);
virtual void SetImage(CImage *pImage);
virtual CImage *GetImage() const;
virtual void SetSrcPos(CPoint xSrcPos);
virtual void SetSrcPos(int x, int y);
virtual CPoint GetSrcPos() const;
virtual void Draw(CImage *pImage);
virtual void Draw(CImage *pImage, const CRect& rect);

public:
virtual void OnGainFocus();
virtual void OnLoseFocus();
virtual void OnActive();
virtual void OnDeactive();
virtual void OnCreation();
virtual void OnDeletion();

public:
virtual void AddObject(CObject *pObject);
virtual void DelObject(CObject *pObject);
virtual bool Including(CObject *pObject);
virtual CObject *FindObject(const CPoint& point);
virtual CObject *FindWheel(const CPoint& point);
virtual CObject *FindFocus(const CPoint& point);
virtual CObject *FindExcept(const CPoint& point, CObject *pExcept);

public:
virtual void SetAutoTile(bool bAutoTile = true);
virtual bool IsAutoTile() const;
virtual void SetAutoSize(bool bAutoSize = true);
virtual bool IsAutoSize() const;
virtual void AutoTile(CPoint &xPen, CSize &xBand, CSize &xTile);

public:
void EnableAction(int nMouseAction, bool bEnable = true);
bool IsEnableAction(int nMouseAction) const;
void SetMouseProc(int nType, FN_MouseProc MouseProc);
FN_MouseProc GetMouseProc(int nType) const;
virtual void OnMouseMove(UINT nFlags, CPoint point);
virtual void OnMouseWheel(UINT nFlags, short zDelta, CPoint point);
virtual bool OnMouseEnter(UINT nFlags, CPoint point);
virtual bool OnMouseLeave(UINT nFlags, CPoint point);
virtual void OnLButtonDown(UINT nFlags, CPoint point);
virtual void OnLButtonUp(UINT nFlags, CPoint point);
virtual void OnRButtonDown(UINT nFlags, CPoint point);
virtual void OnRButtonUp(UINT nFlags, CPoint point);
virtual void OnMButtonDown(UINT nFlags, CPoint point);
virtual void OnMButtonUp(UINT nFlags, CPoint point);
virtual void OnLClick(UINT nFlags, CPoint point);
virtual void OnRClick(UINT nFlags, CPoint point);
virtual void OnMClick(UINT nFlags, CPoint point);
virtual void OnLDblClk(UINT nFlags, CPoint point);
virtual void OnRDblClk(UINT nFlags, CPoint point);
virtual void OnMDblClk(UINT nFlags, CPoint point);
virtual void OnMouseExtend(UINT nMEId, CPoint point);
virtual bool OnKeyDown(UINT nFlags, dword dwKey);
virtual bool OnKeyUp(UINT nFlags, dword dwKey);

public:
virtual void SetDragMode(byte byDragMode);
virtual byte GetDragMode() const;
virtual bool CheckDragMode(UINT nFlags);
virtual int GetDragThrs() const;
virtual void SetDrawMode(byte byDrawMode);
virtual byte GetDrawMode() const;
virtual bool CheckDrawMode(UINT nFlags);
virtual int GetDrawThrs();
virtual void OnDrawRect(UINT nFlags, const CRect& rect);
virtual void OnDrawOver(UINT nFlags, const CRect& rect);
virtual void OnMousePick(UINT nFlags, CPoint point);
virtual void OnMouseDrag(UINT nFlags, CPoint point);
virtual void OnMouseDrop(UINT nFlags, CPoint point);

public:
virtual void OnTrackLeave(UINT nFlags, CPoint point);
virtual void OnTrackHover(UINT nFlags, CPoint point);
void TrackMouseEvent(int nEventTrack);

public:
virtual void SetInteract(bool bInteract);
virtual bool IsInteract() const;
virtual void OnDragInteract(CObject *pObject);
virtual void OnDropInteract(CObject *pObject);

protected:
int m_nObjId;
CPoint m_xOffset;
CPoint m_xDrawPos;
CSize m_xSize;
int m_nDepth;
bool m_bCease : 1;
bool m_bShow : 1;
bool m_bExist : 1;
bool m_bInteract : 1;
bool m_bAutoTile : 1;
bool m_bAutoSize : 1;
byte m_byDragMode;
byte m_byDrawMode;
int m_nMouseAction;
int m_nEventTrack;
FN_MouseProc OnMouseProc[MP_MAX];

protected:
static CPoint DragOffset;

public:
CObject *m_pNext;
CObject *m_pPrev;
CObject *m_pHome;
CObject *m_pParent;
};
zhouyundong_2012
 
Posts: 148
Joined: 10 February 2012

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

Postby zhouyundong_2012 » Sat Jan 07, 2017 2:21 pm

class CZ2coo {
public:
SINGLETON(CZ2coo);
~CZ2coo();

protected:
CZ2coo();

public:
bool Initial();
void Release();
void SetWindow(CWindow *_window);
CWindow *GetWindow() const;
bool IsActived(CObject *pObject) const;
void SetActived(CObject *pObject);
CObject *GetActived() const;
bool IsFocused(CObject *pObject) const;
void SetFocused(CObject *pObject);
CObject *GetFocused() const;
CPoint GetLDown() const;
CPoint GetRDown() const;
void Draw(CImage *pImage);
void Draw(CImage *pImage, const CRect& rect);
void Redraw(CObject *pObject);
void Redraw(const CRect& rect);
void Redraw(CObject *pObject, const CRect& add); //附加区域
void Activate(CObject *pObject);
void TrackMouseEvent(int nEventTrack);
void SendMessage(UINT uMsg, WPARAM wParam = 0, LPARAM lParam = 0);
bool PostMessage(UINT uMsg, WPARAM wParam = 0, LPARAM lParam = 0);

public:
void AddObject(CObject *pObject);
void DelObject(CObject *pObject);
CObject *FindObject(const CPoint& point);
CObject *FindWheel(const CPoint& point);
CObject *FindFocus(const CPoint& point);
CObject *FindExcept(const CPoint& point, CObject *pExcept);

public:
virtual void OnLButtonDown(UINT nFlags, CPoint point);
virtual void OnLButtonUp(UINT nFlags, CPoint point);
virtual void OnMouseMove(UINT nFlags, const CPoint& point);
virtual void OnMouseWheel(UINT nFlags, short zDelta, CPoint point);
virtual void OnRButtonDown(UINT nFlags, CPoint point);
virtual void OnRButtonUp(UINT nFlags, CPoint point);
virtual void OnMButtonDown(UINT nFlags, CPoint point);
virtual void OnMButtonUp(UINT nFlags, CPoint point);
virtual void OnMouseExtend(UINT nMEId, CPoint point);
virtual void OnKeyDown(UINT nFlags, dword dwKey);
virtual void OnKeyUp(UINT nFlags, dword dwKey);

private:
void _OnLButtonUp(UINT nFlags, CPoint point);
void _OnMouseMove(UINT nFlags, const CPoint& point);
bool _PtInPressed(UINT nFlags, CPoint point);
void _ResetFocused(UINT nFlags, const CPoint& point);

protected:
virtual bool CheckDrawThrs(CPoint point);
virtual void OnDrawRect(UINT nFlags, const CPoint& point);
virtual void OnDrawOver(UINT nFlags, const CPoint& point);

protected:
virtual bool CheckDragThrs(CPoint point);
virtual void OnMousePick(UINT nFlags, const CPoint& point);
virtual void OnMouseDrag(UINT nFlags, const CPoint& point);
virtual void OnMouseDrop(UINT nFlags, const CPoint& point);

protected:
void TerminateAction(UINT nFlags, const CPoint& point);

protected:
CWindow *window;
CRect ClientRect;

protected:
CContainer *m_pContainer;

protected:
int m_nLStatus;
CObject *m_pActived;
CObject *m_pFocused;
CPoint m_xLDown; //左键按下位置
CPoint m_xRDown; //右键按下位置
};
zhouyundong_2012
 
Posts: 148
Joined: 10 February 2012

PreviousNext

Return to Software