SudokuSolver 2.3 程序实现

用C++实现的数独解题程序 SudokuSolver 2.2 及实例分析里新发现了一处可以改进 grp 算法的地方，本次版本实现了对应的改进 grp 算法。

CQuizDealer 类声明部分的修改

增加了两个私有接口：

bool sameCandidates(u8 cel1, u8 cel2);u8 anotherGreenWorld(u8* pGrp);u8 incompleteShrinkByAGW(u8 times, u8* pTimesVals, u8* pValsCells, u8* pGrp);

anotherGreenWorld，这个略显随意和突兀的命名，来自 Brian Eno 于 1977 年发行的专辑《Another Green World》。

filterOneGroup 接口实现的小修改

把末尾的

return RET_PENDING;

改为

return anotherGreenWorld(pGrp);

anotherGreenWorld 接口实现

u8 CQuizDealer::anotherGreenWorld(u8* pGrp){u8 valsCells[100] = {0};u8 size = pGrp[0];for (u8 idx = 1; idx <= size; ++idx) {u8 valSum = m_seqCell[pGrp[idx]].candidates[0];for (u8 vidx = 1; vidx <= valSum; ++vidx) {u8 val = m_seqCell[pGrp[idx]].candidates[vidx];u8 pos = val * 10 + valsCells[val];valsCells[pos] = pGrp[idx];valsCells[val] += 1;}}u8 timesVals[100] = {0};for (u8 val = 1; val < 10; ++val) {u8 times = valsCells[val];if (times == 0)continue;u8 pos = times * 10 + timesVals[times];timesVals[pos] = val;timesVals[times] += 1;}for (u8 times = 2; times <= 6; ++times) {if (times > timesVals[times])continue;u8 ret = incompleteShrinkByAGW(times, timesVals, valsCells, pGrp);if (ret != RET_PENDING)return ret;}return RET_PENDING;}

incompleteShrinkByAGW 接口实现

u8 CQuizDealer::incompleteShrinkByAGW(u8 times, u8* pTimesVals, u8* pValsCells, u8* pGrp){u8 combi[10] = {0};combi[0] = pTimesVals[times];for (u8 idx = 0; idx < times; ++idx)combi[idx + 1] = idx;u8 base = times * 10;while (true) {u8 celSet[10] = {0};u8 valSet[10] = {0};if (matchValsCells(times, combi, pTimesVals, pValsCells, celSet, valSet)) {valSet[0] = times;bool shrunken = false;for (u8 idx = 1; idx <= times; ++idx) {u8 cel = celSet[idx];u8 candiSum = m_seqCell[cel].candidates[0];if (candiSum == times)continue;if (candiSum < times) {printf(\"AGW: [%d,%d] candidates %d lower than times %d!\\n\", (int)(cel / 9 + 1), (int)(cel % 9 + 1), (int)candiSum, (int)times);return RET_WRONG;}shrunken = true;for (u8 pos = 1; pos <= candiSum; ++pos) {u8 val = m_seqCell[cel].candidates[pos];if (!inSet(val, valSet)) {removeVal(m_seqCell[cel].candidates, val);printf(\"%d shrunken out of [%d,%d] by AGW\\n\", (int)val, (int)(cel / 9 + 1), (int)(cel % 9 + 1));}}}if (shrunken) {                printCelSetValSet(celSet, valSet);return RET_SHRUNKEN;}}if (!move2NextCombi(times, combi))break;}return RET_PENDING;}

辅助函数 move2NextCombi 的实现

bool move2NextCombi(u8 times, u8* pCombi){if (pCombi[1] == pCombi[0] - times)return false;u8 bound = pCombi[0] - 1;for (u8 idx = times; idx > 0; --idx) {if (pCombi[idx] < bound - (times - idx)) {pCombi[idx] += 1;for (u8 tail = idx + 1; tail <= times; ++tail)pCombi[tail] = pCombi[tail - 1] + 1;return true;}}return true;}

辅助函数matchValsCells 的实现

bool matchValsCells(u8 times, u8* pCombi, u8* pTimesVals, u8* pValsCells, u8* pCelSet, u8* pValSet){u8 base = times * 10;for (u8 idx = 1; idx <= times; ++idx) {u8 pos = base + pCombi[idx];u8 val = pTimesVals[pos];pValSet[idx] = val;if (pCelSet[0] == 0) {pCelSet[0] = times;memcpy(pCelSet + 1, &(pValsCells[val * 10]), times);continue;}if (0 != memcmp(pCelSet + 1, &(pValsCells[val * 10]), times))return false;}return true;}

辅助函数printCelSetValSet 的实现

void printCelSetValSet(u8* pCelSet, u8* pValSet){printf(\"CelSet: \");for (u8 idx = 1; idx <= pCelSet[0]; ++idx) {u8 cel = pCelSet[idx];printf(\"[%d,%d] \", (int)(cel / 9 + 1), (int)(cel % 9 + 1));}printf(\"ValSet: \");for (u8 idx = 1; idx <= pValSet[0]; ++idx) {printf(\"%d \", (int)pValSet[idx]);}printf(\"\\n\");}

版本信息调整

// 1.0 2021/9/20// 2.0 2021/10/2// 2.1 2021/10/4// 2.2 2021/10/10#define STR_VER \"Sudoku Solver 2.3 2021/10/17 by readalps\\n\\n\"

实例分析

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

1286) col 9 complete shrunken by group[9,4]: 2 3 7 8 shrunken to  3 8 worked by row-ply1.[9,5]: 1 2 3 6 7 8 shrunken to  1 3 8 worked by row-ply1.[9,6]: 1 2 3 6 8 shrunken to  1 3 8 worked by row-ply1.[6,6]: 2 6 9 shrunken to  6 9 worked by col-ply2.[7,6]: 2 9 shrunken to  9 worked by col-ply2.1288) col 6 shrunken ply-2 by vblk 1

一处是第 9 行的 row-ply1，另一处是紧随其后，第 6 列的 col-ply2。依次来分析一下。

先用 runtil 1286 命令进入当时的上下文：

1286) col 9 complete shrunken by group860 000 003023 600 000070 090 206050 007 000010 045 700080 100 030541 000 368038 504 910090 000 400Steps:1287Candidates:[1,3]: 4 5 9    [1,4]: 2 4 7    [1,5]: 1 2 5 7[1,6]: 1 2    [1,7]: 1 5    [1,8]: 4 5 7 9[2,1]: 1 4 9    [2,5]: 1 5 7 8    [2,6]: 1 8[2,7]: 1 5 8    [2,8]: 4 5 7 8 9    [2,9]: 1 4 5 7 9[3,1]: 1 4    [3,3]: 4 5    [3,4]: 3 4 8[3,6]: 1 3 8    [3,8]: 4 5 8    [4,1]: 2 3 4 6 9[4,3]: 2 4 6 9    [4,4]: 2 3 8 9    [4,5]: 2 3 6 8[4,7]: 1 6 8    [4,8]: 2 4 8 9    [4,9]: 1 2 4 9[5,1]: 2 3 6 9    [5,3]: 2 6 9    [5,4]: 2 3 8 9[5,8]: 2 8 9    [5,9]: 2 9    [6,1]: 2 4 6 7 9[6,3]: 2 4 6 7 9    [6,5]: 2 6    [6,6]: 2 6 9[6,7]: 5 6    [6,9]: 2 4 5 9    [7,4]: 2 7 9[7,5]: 2 7    [7,6]: 2 9    [8,1]: 2 6 7[8,5]: 2 6 7    [8,9]: 2 7    [9,1]: 2 6 7[9,3]: 2 6 7    [9,4]: 2 3 7 8    [9,5]: 1 2 3 6 7 8[9,6]: 1 2 3 6 8    [9,8]: 2 5 7    [9,9]: 2 5 7The foremost cell with 2 candidate(s) at [1,6]At guess level 5 [1,2] 2Run time: 270 milliseconds; steps: 1287, solution sum: 1.

1286 步时，第 9 列满足完全收缩的 grp 算法，因而有至少一个空位的候选值收缩为单值，进行填值后调整关联空位的候选值，步数加一，当前输出的实际上是走完 1287 步后的上下文。现在把关注点放到第 9 行，当时 quiz 已填值情况为：

860 000 003023 600 000070 090 206050 007 000010 045 700080 100 030541 000 368038 504 910090 000 400

从下一步的输出信息看，第 9 行施用了 row-ply1，且 [9,4]、[9,5]、[9,6] 三个空位都得到了收缩，可推知是左下宫和右下宫的已填值交集作用于第 9 行的第二节所致，即：

{5, 4, 1, 3, 8} ∩ {3, 6, 8, 9, 1} = {1, 3, 8}

所以，[9,4]、[9,5]、[9,6] 三个空位必然要填入{1, 3, 8} 里的三个数。而第 9 行当时各个空位的候选值分布情况为：

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

这就很好地对应上了下一步的输出信息：

[9,4]: 2 3 7 8 shrunken to  3 8 worked by row-ply1.[9,5]: 1 2 3 6 7 8 shrunken to  1 3 8 worked by row-ply1.[9,6]: 1 2 3 6 8 shrunken to  1 3 8 worked by row-ply1.

单纯考虑第 9 行当时各个空位的候选值分布情况，这次的不完全收缩也能这样推导出来：

[9,1]、[9,3]、[9,8]、[9,9] 这四个空位的候选值集合的并集为 {2, 5, 6, 7}，第 9 行的七个空位的待填值集合为 {2, 5, 6, 7, 1, 3, 8}，因而另三个空位的待填值必然为 {1, 3, 8}。

可以依此再实现一个补充的不完全收缩 grp 算法（比如叫做 thirdGreenWorld~），这也进一步推进了用C++实现的数独解题程序 SudokuSolver 2.1 及实例分析里的那个推测：grp 算法增强后有可能就不需要使用第二类收缩算法。这一点要明确出来，需要数学上的严格推导。

接着来看第 6 列的 col-ply2。即：

[6,6]: 2 6 9 shrunken to  6 9 worked by col-ply2.[7,6]: 2 9 shrunken to  9 worked by col-ply2.

当时 quiz 已填值情况为：

860 000 003023 600 000070 090 206
050 007 000010 045 700080 100 030
541 000 368038 504 910090 000 400

第 6 列纵向跨越第 2 宫、第 5 宫、第 8 宫，[6,6] 和 [7,6] 分别属于其中的后两宫。对第 6 列施行 col-ply2，可以推定是把第 2 宫里的 6 和 9 考虑往第 6 列的第二节和第三节的空位上填。

从上面的全体空位候选值分布信息里提取出第 6 列各空位的候选值分布情况，为：

[1,6]: 1 2
[2,6]: 1 8
[3,6]: 1 3 8
[6,6]: 2 6 9
[7,6]: 2 9
[9,6]: 1 2 3 6 8

其中，[9,6] 空位因为刚才的第 9 行的 row-ply1，其候选值集合中只剩下 1、3、8。第 6 列的第二节和第三节共有三个空位，即 [6,6]、[7,6] 和 [9,6]，往这三个空位里填 6 和 9，而 [9,6] 的候选值里没有 6 和 9，因而 6 和 9 必然要填入[6,6] 和 [7,6]，即有：

[6,6]: 2 6 9 shrunken to  6 9 worked by col-ply2.[7,6]: 2 9 shrunken to  9 worked by col-ply2.

这里第 6 列的 col-ply2 得以发生是借助了第 9 行的 row-ply1。第 6 列的 col-ply2 实施的收缩效果在现有的 grp 算法一样可以应对，即：

第 6 列的各空位中，只有 [6,6] 有候选值6，因而直接推定 [6,6] = 6，进而用同样的方法推定 [7,6] = 9，以及 [1,6] = 2，等等。