SudokuSolver 2.0 实现效果

H:\\Read\\num\\Release>sudoku.exeOrder please:Sudoku Solver 2.0 2021/10/2 by readalpsOrder List:load-quiz <file>: load quiz from fileshow: show quiz infostep: step forwardrun: run till the end or a new solution metbye: quitOrder please:

可以看到，SudokuSolver 2.0 版和之前的 1.0 版用法上完全一样。2.0 版主要实现了一些精确求解的方法，减少求解过程中的猜测，提升求解速度。仍以一道心形数独题的求解里的那道题为例，来具体看一下：

Order please:step000 000 000023 000 780100 406 009400 050 001900 000 006060 000 090005 000 800000 301 000000 090 000Steps:1Candidates:[1,1]: 5 6 7 8    [1,2]: 4 5 7 8 9    [1,3]: 4 6 7 8 9
...[2,1]: 5 6    [2,4]: 1 5 9    [2,5]: 1[2,6]: 5 9    [2,9]: 4 5    [3,2]: 5 7 8
...[9,9]: 2 3 4 5 7The foremost cell with one candidate at [2,5]Order please:

step 命令的输出，对比 1.0 版，2.0 版增加了 steps 累计值输出；待填格的候选值调整为三格共一行；若存在单候选值的 cell，则会在末尾部分输出最靠前的单候选值的 cell 位置。

从上面输出的信息可以看到，第一步只是求各个待填格的候选值，而没有做具体的填值操作，这和 1.0 版是一样的。

Order please:step000 000 000023 010 780100 406 009400 050 001900 000 006060 000 090005 000 800000 301 000000 090 000Steps:2Candidates:[1,1]: 5 6 7 8    [1,2]: 4 5 7 8 9    [1,3]: 4 6 7 8 9[1,4]: 2 5 7 8 9    [1,5]: 2 3 7 8    [1,6]: 2 3 5 7 8 9[1,7]: 1 2 3 4 5 6    [1,8]: 1 2 3 4 5 6    [1,9]: 2 3 4 5[2,1]: 5 6    [2,4]: 5 9    [2,6]: 5 9[2,9]: 4 5    [3,2]: 5 7 8    [3,3]: 7 8
...[9,7]: 1 2 3 4 5 6    [9,8]: 1 2 3 4 5 6 7    [9,9]: 2 3 4 5 7Order please:

第二步在 [2,5] 位置填上了 1，并对所有待填格的候选值做出调整，这和1.0 版依然是一样的。

所有待填格的候选值数目都大于 1，最靠前的最小候选值数目的待填格为 [2,1]，1.0 版下一步就开始第一级猜测：[2,1] = 5。现在来看 2.0 版有什么不同：

Order please:steprow 2 shrunken by group000 000 000623 010 784100 406 009400 050 001900 000 006060 000 090005 000 800000 301 000000 090 000Steps:5Candidates:[1,1]: 5 7 8    [1,2]: 4 5 7 8 9    [1,3]: 4 7 8 9[1,4]: 2 5 7 8 9    [1,5]: 2 3 7 8    [1,6]: 2 3 5 7 8 9[1,7]: 1 2 3 5 6    [1,8]: 1 2 3 5 6    [1,9]: 2 3 5[2,4]: 5 9    [2,6]: 5 9    [3,2]: 5 7 8
...[9,9]: 2 3 5 7Order please:

可以看到 [2,1] 位置上直接填上了 6，跳过了 [2,1] = 5 的猜测，同时还有 [2,9] = 4。相关的一条信息为：

row 2 shrunken by group

这是说，第 2 行所在的 9 个 cell 为一组，单纯由这一组 cell 的候选值分布情况就可以推导出某个（些）cell 的唯一取值来。具体看一下这里的情形，前两步之后，第 2 行有 4 个待填格（0-cell），其候选值分布情况为：

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

6 只在 [2,1] 的候选值中出现，所以必然有[2,1] = 6；同样地，有[2,9] = 4。

这便是第三步的行为，它把[2,1] 和 [2,9] 的候选值个数都缩减为 1，于是第四步接着做填值和候选值调整的工作。即交互输入的第 3 次 step 命令在程序内部实际走了两步，所以有 Steps:4 的输出信息。

往下不再单步走了，直接用一个 run 命令跑完：

Order please:runrow 4 shrunken by grouprow 4 shrunken by grouprow 7 shrunken by grouprow 7 shrunken by grouprow 7 shrunken by grouprow 7 shrunken by grouprow 8 shrunken by grouprow 8 shrunken by grouprow 8 shrunken by grouprow 8 shrunken by grouprow 1 shrunken by grouprow 6 shrunken by grouprow 3 shrunken by grouprow 5 shrunken by grouprow 6 shrunken by grouprow 5 shrunken by grouprow 9 shrunken by grouprow 9 shrunken by groupcol 2 shrunken by group549 738 162623 915 784187 426 359438 659 271951 872 436762 143 598395 264 817276 381 945814 597 623Done [steps:58, solution sum:1].Run time: 40 milliseconds; steps: 58, solution sum: 1.Order please:stepNo more solution (solution sum is 1).

从上面的输出信息可以看出，2.0 版求解这个心形数独题完全没有猜测。

SudokuSolver 2.0 程序实现

在 1.0 版的基础上，2.0 版做了以下方面的一些改进。

解决 load-quiz 命令实现的一处 bug

即输入交互命令 load-quiz H:\\s.txt 会报无效参数（Invalid argument）的错误：

Order please:load-quiz H:\\s.txtFail to open quiz file  H:\\s.txt with err 22:Invalid argument.

问题出在 dealOrder 函数里如下标黄行的代码：

void dealOrder(std::string& strOrder){std::string strEx;if (\"bye\" == strOrder)setQuit();else if (matchPrefixEx(strOrder, \"load-quiz\", strEx))CQuizDealer::instance()->loadQuiz(strEx);

调用 matchPrefixEx 函数传入的第二个参数为\”load-quiz\”，第一参数传入

load-quiz H:\\s.txt

matchPrefixEx 会给输出参数 strEx 填上 \” H:\\s.txt\”，即开头多了一个空格字符，导致调用到 loadQuiz 接口里打开文件时报非法参数的错误。

因此，修改方法很简单，只需把标黄代码行里的\”load-quiz\” 改为\”load-quiz \” 即可。

新增 CQuizDealer::adjustCandidates 接口

新增的adjustCandidates 接口替代原有的reCalcCandidates 接口。1.0 版里 reCalcCandidates 接口（参见SudokuSolver 1.0：用C++实现的数独解题程序【二】），对 m_setBlank 里的每个 0-cell 都重新计算其候选值集合，而adjustCandidates 只对新填值 cell 所在行、所在列、所在宫里 0-cell 的候选值集合做微调的收缩处理，即从集合中去掉新填值。具体实现如下：

bool CQuizDealer::adjustCandidates(u8 idx, u8 val){u8 row = idx / 9;u8 col = idx % 9;u8 blk = (row / 3) * 3 + (col / 3);u8 rowBase = row * 9;for (u8 colIdx = 0; colIdx < 9; ++colIdx) {Cell& cel = m_seqCell[rowBase + colIdx];if (cel.val != 0)continue;if (!removeVal(cel.candidates, val)) {printf(\"shrinking %d from [%d,%d] went wrong\\n\", (int)val, (int)row + 1, (int)colIdx + 1);return false;}}for (u8 rowIdx = 0; rowIdx < 81; rowIdx += 9) {Cell& cel = m_seqCell[rowIdx + col];if (cel.val != 0)continue;if (!removeVal(cel.candidates, val)) {printf(\"shrinking %d from [%d,%d] went wrong\\n\", (int)val, (int)rowIdx / 9 + 1, (int)col + 1);return false;}}for (u8 blkIdx = 0; blkIdx < 9; ++blkIdx) {Cell& cel = m_seqCell[block2row(blk, blkIdx) * 9 + block2col(blk, blkIdx)];if (cel.val != 0)continue;if (!removeVal(cel.candidates, val)) {printf(\"shrinking %d from blk[%d,%d] went wrong\\n\", (int)val, (int)blk + 1, (int)blkIdx + 1);return false;}}return true;}

其中用到的 removeVal 函数实现如下：

bool removeVal(u8* pVals, u8 val){shrink(pVals, val);return (pVals[0] != 0);}

shrink 为候选值集合收缩函数，实现如下：

void shrink(u8* pVals, u8 val){for (u8 idx = 1; idx <= pVals[0]; ++idx) {if (pVals[idx] != val)continue;for (u8 pos = idx + 1; pos <= pVals[0]; ++pos)pVals[pos - 1] = pVals[pos];pVals[0] = pVals[0] - 1;break;}}

shift 接口实现只改动如下所示的末尾一行代码：

bool CQuizDealer::shift(u8 idx, u8 valIdx){m_seqCell[idx].val = m_seqCell[idx].candidates[valIdx];m_seqCell[idx].candidates[0] = 0;if (!adjustTakens(idx, m_seqCell[idx].val))return false;std::set<u8>::iterator it = m_setBlank.find(idx);m_setBlank.erase(it);return adjustCandidates(idx, m_seqCell[idx].val);}

一些精确求解方法的实现

这部分增加的代码量最多，也使得 2.0 版的代码总量比 1.0 版的代码总量翻了一倍。为避免重复，以下代码内容和 1.0 版相同的部分多使用省略号表示。

CQuizDealer 声明部分增加的内容

class CQuizDealer{public:...
private:enum {STA_UNLOADED = 0, STA_LOADED, STA_INVALID, STA_VALID, STA_DONE};enum {RET_PENDING, RET_OK, RET_WRONG};...
    bool calcCandidates(u8 idx);bool adjustCandidates(u8 idx, u8 val);void guess(u8 idx);...
    void useSnapshot(Snapshot* pSnap);u8 filterCandidates();u8 filterRowGroup(u8 row);u8 filterColGroup(u8 col);u8 filterBlkGroup(u8 blk);u8 filterRowCandidatesEx(u8 row);bool filterOneGroup(u8* pGrp);u8 filterRowByPolicy1(u8 row, u8 idx, u8* pVals, u8* pBlkTakens);u8 shrinkRowCandidatesP1(u8* pBlk, u8* pRow, u8 zeroSum, u8 row, u8 colBase);u8 shrinkCandidates(u8 cellPos, u8* pVals);u8 filterRowByPolicy2(u8 row, u8 idx, u8* pVals, u8* pBlkTakens);u8 shrinkRowCandidatesP2(u8* pBlk, u8* pRow, u8 zeroSum, u8 row, u8 colBase);void calcExCols(u8* pEx, u8* pBlk, u8* pRow, u8 rowBase, u8 colBase, bool ply1);void setBlkRowTakens(u8 blkBase, u8 innRow, u8* pTakens);void setRowTakensInBlk(u8 rowBase, u8 colBase, u8* pVals);u8 filterColCandidatesEx(u8 col);void setBlkColTakens(u8 blkBase, u8 innCol, u8* pTakens);void setColTakensInBlk(u8 col, u8 rowBase, u8* pVals);u8 filterColByPolicy1(u8 col, u8 idx, u8* pVals, u8* pBlkTakens);u8 shrinkColCandidatesP1(u8* pBlk, u8* pCol, u8 zeroSum, u8 col, u8 segRowBase);u8 filterColByPolicy2(u8 col, u8 idx, u8* pVals, u8* pBlkTakens);u8 shrinkColCandidatesP2(u8* pBlk, u8* pCol, u8 zeroSum, u8 col, u8 segRowBase);void calcExRows(u8* pEx, u8* pBlk, u8* pCol, u8 col, u8 segRowBase, bool ply1);Cell m_seqCell[81];...};

adjust 接口实现修改

void CQuizDealer::adjust(){if (m_state != STA_VALID)return;bool changed = false;u8 guessIdx = 0;u8 lowestSum = 10;for (std::set<u8>::iterator it = m_setBlank.begin(); it != m_setBlank.end();) {u8 idx = *it;u8 sum = m_seqCell[idx].candidates[0];if (sum != 1) {if (sum < lowestSum) {lowestSum = sum;guessIdx = idx;}++it;continue;}m_seqCell[idx].val = m_seqCell[idx].candidates[1];m_seqCell[idx].candidates[0] = 0;if (!adjustTakens(idx, m_seqCell[idx].val)) {nextGuess();23             return;}m_setBlank.erase(it++);if (!adjustCandidates(idx, m_seqCell[idx].val)) {nextGuess();return;}changed = true;}if (changed)++m_steps;if (m_setBlank.empty()) {m_state = STA_DONE;m_soluSum++;return;}if (!changed) {u8 v = filterCandidates();if (v == RET_OK)adjust();else if (v == RET_WRONG)nextGuess();elseguess(guessIdx);return;}}

可以看到，adjust 接口的修改主要是两处：一处（lines 26-29）是每当给一个 0-cell 填值后随即调用 adjustCandidates 接口做相关 cells 的候选值集合收缩处理；另一处（lines 39-48）是当前所有的 0-cell 都没有收缩为单候选值时，调用新增接口 filterCandidates 对 0-cell 做进一步的候选值集合收缩处理，并根据收缩结果的不同调用相应的接口。

filterCandidates 接口有三种返回值：RET_PENDING、RET_OK、RET_WRONG，分别对应：所有 0-cell 的候选值数目都大于 1 的情形、某 0-cell 的候选值数目等于 1 的情形、某0-cell 的候选值数目等于 0 的情形（即无法填值的情形）。

新增的filterCandidates 接口

u8 CQuizDealer::filterCandidates(){++m_steps;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;for (u8 row = 0; row < 9; ++row)if (ret =filterRowCandidatesEx(row))return ret;for (u8 col = 0; col < 9; ++col)if (ret =filterColCandidatesEx(col))return ret;return ret;}

filterCandidates 接口实现内部汇集了两类候选值集合收缩算法，如上梅色标注的子接口属于第一类，浅天蓝色标注的子接口属于第二类。

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;if (filterOneGroup(celIdxs)) {printf(\"row %d shrunken by group\\n\", (int)row + 1);return RET_OK;}return RET_PENDING;}

fillRowGroup 接口实现的候选值集合收缩算法在前面的实例中已经做过陈述。具体从实现看，代码分为两部分：

（1）遍历由参数 row 指定的行，找出该行中的全体 0-cell，并把它们的下标记录到数组 celIdxs 中，该行 0-cell 的总数记录在 celIdxs 的头项里；

（2）调用 filterOneGroup(celIdxs) 实施对指定一组 cell 做候选值集合收缩处理。

filterColGroup 和filterBlkGroup 接口

u8 CQuizDealer::filterColGroup(u8 col){u8 celIdxs[10] = {0}; // first item denotes sum of zerosfor (u8 row = 0; row < 9; ++row) {u8 celIdx = row * 9 + col;if (m_seqCell[celIdx].val == 0) {celIdxs[0] += 1;celIdxs[celIdxs[0]] = celIdx;}}if (celIdxs[0] == 0)return RET_PENDING;if (filterOneGroup(celIdxs)) {printf(\"col %d shrunken by group\\n\", (int)col + 1);return RET_OK;}return RET_PENDING;}u8 CQuizDealer::filterBlkGroup(u8 blk){u8 celIdxs[10] = {0}; // first item denotes sum of zerosfor (u8 idx = 0; idx < 9; ++idx) {u8 celIdx = block2row(blk, idx) * 9 + block2col(blk, idx);if (m_seqCell[celIdx].val == 0) {celIdxs[0] += 1;celIdxs[celIdxs[0]] = celIdx;}}if (celIdxs[0] == 0)return RET_PENDING;if (filterOneGroup(celIdxs)) {printf(\"blk %d shrunken by group\\n\", (int)blk + 1);return RET_OK;}return RET_PENDING;}

这两个接口实现和 filterRowGroup 的实现是类似的，只是以一列 cell 或一宫 cell 为一组。三个接口的核心算法实现都在 filterOneGroup 接口。

filterOneGroup 接口

bool CQuizDealer::filterOneGroup(u8* pGrp){u8 size = pGrp[0];u8 times[20] = {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];times[val] += 1;times[val + 9] = pGrp[idx];}}bool ret = false;for (u8 val = 1; val <= 9; ++val) {if (times[val] == 1) {ret = true;u8 celIdx = times[val + 9];m_seqCell[celIdx].candidates[0] = 1;m_seqCell[celIdx].candidates[1] = val;}}return ret;}

该接口的算法实现很简单。用了一个 times 数组用于累计指定一组 cell 的各个候选值出现的次数，比如某个 0-cell 有候选值 3 和 8，那么 times[3] 和 times[8] 最终会分别累计出 3 和 8 各自出现的次数，同时times[3 + 9] 和 times[8 + 9] 里会分别记录最后出现 3 和 8 的那个 0-cell 的下标。这样，当遍历完指定一组的 0-cell，检查 times 数组中下标 1 到 9 的单元有取值为 1 的，就说明对应的 0-cell 可以收缩为单个候选值。

第二类候选值集合收缩算法实现代码放到下一篇。

SudokuSolver 2.0：用C++实现的数独解题程序【一】