?? xsudoku.cpp
字號:
/*/////////////////////////////////////////
// 版權所有(C) 2000-2008 鄧輝 //
// Email： denghui0815@hotmail.com //
// 說明： Intel線程優化大賽參賽作品//
/////////////////////////////////////////*/
#include "XSudoku.h"
// 包含1的個數
// 小于XFILLEDMASK為正常值
// 大于等于XFILLEDMASK值均為255 [XFindMinFeasibilityPos中減少判斷]
__declspec(align(16)) uint8 g_xPopCnt[0xFFFF] = {0};
// 單元格的值到輸出字符的映射
__declspec(align(16)) char g_xOutTab[1 << XGRID_BSIZE] = {0};
// 輸出緩沖
__declspec(align(16)) char g_xOutCells[XGRID_BSIZE + XGRID_BW + 1][(XGRID_BSIZE + XGRID_BH) * 2 + 2] = {0};
// 保存與當前單元格相關的單元格
__declspec(align(16)) uint8 g_xMutuality[XGRID_AREA][XGRID_MUTUALITYSSE] = {0};
__declspec(align(16)) uint8 g_nMutuality[XGRID_AREA] = {0};
// 初始化靜態加速Tab
void XInitTab()
{
int i,j;
// 初始化PopCnt數組
g_xPopCnt[0] = 0;
g_xPopCnt[1] = 1;
g_xPopCnt[2] = 1;
g_xPopCnt[3] = 2;
for(i = 0x04; i < 0x10; ++i) g_xPopCnt[i] = g_xPopCnt[i >> 2] + g_xPopCnt[i & 0x03];
for(i = 0x10; i < 0x100; ++i) g_xPopCnt[i] = g_xPopCnt[i >> 4] + g_xPopCnt[i & 0x0F];
#pragma omp parallel for
for(i = 0x100; i < XFILLEDMASK; ++i) g_xPopCnt[i] = g_xPopCnt[i >> 8] + g_xPopCnt[i & 0xFF];
#pragma omp parallel for
for(i = XFILLEDMASK; i < 0x10000; ++i) g_xPopCnt[i] = 0xFF;
// 計算每個單元格的關聯單元格數組
for(i = 0; i < XGRID_AREA; ++i)
{
g_nMutuality[i] = 0;
for(j = 0; j < XGRID_AREA; ++j)
{
if(i == j) continue;
// 如果兩個單元格滿足以下條件 則這兩個單元格存在關聯關系
// 1. 單元格的橫坐標相同
// 2. 單元格的縱坐標相同
// 3. 單元格所在塊的橫坐標相同且單元格所在塊的縱坐標相同[兩個單元格在同一個塊中]
if( ( i % XGRID_BSIZE == j % XGRID_BSIZE ) || ( i / XGRID_BSIZE == j / XGRID_BSIZE ) ||
( ( i / XGRID_BSIZE / XGRID_BH == j / XGRID_BSIZE / XGRID_BH ) &&
( ( i % XGRID_BSIZE ) / XGRID_BW ) == ( ( j % XGRID_BSIZE ) / XGRID_BW ) ) )
{
g_xMutuality[i][g_nMutuality[i]++] = j;
}
}
for(j = XGRID_MUTUALITY; j < XGRID_MUTUALITYSSE; ++j) g_xMutuality[i][j] = XGRID_AREA;
}
// 初始化值到字符的映射
for(i = 0; i < XGRID_BSIZE; ++i) g_xOutTab[ 1 << i] = i + '1';
// 初始化輸出字符表格
for(i = 0; i < XGRID_BSIZE + XGRID_BW + 1; ++i)
{
if(i % (XGRID_BH + 1) == 0)
{
for(j = 0; j < (XGRID_BSIZE + XGRID_BH) * 2 + 1; ++j)
{
g_xOutCells[i][j] = (j % (XGRID_BW * 2 + 2) == 0) ? '+' : '-';
}
}
else
{
for(j = 0; j < (XGRID_BSIZE + XGRID_BH) * 2 + 1; ++j)
{
g_xOutCells[i][j] = (j % (XGRID_BW * 2 + 2) == 0) ? '|' : ' ';
}
}
g_xOutCells[i][(XGRID_BSIZE + XGRID_BH) * 2 + 1] = (i == XGRID_BSIZE + XGRID_BW) ? '\0' : '\n';
}
}
// 輸出網格
__inline void XAddSolution(int* pRunMode, int* pTotal, XCells pCells)
{
#ifndef XOUT_SOLUTION
if(++(*pTotal) > 1)
{
*pRunMode &= ~XRUN_FIND_FLAG;
}
#else
static mutex xMutex;
if(*pRunMode & XRUN_FIND_ONE)
{
if(++(*pTotal) > 1)
{
*pRunMode &= ~XRUN_FIND_FLAG;
}
}
else
{
tbb::mutex::scoped_lock lock(xMutex);
++(*pTotal);
}
if(*pRunMode & (XRUN_OUT_STD | XRUN_OUT_FILE))
{
for(int nPos = 0; nPos < XGRID_AREA; ++nPos)
{
int x = nPos % XGRID_BSIZE;
int y = nPos / XGRID_BSIZE;
g_xOutCells[y + y / XGRID_BH + 1][(x + x / XGRID_BW + 1) * 2] = g_xOutTab[pCells[nPos] - XFILLEDMASK];
}
if(*pRunMode & XRUN_OUT_STD)
{
printf("第%d種\n%s\n\n", *pTotal, (const char*)g_xOutCells);
}
else
{
FILE* fp = fopen("xout.txt", "a");
fprintf(fp, "第%d種\n%s\n\n", *pTotal, (const char*)g_xOutCells);
fclose(fp);
}
}
#endif
}
// 為nPos位置的單元格置上nMask表示的值
// 當某個關聯單元格清除后僅剩下一種可能性則繼續遞歸調用XFillCell填充掉該單元格
// 將填充的單元格位置保存到pGrid->pFilledPos中
__inline int XFillCell(XGrid* pGrid, XCells pCells, int nPos, int nMask)
{
int nFilled = pGrid->nFilled;
for(;;)
{
#ifdef XGRID_MUTUALITYSSE_CLEAR
uint8* const pMutuality = pGrid->pMutuality[nPos];
const uint8 nMutuality = pGrid->nMutuality[nPos];
#else
uint8* const pMutuality = g_xMutuality[nPos];
const uint8 nMutuality = g_nMutuality[nPos];
#endif
pCells[nPos] = nMask + XFILLEDMASK;
pGrid->pFilledPos[nFilled++] = nPos;
nPos = -1;
#pragma unroll(16)
for(int i = 0; i < nMutuality; ++i)
{
const uint8 nTmp = pMutuality[i];
// 去掉該單元格填充nMask的可能性
pCells[nTmp] &= ~nMask;
// 如果單元格沒有可選擇的填值方案 返回失敗
if(pCells[nTmp] == 0) return XFILL_INVALID;
// 判斷該單元格是否只有一種填值可能,如果是將調用XFillCell給該單元格填值
if(g_xPopCnt[pCells[nTmp]] == 1) nPos = nTmp;
}
if(nPos < 0) break;
nMask = pCells[nPos];
}
pGrid->nFilled = nFilled;
return pGrid->nFilled;
}
__inline int XFillCellLoad(XGrid* pGrid, XCells pCells, int nPos, int nMask)
{
int nNewPos = -1;
#ifdef XGRID_MUTUALITYSSE_CLEAR
uint8* const pMutuality = pGrid->pMutuality[nPos];
const uint8 nMutuality = pGrid->nMutuality[nPos];
#else
uint8* const pMutuality = g_xMutuality[nPos];
const uint8 nMutuality = g_nMutuality[nPos];
#endif
// 如果該單元格已經填充了nMask 直接返回
if(pCells[nPos] == nMask + XFILLEDMASK) return pGrid->nFilled;
// 判斷當前單元格能填nMask表示的值
if((pCells[nPos] & nMask) == 0) return XFILL_INVALID;
// 為第nPos個單元格填上nMask表示的值
pCells[nPos] = nMask + XFILLEDMASK;
for(int i = 0; i < nMutuality; ++i)
{
const uint8 nTmp = pMutuality[i];
// 去掉該單元格填充nMask的可能性
pCells[nTmp] &= ~nMask;
// 如果單元格沒有可選擇的填值方案 返回失敗
if(pCells[nTmp] == 0) return XFILL_INVALID;
// 判斷該單元格是否只有一種填值可能,如果是將調用XFillCell給該單元格填值
if(g_xPopCnt[pCells[nTmp]] == 1) nNewPos = nTmp;
}
// 記錄當前填充的單元格
pGrid->pFilledPos[pGrid->nFilled++] = nPos;
if(nNewPos >= 0)
{
if(XFillCell(pGrid, pCells, nNewPos, pCells[nNewPos]) == XFILL_INVALID)
{
// 恢復已經填值的單元格
--pGrid->nFilled;
return XFILL_INVALID;
}
}
return pGrid->nFilled;
}
// 查找可填的數字最少的單元格
__inline int XFindMinFeasibilityPos(XCells pCells)
{
int nMinCnt = 0xFF;
int nMinPos = -1;
// 在所有未填值的單元格中查找可填值方案最少的單元格
for(int i = 0; i < XGRID_AREA && nMinCnt > 1; ++i)
{
if(g_xPopCnt[pCells[i]] < nMinCnt)
{
nMinPos = i;
nMinCnt = g_xPopCnt[pCells[i]];
}
}
return nMinPos;
}
// 刪除與單元格nPos相關聯的單元格 [XGRID_BSIZE>=9且需要查找所有情況時清除關聯可加速]
#ifdef XGRID_MUTUALITYSSE_CLEAR
__inline void XRemoveMutuality(XGrid* pGrid, uint8 nPos)
{
uint8* const pCur = pGrid->pMutuality[nPos];
for(int i = pGrid->nMutuality[nPos] - 1; i >= 0; --i)
{
uint8* const pTmp = pGrid->pMutuality[pCur[i]];
const int nTmp = --pGrid->nMutuality[pCur[i]];
for(int j = 0; j < nTmp; ++j)
{
if(pTmp[j] == nPos)
{
for(int k = j; k < nTmp; ++k) pTmp[k] = pTmp[k+1];
break;
}
}
}
}
#endif
// 加載測試數據
__inline int XLoadGrid(XGrid* pGrid, const char* pInput)
{
int nPos = 0;
int nMask = (1 << XGRID_BSIZE) - 1;
#ifdef XGRID_MUTUALITYSSE_CLEAR
XMEMCOPY(pGrid->pMutuality, g_xMutuality, sizeof(g_xMutuality));
XMEMCOPY(pGrid->nMutuality, g_nMutuality, sizeof(g_nMutuality));
#endif
for(nPos = 0; nPos < XGRID_AREA; ++nPos) pGrid->xCells[nPos] = nMask;
for(nPos = 0; nPos < XGRID_AREA; ++nPos)
{
if(pInput[nPos] >= '1' && pInput[nPos] <= '0' + XGRID_BSIZE)
{ // 填充nPos的值為 1 << ( pInput[nPos] - '1' )
if(XFillCellLoad(pGrid, pGrid->xCells, nPos, 1 << ( pInput[nPos] - '1' )) == XFILL_INVALID)
{
return XFILL_INVALID;
}
}
}
#ifdef XGRID_MUTUALITYSSE_CLEAR
// [XGRID_BSIZE>=9且需要查找所有情況時清除關聯可加速]
for(int i = 0; i < pGrid->nFilled; ++i)
{
XRemoveMutuality(pGrid, pGrid->pFilledPos[i]);
}
#endif
return XGRID_AREA - pGrid->nFilled;
}
__inline void XFillCellStack(XGrid* pGrid)
{
__declspec(align(16)) XCells xCellsStack[XGRID_AREA + 1];
__declspec(align(16)) int nMinPosStack[XGRID_AREA];
__declspec(align(16)) int nCurValStack[XGRID_AREA];
__declspec(align(16)) int nFilledStack[XGRID_AREA];
int nIndex = 0;
XMEMCOPY(xCellsStack[0], pGrid->xCells, sizeof(xCellsStack[0]));
// 查找當前填值可能性最少的單元格
nMinPosStack[nIndex] = XFindMinFeasibilityPos(xCellsStack[nIndex]);
nCurValStack[nIndex] = xCellsStack[nIndex][nMinPosStack[nIndex]];
nFilledStack[nIndex] = pGrid->nFilled;
while( (*pGrid->pRunMode & XRUN_FIND_FLAG) && nIndex >= 0 )
{
nFilledStack[nIndex + 1] = XFILL_INVALID;
// 嘗試填充當前單元格
while(nFilledStack[nIndex + 1] == XFILL_INVALID && nCurValStack[nIndex])
{
XMEMCOPY(xCellsStack[nIndex + 1], xCellsStack[nIndex], sizeof(xCellsStack[0]));
unsigned int nMask = nCurValStack[nIndex] & -nCurValStack[nIndex];
nCurValStack[nIndex] -= nMask;
nFilledStack[nIndex + 1] = XFillCell(pGrid, xCellsStack[nIndex + 1], nMinPosStack[nIndex], nMask);
}
if(nFilledStack[nIndex + 1] > XGRID_AREA)
{ // 沒有合法的填充值
pGrid->nFilled = nFilledStack[--nIndex];
}
else if(nFilledStack[nIndex + 1] != XGRID_AREA)
{ // 是合法的填充值, 還存在未填值的單元格
++nIndex;
// 查找當前填值可能性最少的單元格
nMinPosStack[nIndex] = XFindMinFeasibilityPos(xCellsStack[nIndex]);
nCurValStack[nIndex] = xCellsStack[nIndex][nMinPosStack[nIndex]];
}
else
{ // 所有單元格均已填值
XAddSolution(pGrid->pRunMode, pGrid->pTotal, xCellsStack[nIndex + 1]);
pGrid->nFilled = nFilledStack[nIndex];
}
}
}
class CXSudokuTask: public tbb::task
{
XGrid* m_pGrid;
public:
CXSudokuTask( XGrid* pGrid) : m_pGrid(pGrid){}
tbb::task* execute()
{
if( ( *m_pGrid->pRunMode & XRUN_FIND_FLAG ) == 0) return NULL;
if( m_pGrid->nFilled < XGRID_CHANGE_MUTUALITY_SIZE)
{
tbb::task_list list;
__declspec(align(16)) XGrid pChildGrid[XGRID_BSIZE];
int nChildGrid = 0, nNewFilled = 0, nOldFilled = m_pGrid->nFilled;
// 查找當前填值可能性最少的單元格
int nMinPos = XFindMinFeasibilityPos(m_pGrid->xCells);
// 如果當前單元格只有一種填值情況,則直接給該單元格填值
if(g_xPopCnt[m_pGrid->xCells[nMinPos]] == 1 && nOldFilled < XGRID_AREA)
{
nNewFilled = XFillCell(m_pGrid, m_pGrid->xCells, nMinPos, m_pGrid->xCells[nMinPos]);
nMinPos = XFindMinFeasibilityPos(m_pGrid->xCells);
}
if(nNewFilled < XGRID_AREA)
{ // 存在多種可能的填值情況
int nCurVal = m_pGrid->xCells[nMinPos];
while(nCurVal)
{
XGrid* pCurGrid = pChildGrid + nChildGrid;
XMEMCOPY(pCurGrid, m_pGrid, sizeof(pChildGrid[0]));
unsigned int nMask = nCurVal & -nCurVal;
nCurVal -= nMask;
// 給該單元格填可能的值
nNewFilled = XFillCell(pCurGrid, pCurGrid->xCells, nMinPos, nMask);
if(nNewFilled < XGRID_AREA)
{ // 是合法的填充值, 還存在未填值的單元格
#ifdef XGRID_MUTUALITYSSE_CLEAR
// [XGRID_BSIZE>=9且需要查找所有情況時清除關聯可加速]
for(int i = nOldFilled; i < nNewFilled; ++i)
{
XRemoveMutuality(pCurGrid, pCurGrid->pFilledPos[i]);
}
#endif
// 增加子Task
list.push_back( *new( allocate_child() ) CXSudokuTask(pCurGrid));
++nChildGrid;
}
else if(nNewFilled == XGRID_AREA)
{ // 所有單元格均已填值
XAddSolution(pCurGrid->pRunMode, pCurGrid->pTotal, pCurGrid->xCells);
}
}
set_ref_count( nChildGrid + 1 );
spawn_and_wait_for_all(list);
}
else if(nNewFilled == XGRID_AREA)
{ // 所有單元格均已填值
XAddSolution(m_pGrid->pRunMode, m_pGrid->pTotal, m_pGrid->xCells);
}
}
else
{
XFillCellStack(m_pGrid);
}
return NULL;
}
};
// 大于 9 * 9 的網格 查找所有的填值可能方案時 效率更高
void XParallelSudoku( XGrid* pGrid )
{
CXSudokuTask& xTask = *new(tbb::task::allocate_root()) CXSudokuTask(pGrid);
tbb::task::spawn_root_and_wait(xTask);
}
int XFindGrid(int nRunMode, const char* pInput)
{
int nTotal = 0;
XGrid xGrid = {0};
xGrid.pRunMode = &nRunMode;
xGrid.pTotal = &nTotal;
// 加載網格數據
switch(XLoadGrid(&xGrid, pInput))
{
case 0:
nTotal = 1;
break;
case XFILL_INVALID:
break;
default:
// 填充單元格
XFillCellStack(&xGrid);
}
return nTotal;
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -