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

本文主要是介绍SudokuSolver 1.1：用C++实现的数独解题程序【二】，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

本篇是 SudokuSolver 1.1：用C++实现的数独解题程序【一】的续篇。

filterRowCandidatesEx 接口

 1 u8 CQuizDealer::filterRowCandidatesEx(u8 row)
 2 {
 3     u8 vals[10] = {0}; // last item denotes sum of zeros
 4     u8 base = row * 9;
 5     for (u8 col = 0; col < 9; ++col) {
 6         vals[col] = m_seqCell[base + col].val;
 7         if (vals[col] == 0) {
 8             vals[9] += 1;
 9         }
10     }
11     if (vals[9] == 0)
12         return RET_PENDING;
13     u8 blkBase = (row / 3) * 3;
14     u8 blkTakens[21] = {0};
15     setBlkRowTakens(blkBase, row % 3, blkTakens);
16     if (blkTakens[0] == 0 && blkTakens[7] == 0 && blkTakens[14] == 0)
17         return RET_PENDING;
18     u8 ret = RET_PENDING;
19     for (u8 idx = 0; idx < 3; ++idx) {
20         if (ret = filterRowByPolicy1(row, idx, vals, blkTakens))
21             return ret;
22     }
23     for (u8 idx = 0; idx < 3; ++idx) {
24         if (ret = filterRowByPolicy2(row, idx, vals, blkTakens))
25             return ret;
26     }
27     return RET_PENDING;
28 }

filterRowCandidatesEx 接口实现对由参数 row 指定的行实施第二类候选值集合收缩算法。第 3 行到第 12 行的代码段是把该行当前各个 cell 的值填到数组 vals 中，并用 vals[9] 记录 0-cell 数量，若 vals[9] 为 0，则说明该行没有 0-cell，即不具备收缩价值，直接返回 RET_PENGING，好让调用者进一步去考察其它行。

第 13 行到第 17 行的代码段是调用 setBlkRowTakens 接口填制 blkTakens 数组。blkTakens 数组实际记录了三个集合。举例说明一下：

000 000 000
023 010 780
100 406 009

400 050 001
900 000 006
060 000 090
...

第二行从左至右每 3 个一节，被划分为三节，这三节分别落在第 1 宫、第 2 宫、第 3 宫。事实上，每一行都可以依次方法划分为三节，每一节对应左、中、右各一个宫。blkTakens 数组的单元，每 7 个一组分成三组，每组记录一个宫中除去指定的行之外已填数字的集合。在上例中，填入 blkTakens 数组的三个集合分别是 {1}、{4, 6}、{9}，对应到 blkTakens 数组的单元取值，则有：

blkTakens[0] = 1，blkTakens[1] = 1；
blkTakens[7] = 2，blkTakens[8] = 4，blkTakens[9] = 6；
blkTakens[14] = 1，blkTakens[15] = 9。

第 2 行有 4 个空位（0-cell），具体分布是第一节 1 个，第二节 2 个，第三节 1 个。而 blkTakens 数组的中宫集合，即 {4, 6} ，里的元素不能填到第 2 行的第二节（不然中宫里会出现两个 4 或两个 6），于是 4 和 6 只能填到第 2 行的第一节和第三节的空位上，而 [2,9] 空位的候选值里不能有 6（因为第 9 列里已经有 6），于是可以推定 [2,9] = 4，进而又有 [2,1] = 6。

仍以上面的例子为例，考察第 4 行，则填入 blkTakens 数组的三个集合分别是 {6,9}、{}、{6,9}，对应到 blkTakens 数组的单元取值，则有：

blkTakens[0] = 2，blkTakens[1] = 9，blkTakens[2] = 6；
blkTakens[7] = 0；
blkTakens[14] = 2，blkTakens[15] = 6，blkTakens[16] = 9。

第 4 行有 6 个空位，具体分布是每一节各 2 个。而 blkTakens 数组的左宫集合与右宫集合相等，更一般而言，它们的交集为 {6, 9} ，易知这个交集里的元素只能填到第 4 行的第二节的空位上，而 [4,6] 空位的候选值里不能有 6（因为第 6 列里已经有 6），于是可以推定 [4,6] = 9，进而又有 [4,4] = 6。

上面例子里的第 2 行和第 4 行收缩示例实际就是 filterRowByPolicy2 和 filterRowByPolicy1 里分别实现的方法。

setBlkRowTakens 接口

 1 void CQuizDealer::setBlkRowTakens(u8 blkBase, u8 innRow, u8* pTakens)
 2 {
 3     for (u8 idx = 0; idx < 3; ++idx) {
 4         u8 blk = blkBase + idx;
 5         u8* pVals = pTakens + idx * 7;
 6         u8 colBase = idx * 3;
 7         u8 row = block2row(blk, ((innRow + 1) % 3) * 3);
 8         setRowTakensInBlk(row * 9, colBase, pVals);
 9         row = block2row(blk, ((innRow + 2) % 3) * 3);
10         setRowTakensInBlk(row * 9, colBase, pVals);
11     }
12 }

其中调用的 setRowTakensInBlk 接口为：

 1 void CQuizDealer::setRowTakensInBlk(u8 rowBase, u8 colBase, u8* pVals)
 2 {
 3     for (u8 col = colBase; col < colBase + 3; ++col) {
 4         u8 val = m_seqCell[rowBase + col].val;
 5         if (val != 0) {
 6             u8 sum = pVals[0] + 1;
 7             pVals[sum] = val;
 8             pVals[0] = sum;
 9         }
10     }
11 }

filterRowByPolicy1 接口

 1 u8 CQuizDealer::filterRowByPolicy1(u8 row, u8 idx, u8* pVals, u8* pBlkTakens)
 2 {
 3     u8 colBase = idx * 3;
 4     u8 v1 = pVals[colBase], v2 = pVals[colBase + 1], v3 = pVals[colBase + 2];
 5     u8 zeroSum = (u8)(v1 == 0) + (u8)(v2 == 0) + (u8)(v3 == 0);
 6     if (zeroSum == 0)
 7         return RET_PENDING;
 8     u8 isVals[7] = {0};
 9     if (idx == 0)
10         intersection(pBlkTakens + 7, pBlkTakens + 14, isVals);
11     else if (idx == 1)
12         intersection(pBlkTakens, pBlkTakens + 14, isVals);
13     else
14         intersection(pBlkTakens, pBlkTakens + 7, isVals);
15     if (isVals[0] == 0)
16         return RET_PENDING;
17     return shrinkRowCandidatesP1(isVals, pVals, zeroSum, row, colBase);
18 }

filterRowCandidatesEx 接口里调用 filterRowByPolicy1 的代码段如下：

19     for (u8 idx = 0; idx < 3; ++idx) {
20         if (ret = filterRowByPolicy1(row, idx, vals, blkTakens))
21             return ret;
22     }

沿用上面的例子说明一下 filterRowByPolicy1 接口的实现代码：

000 000 000
023 010 780
100 406 009

400 050 001
900 000 006
060 000 090
...

考察第四行，上面代码段里至多会调用 filterRowByPolicy1 接口三次，idx 由 0 开始，逐次加一。

先看 idx = 0 的情形，四个传入参数分别为：row = 3（第四行的行下标为 3）、idx = 0、vals 中记录了第四行各 cell 的取值、blkTakens 中记录了三个集合，即左宫集合 {6, 9}，中宫集合 {}，右宫集合 {6, 9}。这一次调用是求中宫集合与右宫集合的交集，并试图往第四行第一节的空位上填值。

第 3 行到第 7 行的代码段，考察第四行的第一节三个 cell 中有几个空位，若没有空位，则无需填值；此时有两个空位，继续往下走。

第 8 行到第 16 行的代码段，求集合交集。因为 {} ∩ {6, 9} = {}，即交集为空，没有明确要填空的值，直接返回 RET_PENDING（即 0）。回到 filterRowCandidatesEx 接口，idx 加一，再次调用 filterRowByPolicy1。

此时 idx = 1，要试图往第四行第二节填空，第二节有空位，继续考察左宫集合 {6, 9} 与右宫集合 {6, 9} 的交集，交集不为空，进一步调用 shrinkRowCandidatesP1 接口，发现可以对第四行做收缩处理，返回 RET_OK，回到 filterRowCandidatesEx 接口，继续向上级调用返回 RET_OK。

intersection 函数实现求两个集合的交集，具体实现为：

 1 void intersection(u8* pA, u8* pB, u8* pOut)
 2 {
 3     u8 sumA = pA[0], sumB = pB[0];
 4     if (sumA == 0 || sumB == 0)
 5         return;
 6     for (u8 pos = 1; pos <= sumA; ++pos)
 7         for (u8 idx = 1; idx <= sumB; ++idx)
 8             if (pB[idx] == pA[pos]) {
 9                 u8 sum = pOut[0] + 1;
10                 pOut[sum] = pA[pos];
11                 pOut[0] = sum;
12                 break;
13             }
14 }

shrinkRowCandidatesP1 接口

 1 u8 CQuizDealer::shrinkRowCandidatesP1(u8* pBlk, u8* pRow, u8 zeroSum, u8 row, u8 colBase)
 2 {
 3     for (u8 col = colBase; col < colBase + 3; ++col) {
 4         if (pRow[col] != 0)
 5             if (!removeVal(pBlk, pRow[col]))
 6                 return RET_PENDING;
 7     }
 8     if (zeroSum < pBlk[0]) {
 9         printf("shrinking row %d with ply1[blk:%d] went WRONG: 0Sum [%d] < vSum [%d]\n", (int)row + 1, (int)colBase / 3 + 1, (int)zeroSum, (int)pBlk[0]);
10         return RET_WRONG;
11     }
12     u8 rowBase = row * 9;
13     u8 exVals[4] = {0};
14     if (zeroSum > pBlk[0]) {
15         calcExCols(exVals, pBlk, pRow, rowBase, colBase, true);
16         if (zeroSum - exVals[0] < pBlk[0]) {
17             printf("shrinking row %d with ply1[blk:%d] went WRONG: 0Sum [%d] - xSum [%d] < vSum [%d]\n", (int)row + 1, (int)colBase / 3 + 1, (int)zeroSum, (int)exVals[0], (int)pBlk[0]);
18             return RET_WRONG;
19         }
20         if (zeroSum - exVals[0] > pBlk[0])
21             return RET_PENDING;
22     }
23     u8 ret = RET_PENDING;
24     bool shrunken = false;
25     for (u8 col = colBase; col < colBase + 3; ++col) {
26         if (pRow[col] != 0 || inSet(col, exVals))
27             continue;
28         ret = shrinkCandidates(rowBase + col, pBlk);
29         if (ret == RET_WRONG) {
30             printf("shrinking [%d,%d] with row-ply1 went WRONG\n", (int)row + 1, (int)col + 1);
31             return RET_WRONG;
32         }
33         if (ret == RET_OK)
34             shrunken = true;
35     }
36     if (shrunken) {
37         ret = RET_OK;
38         printf("row %d shrunken ply-1 by blk %d\n", (u8)row + 1, (u8)colBase / 3 + 1);
39     }
40     return ret;
41 }

shrinkRowCandidatesP1 接口实现考虑的情形比前述例子里的情形要复杂一些。

第 3 行到第 11 行的代码段是对传入的交集集合 pBlk 做进一步的削减处理，因为交集中某个数字如果已经在要填入的对应行的对应节中出现，则需要从交集中剔除（removeVal 函数实现在上一篇里有）。做完剔除处理后，集合里的数字都是待填值，此时若空位数小于待填值的数量，则必然会导致无法求解的局面，因此返回 RET_WRONG，好让上层调用尽快做出调整。

第 12 行到第 22 行的代码段的逻辑还要复杂一些，通过调用 calcExCols 接口考察对应行的对应节中的空位的候选值情况，若某个空位的候选值集合和做完剔除处理的待填值集合无交集，则把该空位的列下标记入 exVals 数组。exVals 里记录的空位是不能填值的，因此，此时若空位数减去 exVals 里的空位数小于待填值的数量，还是会导致无法求解的局面，同样需要返回 RET_WRONG。

第 23 行到第 40 行的代码段是遍历对应行的对应节的空位，调用 shrinkCandidates 接口试图对空位的候选值做收缩处理。

上面用到的 inSet 函数实现为：

1 bool inSet(u8 val, u8* pVals)
2 {
3     for (u8 idx = 1; idx <= pVals[0]; ++idx)
4         if (val == pVals[idx])
5             return true;
6     return false;
7 }

calcExCols 接口

 1 void CQuizDealer::calcExCols(u8* pEx, u8* pBlk, u8* pRow, u8 rowBase, u8 colBase, bool ply1)
 2 {
 3     u8 lower = (ply1 ? colBase : 0);
 4     u8 upper = (ply1 ? colBase + 3 : 9);
 5     for (u8 col = lower; col < upper; ++col) {
 6         if (ply1) {
 7             if (pRow[col] != 0)
 8                 continue;
 9         }
10         else {
11             if (pRow[col] != 0 || (col >= colBase && col <= colBase + 2))
12                 continue;
13         }
14         u8 vals[10] = {0};
15         intersection(m_seqCell[rowBase + col].candidates, pBlk, vals);
16         if (vals[0] == 0) {
17             u8 sum = pEx[0] + 1;
18             pEx[sum] = col;
19             pEx[0] = sum;
20         }
21     }
22 }

calcExCols 接口为 shrinkRowCandidatesP1 和 shrinkRowCandidatesP2 共用。

shrinkCandidates 接口

 1 u8 CQuizDealer::shrinkCandidates(u8 cellPos, u8* pVals)
 2 {
 3     u8 vals[10] = {0};
 4     intersection(m_seqCell[cellPos].candidates, pVals, vals);
 5     if (vals[0] == 0)
 6         return RET_WRONG;
 7     if (vals[0] != m_seqCell[cellPos].candidates[0]) {
 8         for (u8 idx = 0; idx <= pVals[0]; ++idx)
 9             m_seqCell[cellPos].candidates[idx] = vals[idx];
10         if (vals[0] == 1)
11             return RET_OK;
12     }
13     return RET_PENDING;
14 }

shrinkCandidates 接口对下标为 cellPos 的 0-cell 做候选值收缩处理，逻辑不难，不做额外解释。

filterRowByPolicy2 接口

 1 u8 CQuizDealer::filterRowByPolicy2(u8 row, u8 idx, u8* pVals, u8* pBlkTakens)
 2 {
 3     u8 colBase = idx * 3;
 4     u8 v1 = pVals[colBase], v2 = pVals[colBase + 1], v3 = pVals[colBase + 2];
 5     u8 zeroSum = pVals[9] - (u8)(v1 == 0) - (u8)(v2 == 0) - (u8)(v3 == 0);
 6     if (zeroSum == 0)
 7         return RET_PENDING;
 8     u8* pBlk = pBlkTakens + (idx * 7);
 9     if (pBlk[0] == 0)
10         return RET_PENDING;
11     return shrinkRowCandidatesP2(pBlk, pVals, zeroSum, row, colBase);
12 }

filterRowByPolicy2 和 filterRowByPolicy1 类似。

继续沿用上面的例子说明一下 filterRowByPolicy2 接口的实现代码：

000 000 000
023 010 780
100 406 009

400 050 001
900 000 006
060 000 090
...

考察第二行，filterRowCandidatesEx 接口里至多会调用 filterRowByPolicy2 接口三次，idx 由 0 开始，逐次加一。

先看 idx = 0 的情形，四个传入参数分别为：row = 3（第四行的行下标为 3）、idx = 0、vals 中记录了第四行各 cell 的取值、blkTakens 中记录了三个集合，即左宫集合 {1}，中宫集合 {4, 6}，右宫集合 {9}。这一次调用是考察左宫集合 {1}，并试图往第二行的第二节和第三节的空位上填值。

第 3 行到第 7 行的代码段，考察第二行的第二节和第三节共有几个空位，若没有空位，则无需填值；此时有三个空位，继续往下走。

第 8 行到第 10 行的代码段，求 idx = 0 对应的集合，即左宫集合 {1}。不为空，继续调用 shrinkRowCandidatesP2 接口做进一步处理，后者会因为左宫集合 {1} 里的 1 已经出现在第二行第二节里而返回 RET_PENDING。

回到 filterRowCandidatesEx 接口，idx 加一，再次调用 filterRowByPolicy2。

此时 idx = 1，要试图往第二行的第一节和第三节填空，此两节共有两个空位，而 idx = 1 对应中宫集合 {4, 6}，不为空，进一步调用 shrinkRowCandidatesP2 接口，后者发现可以对第二行做收缩处理，返回 RET_OK，回到 filterRowCandidatesEx 接口，继续向上级调用返回 RET_OK。

shrinkRowCandidatesP2 接口

 1 u8 CQuizDealer::shrinkRowCandidatesP2(u8* pBlk, u8* pRow, u8 zeroSum, u8 row, u8 colBase)
 2 {
 3     u8 rowBase = row * 9;
 4     for (u8 col = 0; col < 9; ++col) {
 5         if (col >= colBase && col <= colBase + 2)
 6             continue;
 7         if (pRow[col] != 0)
 8             if (!removeVal(pBlk, pRow[col]))
 9                 return RET_PENDING;
10     }
11     if (zeroSum < pBlk[0]) {
12         printf("shrinking row %d with ply2[blk:%d] went WRONG: 0Sum [%d] < vSum [%d]\n", (int)row + 1, (int)colBase / 3 + 1, (int)zeroSum, (int)pBlk[0]);
13         return RET_WRONG;
14     }
15     u8 exVals[7] = {0};
16     if (zeroSum > pBlk[0]) {
17         calcExCols(exVals, pBlk, pRow, rowBase, colBase, false);
18         if (zeroSum - exVals[0] < pBlk[0]) {
19             printf("shrinking row %d with ply2[blk:%d] went WRONG: 0Sum [%d] - xSum [%d] < vSum [%d]\n", (int)row + 1, (int)colBase / 3 + 1, (int)zeroSum, (int)exVals[0], (int)pBlk[0]);
20             return RET_WRONG;
21         }
22         if (zeroSum - exVals[0] > pBlk[0])
23             return RET_PENDING;
24     }
25     u8 ret = RET_PENDING;
26     bool shrunken = false;
27     for (u8 col = 0; col < 9; ++col) {
28         if (pRow[col] != 0 || (col >= colBase && col <= colBase + 2) || inSet(col, exVals))
29             continue;
30         ret = shrinkCandidates(rowBase + col, pBlk);
31         if (ret == RET_WRONG) {
32             printf("shrinking [%d,%d] with row-ply2 went WRONG\n", (int)row + 1, (int)col + 1);
33             return RET_WRONG;
34         }
35         if (ret == RET_OK)
36             shrunken = true;
37     }
38     if (shrunken) {
39         ret = RET_OK;
40         printf("row %d shrunken ply-2 by blk %d\n", (u8)row + 1, (u8)colBase / 3 + 1);
41     }
42     return ret;
43 }

shrinkRowCandidatesP2 接口实现和 shrinkRowCandidatesP1 类似。

filterColCandidatesEx 接口

 1 u8 CQuizDealer::filterColCandidatesEx(u8 col)
 2 {
 3     u8 vals[10] = {0}; // last item denotes sum of zeros
 4     for (u8 row = 0; row < 9; ++row) {
 5         u8 celIdx = row * 9 + col;
 6         vals[row] = m_seqCell[celIdx].val;
 7         if (vals[row] == 0) {
 8             vals[9] += 1;
 9         }
10     }
11     if (vals[9] == 0)
12         return RET_PENDING;
13     u8 blkBase = col / 3;
14     u8 blkTakens[21] = {0};
15     setBlkColTakens(blkBase, col % 3, blkTakens);
16     if (blkTakens[0] == 0 && blkTakens[7] == 0 && blkTakens[14] == 0)
17         return RET_PENDING;
18     u8 ret = RET_PENDING;
19     for (u8 idx = 0; idx < 3; ++idx) {
20         if (ret = filterColByPolicy1(col, idx, vals, blkTakens))
21             return ret;
22     }
23     for (u8 idx = 0; idx < 3; ++idx) {
24         if (ret = filterColByPolicy2(col, idx, vals, blkTakens))
25             return ret;
26     }
27     return RET_PENDING;
28 }

filterColCandidatesEx 接口实现和 filterRowCandidatesEx 接口的实现实质是一样的，相当于对 9×9 方阵旋转 90 度后做一次 filterRowCandidatesEx。

setBlkColTakens 和 setColTakensInBlk 接口

 1 void CQuizDealer::setBlkColTakens(u8 blkBase, u8 innCol, u8* pTakens)
 2 {
 3     for (u8 idx = 0; idx < 3; ++idx) {
 4         u8 blk = blkBase + idx * 3;
 5         u8* pVals = pTakens + idx * 7;
 6         u8 rowBase = idx * 27;
 7         u8 col = block2col(blk, (innCol + 1) % 3);
 8         setColTakensInBlk(col, rowBase, pVals);
 9         col = block2col(blk, (innCol + 2) % 3);
10         setColTakensInBlk(col, rowBase, pVals);
11     }
12 }

 1 void CQuizDealer::setColTakensInBlk(u8 col, u8 rowBase, u8* pVals)
 2 {
 3     for (u8 idx = rowBase; idx < rowBase + 27; idx += 9) {
 4         u8 val = m_seqCell[idx + col].val;
 5         if (val != 0) {
 6             u8 sum = pVals[0] + 1;
 7             pVals[sum] = val;
 8             pVals[0] = sum;
 9         }
10     }
11 }

filterColByPolicy1 和 shrinkColCandidatesP1 接口

 1 u8 CQuizDealer::filterColByPolicy1(u8 col, u8 idx, u8* pVals, u8* pBlkTakens)
 2 {
 3     u8 segRowBase = idx * 3;
 4     u8 v1 = pVals[segRowBase], v2 = pVals[segRowBase + 1], v3 = pVals[segRowBase + 2];
 5     u8 zeroSum = (u8)(v1 == 0) + (u8)(v2 == 0) + (u8)(v3 == 0);
 6     if (zeroSum == 0)
 7         return 0;
 8     u8 isVals[7] = {0};
 9     if (idx == 0)
10         intersection(pBlkTakens + 7, pBlkTakens + 14, isVals);
11     else if (idx == 1)
12         intersection(pBlkTakens, pBlkTakens + 14, isVals);
13     else
14         intersection(pBlkTakens, pBlkTakens + 7, isVals);
15     if (isVals[0] == 0)
16         return RET_PENDING;
17     return shrinkColCandidatesP1(isVals, pVals, zeroSum, col, segRowBase);
18 }

 1 u8 CQuizDealer::shrinkColCandidatesP1(u8* pBlk, u8* pCol, u8 zeroSum, u8 col, u8 segRowBase)
 2 {
 3     for (u8 idx = segRowBase; idx < segRowBase + 3; ++idx) {
 4         if (pCol[idx] != 0)
 5             if (!removeVal(pBlk, pCol[idx]))
 6                 return RET_PENDING;
 7     }
 8     if (zeroSum < pBlk[0]) {
 9         printf("shrinking col %d with ply1[vblk:%d] went WRONG: 0Sum [%d] < vSum [%d]\n", (int)col + 1, (int)segRowBase / 3 + 1, (int)zeroSum, (int)pBlk[0]);
10         return RET_WRONG;
11     }
12     u8 exVals[4] = {0};
13     if (zeroSum > pBlk[0]) {
14         calcExRows(exVals, pBlk, pCol, col, segRowBase, true);
15         if (zeroSum - exVals[0] < pBlk[0]) {
16             printf("shrinking col %d with ply1[vblk:%d] went WRONG: 0Sum [%d] - xSum [%d] < vSum [%d]\n", (int)col + 1, (int)segRowBase / 3 + 1, (int)zeroSum, (int)exVals[0], (int)pBlk[0]);
17             return RET_WRONG;
18         }
19         if (zeroSum - exVals[0] > pBlk[0])
20             return RET_PENDING;
21     }
22     u8 ret = RET_PENDING;
23     bool shrunken = false;
24     for (u8 row = segRowBase; row < segRowBase + 3; ++row) {
25         if (pCol[row] != 0 || inSet(row, exVals))
26             continue;
27         ret = shrinkCandidates(row * 9 + col, pBlk);
28         if (ret == RET_WRONG) {
29             printf("shrinking [%d,%d] with col-ply1 went WRONG\n", (int)row + 1, (int)col + 1);
30             return RET_WRONG;
31         }
32         if (ret == RET_OK)
33             shrunken = true;
34     }
35     if (shrunken) {
36         ret = RET_OK;
37         printf("col %d shrunken ply-1 by vblk %d\n", (u8)col + 1, (u8)segRowBase / 3 + 1);
38     }
39     return ret;
40 }

filterColByPolicy2 和 shrinkColCandidatesP2 接口

 1 u8 CQuizDealer::filterColByPolicy2(u8 col, u8 idx, u8* pVals, u8* pBlkTakens)
 2 {
 3     u8 segRowBase = idx * 3;
 4     u8 v1 = pVals[segRowBase], v2 = pVals[segRowBase + 1], v3 = pVals[segRowBase + 2];
 5     u8 zeroSum = pVals[9] - (u8)(v1 == 0) - (u8)(v2 == 0) - (u8)(v3 == 0);
 6     if (zeroSum == 0)
 7         return 0;
 8     u8* pBlk = pBlkTakens + (idx * 7);
 9     if (pBlk[0] == 0)
10         return RET_PENDING;
11     return shrinkColCandidatesP2(pBlk, pVals, zeroSum, col, segRowBase);
12 }

 1 u8 CQuizDealer::shrinkColCandidatesP2(u8* pBlk, u8* pCol, u8 zeroSum, u8 col, u8 segRowBase)
 2 {
 3     for (u8 row = 0; row < 9; ++row) {
 4         if (row >= segRowBase && row <= segRowBase + 2)
 5             continue;
 6         if (pCol[row] != 0)
 7             if (!removeVal(pBlk, pCol[row]))
 8                 return RET_PENDING;
 9     }
10     if (zeroSum < pBlk[0]) {
11         printf("shrinking col %d with ply2[vblk:%d] went WRONG: 0Sum [%d] < vSum [%d]\n", (int)col + 1, (int)segRowBase / 3 + 1, (int)zeroSum, (int)pBlk[0]);
12         return RET_WRONG;
13     }
14     u8 exVals[7] = {0};
15     if (zeroSum > pBlk[0]) {
16         calcExRows(exVals, pBlk, pCol, col, segRowBase, false);
17         if (zeroSum - exVals[0] < pBlk[0]) {
18             printf("shrinking col %d with ply2[vblk:%d] went WRONG: 0Sum [%d] - xSum [%d] < vSum [%d]\n", (int)col + 1, (int)segRowBase / 3 + 1, (int)zeroSum, (int)exVals[0], (int)pBlk[0]);
19             return RET_WRONG;
20         }
21         if (zeroSum - exVals[0] > pBlk[0])
22             return RET_PENDING;
23     }
24     u8 ret = 0;
25     bool shrunken = false;
26     for (u8 row = 0; row < 9; ++row) {
27         if (pCol[row] != 0 || (row >= segRowBase && row <= segRowBase + 2) || inSet(row, exVals))
28             continue;
29         ret = shrinkCandidates(row * 9 + col, pBlk);
30         if (ret == RET_WRONG) {
31             printf("shrinking [%d,%d] with col-ply2 went wrong\n", (int)row + 1, (int)col + 1);
32             return RET_WRONG;
33         }
34         if (ret == RET_OK)
35             shrunken = true;
36     }
37     if (shrunken) {
38         ret = RET_OK;
39         printf("col %d shrunken ply-2 by vblk %d\n", (u8)col + 1, (u8)segRowBase / 3 + 1);
40     }
41     return ret;
42 }

calcExRows 接口

 1 void CQuizDealer::calcExRows(u8* pEx, u8* pBlk, u8* pCol, u8 col, u8 segRowBase, bool ply1)
 2 {
 3     u8 lower = (ply1 ? segRowBase : 0);
 4     u8 upper = (ply1 ? segRowBase + 3 : 9);
 5     for (u8 row = lower; row < upper; ++row) {
 6         if (ply1) {
 7             if (pCol[row] != 0)
 8                 continue;
 9         }
10         else {
11             if (pCol[row] != 0 || (row >= segRowBase && row <= segRowBase + 2))
12                 continue;
13         }
14         u8 vals[10] = {0};
15         intersection(m_seqCell[row * 9 + col].candidates, pBlk, vals);
16         if (vals[0] == 0) {
17             u8 sum = pEx[0] + 1;
18             pEx[sum] = row;
19             pEx[0] = sum;
20         }
21     }
22 }

其他细微代码修改

printCandidates 函数

去掉了末尾的一行语句，即 printf("\n");

showQuiz 接口

 1 void CQuizDealer::showQuiz()
 2 {
 3     ...
    printf("\nSteps:%u\nCandidates:\n", m_steps);
31     u8 count = 1;
32     u8 foremost = 0;
33     for (std::set<u8>::iterator it = m_setBlank.begin(); it != m_setBlank.end(); ++it, ++count) {
34         u8 pos = *it;
35         u8* pVals = m_seqCell[pos].candidates;
36         if (foremost == 0 && pVals[0] == 1)
37             foremost = pos;
38         printCandidates(pos, pVals);
39         if (count % 3 == 0)
40             printf("\n");
41         else
42             printf("    ");
43     }
44     if (count % 3 != 1)
45         printf("\n");
46     if (foremost != 0)
47         printf("The foremost cell with one candidate at [%d,%d]\n", (int)(foremost / 9 + 1), (int)(foremost % 9 + 1));
48     if (m_guessLevel != 0)
49         printf("\nAt guess level %d [%d,%d] %d\n", (int)m_guessLevel, (int)(m_guessPos / 9 + 1), (int)(m_guessPos % 9 + 1), (int)m_guessValPos);
50 }

parse 和 guess 接口

开头增加一条语句：++m_steps;

nextGuess 接口

 1 void CQuizDealer::nextGuess()
 2 {
 3     ...
    ++m_steps;
12     Snapshot* pTop = m_stkSnap.top();
13     ...

step 接口

去掉语句：nextGuess(); 之后的一条语句：m_steps++;

showOrderList 函数

// Sudoku Solver 1.0 2021/9/20
#define STR_VER "Sudoku Solver 1.1 2021/10/2 by readalps\n\n"

void showOrderList()
{
    printf(STR_VER);
    ...
}

进一步的实例分析放到下一篇。

这篇关于SudokuSolver 1.1：用C++实现的数独解题程序【二】的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

C/C++教程