SudokuSolver 2.2 程序实现

根据用C++实现的数独解题程序 SudokuSolver 2.1 及实例分析里分析，对 2.1 版做了一些改进和尝试。

CQuizDealer 类声明部分的修改

class CQuizDealer{public:...
    void run(ulong tilsteps = 0);void setOnlyGrpMode() {m_onlyGrp = true;}...
private:...CQuizDealer() : m_state(STA_UNLOADED), ..., m_onlyGrp(false) {};inline void incSteps() {++m_steps;}inline bool IsDone(u8 ret) {return (ret == RET_OK || ret == RET_WRONG);}...u8 filterOneGroup(u8* pGrp);bool completeShrinkByGrp(u8* pGrp, u8* pTimes);u8 incompleteShrinkByGrp(u8 valSum, u8* pCelSumExs, u8* pGrp);bool sameCandidates(u8 cel1, u8 cel2);...
    ulong m_steps;bool m_onlyGrp;...};

新增的 setOnlyGrpMode 接口用于控制只采用第一类收缩算法求解。

filterCandidates 接口实现修改

u8 CQuizDealer::filterCandidates(){incSteps();u8 ret = RET_PENDING;for (u8 row = 0; row < 9; ++row)if (ret = filterRowGroup(row))return ret;for (u8 col = 0; col < 9; ++col)if (ret = filterColGroup(col))return ret;for (u8 blk = 0; blk < 9; ++blk)if (ret = filterBlkGroup(blk))return ret;if (!m_onlyGrp) {for (u8 row = 0; row < 9; ++row) {ret = filterRowCandidatesEx(row);if (IsDone(ret))return ret;}for (u8 col = 0; col < 9; ++col) {ret = filterColCandidatesEx(col);if (IsDone(ret))return ret;}}if (ret == RET_SHRUNKEN) {printf(\"incomplete shrink met, filter again\\n\");return filterCandidates();}return ret;}

增加了 onlyGrp 控制，即上面所说的是否只采用第一类收缩算法求解。末尾增加的条件递归调用，源自上一篇的实例分析。

filterRowGroup 接口实现修改

u8 CQuizDealer::filterRowGroup(u8 row){u8 celIdxs[10] = {0}; // first item denotes sum of zerosu8 base = row * 9;for (u8 col = 0; col < 9; ++col) {if (m_seqCell[base + col].val == 0) {celIdxs[0] += 1;celIdxs[celIdxs[0]] = base + col;}}if (celIdxs[0] == 0)return RET_PENDING;u8 ret = filterOneGroup(celIdxs);if (ret == RET_OK)printf(\"%u) row %d complete shrunken by group\\n\", m_steps, (int)row + 1);else if (ret == RET_WRONG)printf(\"%u) row %d shrink by group went WRONG\\n\", m_steps, (int)row + 1);else if (ret == RET_SHRUNKEN)printf(\"%u) row %d incomplete shrunken by group\\n\", m_steps, (int)row + 1);return ret;}

filterColGroup 和 filterBlkGroup 接口修改类似。

filterOneGroup 接口新实现

u8 CQuizDealer::filterOneGroup(u8* pGrp){u8 times[20] = {0};if (completeShrinkByGrp(pGrp, times))return RET_OK;u8 size = pGrp[0];u8 celSumExs[100] = {0};for (u8 idx = 1; idx <= size; ++idx) {u8 valSum = m_seqCell[pGrp[idx]].candidates[0];u8 base = valSum * 10;celSumExs[base] += 1;u8 pos = base + celSumExs[base];celSumExs[pos] = pGrp[idx];}for (u8 idx = 2; idx <= 6; ++idx) {u8 ret = incompleteShrinkByGrp(idx, celSumExs, pGrp);if (ret != RET_PENDING)return ret;}return RET_PENDING;}

filterOneGroup 接口的原有实现只支持完全收缩，现在放到了新增 completeShrinkByGrp 接口里：

bool CQuizDealer::completeShrinkByGrp(u8* pGrp, u8* pTimes){u8 size = pGrp[0];for (u8 idx = 1; idx <= size; ++idx) {u8 sum = m_seqCell[pGrp[idx]].candidates[0];for (u8 inn = 1; inn <= sum; ++inn) {u8 val = m_seqCell[pGrp[idx]].candidates[inn];pTimes[val] += 1;pTimes[val + 9] = pGrp[idx];}}bool ret = false;for (u8 val = 1; val <= 9; ++val) {if (pTimes[val] == 1) {ret = true;u8 celIdx = pTimes[val + 9];m_seqCell[celIdx].candidates[0] = 1;m_seqCell[celIdx].candidates[1] = val;}}return ret;}

新增 incompleteShrinkByGrp 接口实现

u8 CQuizDealer::incompleteShrinkByGrp(u8 valSum, u8* pCelSumExs, u8* pGrp){u8 base = valSum * 10;if (pCelSumExs[base] < valSum)return RET_PENDING;u8 itemSum = 0;Item items[9];for (u8 pos = 1; pos <= pCelSumExs[base]; ++pos) {u8 idx = 0;for (; idx < itemSum; ++idx)if (sameCandidates(pCelSumExs[base + pos], items[idx].celIdxs[0])) {items[idx].celIdxs[items[idx].sameSum] = pCelSumExs[base + pos];items[idx].sameSum++;break;}if (idx == itemSum) {items[itemSum].sameSum = 1;items[itemSum].celIdxs[0] = pCelSumExs[base + pos];++itemSum;}}for (u8 idx = 0; idx < itemSum; ++idx) {if (items[idx].sameSum > valSum)return RET_WRONG;}bool shrunken = false;for (u8 idx = 0; idx < itemSum; ++idx) {if (items[idx].sameSum < valSum)continue;for (u8 pos = 1; pos <= pGrp[0]; ++pos) {if (inSet(pGrp[pos], (u8*)&(items[idx])))continue;u8 isVals[10] = {0};u8 cel1 = items[idx].celIdxs[0];u8 cel2 = pGrp[pos];intersection(m_seqCell[cel1].candidates, m_seqCell[cel2].candidates, isVals);if (isVals[0] == 0)continue;shrunken = true;for (u8 valIdx = 1; valIdx <= isVals[0]; ++valIdx)if (!removeVal(m_seqCell[cel2].candidates, isVals[valIdx]))return RET_WRONG;}}return (shrunken ? RET_SHRUNKEN : RET_PENDING);}

里面用到的 Item 结构以及 sameCandidates 接口为：

struct Item {u8 sameSum;u8 celIdxs[9];Item() {sameSum = 0;}};

bool CQuizDealer::sameCandidates(u8 cel1, u8 cel2)
{
u8 sum = m_seqCell[cel1].candidates[0];
if (sum != m_seqCell[cel2].candidates[0])
return false;
for (u8 idx = 1; idx <= sum; ++idx)
if (m_seqCell[cel1].candidates[idx] != m_seqCell[cel2].candidates[idx])
return false;
return true;
}

filterRowCandidatesEx 接口实现小修改

u8 CQuizDealer::filterRowCandidatesEx(u8 row){...
    for (u8 idx = 0; idx < 3; ++idx) {ret = filterRowByPolicy1(row, idx, vals, blkTakens);if (IsDone(ret))return ret;}for (u8 idx = 0; idx < 3; ++idx) {ret = filterRowByPolicy2(row, idx, vals, blkTakens);if (IsDone(ret))return ret;}return ret;}

filterColCandidatesEx 接口的修改类似。

shrinkRowCandidatesP1 接口实现小修改

u8 CQuizDealer::shrinkRowCandidatesP1(u8* pBlk, u8* pRow, u8 zeroSum, u8 row, u8 colBase){...u8 shrunken = 0;for (u8 col = colBase; col < colBase + 3; ++col) {...
        if (ret != RET_PENDING) {printf(\" worked by row-ply1.\\n\");if (ret == RET_OK)shrunken = 1; // completeelse if (ret == RET_SHRUNKEN && shrunken == 0)shrunken = 2; // incomplete}}if (shrunken == 1) {ret = RET_OK;printf(\"%u) row %d shrunken ply-1 by blk %d\\n\", m_steps, (u8)row + 1, (u8)colBase / 3 + 1);}else if (shrunken == 2)ret = RET_SHRUNKEN;return ret;}

shrinkRowCandidatesP2 接口以及shrinkColCandidatesP1 和shrinkColCandidatesP2 接口的修改类似。

其他小修改

// 1.0 2021/9/20// 2.0 2021/10/2// 2.1 2021/10/4#define STR_VER \"Sudoku Solver 2.2 2021/10/10 by readalps\\n\\n\"void showOrderList(){...printf(\"onlygrp: only using group shrink\\n\");printf(\"step: step forward\\n\");...}void dealOrder(std::string& strOrder){...
    else if (\"onlygrp\" == strOrder)CQuizDealer::instance()->setOnlyGrpMode();else if (\"step\" == strOrder)
    ...

实例分析

继续以SudokuSolver 1.0：用C++实现的数独解题程序【二】里试验过的“最难”数独题为例做分析。在第一次 run 命令的输出中有如下信息：

506) Forward guess [1,4] level 11 at 2 out of 2[2,1]: 1 4 5 9 shrunken to  5 9 worked by row-ply2.[2,8]: 4 5 9 shrunken to  5 9 worked by row-ply2.509) Guess [1,3] level 12 at 1 out of 2

第 2 行有两个空位发生了不完全收缩，走的不是第一类收缩算法（by grp），而是第二类收缩算法（by ply）。重新用 runtil 506 命令进到当时的上下文做深入分析：

...
506) Forward guess [1,4] level 11 at 2 out of 2820 703 601003 600 807070 090 203050 007 104000 045 706007 100 935001 009 568008 500 319090 000 472Steps:506Candidates:[1,3]: 4 5 9    [1,5]: 5    [1,8]: 4 5 9[2,1]: 1 4 5 9    [2,2]: 1 4    [2,5]: 1 2 5[2,6]: 1 2 4    [2,8]: 4 5 9    [3,1]: 1 4 5 6[3,3]: 4 5 6    [3,4]: 4 8    [3,6]: 1 4 8[3,8]: 4 5    [4,1]: 2 3 6 9    [4,3]: 2 6 9[4,4]: 2 3 8 9    [4,5]: 2 3 6 8    [4,8]: 2 8[5,1]: 1 2 3 9    [5,2]: 1 3 8    [5,3]: 2 9[5,4]: 2 3 8 9    [5,8]: 2 8    [6,1]: 2 4 6[6,2]: 4 6 8    [6,5]: 2 6 8    [6,6]: 2 6 8[7,1]: 2 3 4 7    [7,2]: 3 4    [7,4]: 2 3 4[7,5]: 2 3 7    [8,1]: 2 4 6 7    [8,2]: 4 6[8,5]: 2 6 7    [8,6]: 2 4 6    [9,1]: 3 5 6[9,3]: 5 6    [9,4]: 3 8    [9,5]: 1 3 6 8[9,6]: 1 6 8The foremost cell with 1 candidate(s) at [1,5]At guess level 11 [1,4] 2Run time: 326 milliseconds; steps: 506, solution sum: 0.Order please:

由The foremost cell with 1 candidate(s) at [1,5] 可知当时 [1,5] 位置可以直接填值。先走完这一步：

Order please:step820 753 601003 600 807070 090 203050 007 104000 045 706007 100 935001 009 568008 500 319090 000 472Steps:507Candidates:[1,3]: 4 9    [1,8]: 4 9    [2,1]: 1 4 5 9[2,2]: 1 4    [2,5]: 1 2    [2,6]: 1 2 4[2,8]: 4 5 9    [3,1]: 1 4 5 6    [3,3]: 4 5 6[3,4]: 4 8    [3,6]: 1 4 8    [3,8]: 4 5[4,1]: 2 3 6 9    [4,3]: 2 6 9    [4,4]: 2 3 8 9[4,5]: 2 3 6 8    [4,8]: 2 8    [5,1]: 1 2 3 9[5,2]: 1 3 8    [5,3]: 2 9    [5,4]: 2 3 8 9[5,8]: 2 8    [6,1]: 2 4 6    [6,2]: 4 6 8[6,5]: 2 6 8    [6,6]: 2 6 8    [7,1]: 2 3 4 7[7,2]: 3 4    [7,4]: 2 3 4    [7,5]: 2 3 7[8,1]: 2 4 6 7    [8,2]: 4 6    [8,5]: 2 6 7[8,6]: 2 4 6    [9,1]: 3 5 6    [9,3]: 5 6[9,4]: 3 8    [9,5]: 1 3 6 8    [9,6]: 1 6 8The foremost cell with 2 candidate(s) at [1,3]At guess level 11 [1,4] 2Order please:

走完 507 步时，第 2 行的空位候选值分布情况为：

[2,1]: 1 4 5 9[2,2]: 1 4    [2,5]: 1 2    [2,6]: 1 2 4[2,8]: 4 5 9

这里，5 和 9 只能填入两个空位，即 [2,1] 和 [2,8] 中，因此，这两个空位只能是一个填 5 另一个填 9。于是，这两个空位里的除 5 和 9 之外的其他候选值都可以排除掉。这和上一篇的实例分析部分发现的 grp 算法可改进之处还不一样，这是新发现的一处可以改进 grp 算法的地方。

用C++实现的数独解题程序 SudokuSolver 2.2 及实例分析