我正在用C++编写数独求解器,在编写过程中遇到了一些问题。下面是我的解决方案代码。它可以解决数独谜题的前三行,但在第四行结束时就会出现递归失效。使用gdb调试代码后,发现程序已经到达了第四行的结尾,然后回溯到第六列,进行尝试,但最终还是递归失败退出了。
代码中有几个注意事项,存储数独板块的矩阵从(1, 1)处开始,而不是从(0, 0)处开始。因此,当首次调用solveBoard时,参数为(1, 1, 0)。我还附加了setCell和checkConflicts函数,以便更好地了解代码情况。我有三个向量rowConf、colConf和squConf,用于存储已放置在相应行、列或九宫格中的值。我已经呆了几个小时,无法让程序通过第三行。非常感谢您提供帮助!谢谢!
编辑:添加了clearCell()
代码中有几个注意事项,存储数独板块的矩阵从(1, 1)处开始,而不是从(0, 0)处开始。因此,当首次调用solveBoard时,参数为(1, 1, 0)。我还附加了setCell和checkConflicts函数,以便更好地了解代码情况。我有三个向量rowConf、colConf和squConf,用于存储已放置在相应行、列或九宫格中的值。我已经呆了几个小时,无法让程序通过第三行。非常感谢您提供帮助!谢谢!
编辑:添加了clearCell()
bool board::solveBoard(int i, int j, int count)
{
if (j > 9)
{
j = 1;
i++;
printBoard();
if (isSolved())
{
printBoard();
cout <<"The Board has been solved!" <<endl
<<" The number of recursive calls was: " <<count <<endl;
return true;
}
}
if (isBlank(i, j))
{
for (int n = 1; n < 10; n++)
{
if (setCell(i, j, (char)n + '0'))
{
if (solveBoard(i, j + 1, count + 1))
{
return true;
}
}
}
}
else
{
return (solveBoard(i, j + 1, count + 1));
}
clearCell(i, j);
return false;
}
bool board::setCell(int i, int j, char val)
{
int intVal;
intVal = atoi(&val);
if (i >= 1 && i <= BoardSize && j >= 1 && j <= BoardSize &&
intVal >= 1 && intVal <= BoardSize)
{
if (!(checkConflicts(intVal, i, j, squareNumber(i, j))))
{
return false;
}
value[i][j] = intVal;
// Set flags of the conflicts
rowConf[i][intVal] = true;
colConf[j][intVal] = true;
squConf[squareNumber(i, j)][intVal] = true;
return true;
}
else
{
throw rangeError("bad value in setCell");
}
}
bool board::checkConflicts(int val, int i, int j, int k)
{
if (i < 1 && i > BoardSize && j < 1 && j > BoardSize &&
k < 1 && k > BoardSize && val < 1 && val > BoardSize)
{
throw rangeError("bad value in checkConflicts()");
}
if (rowConf[i][val] || colConf[j][val] || squConf[k][val])
{
return false;
}
else
{
return true;
}
}
Initial Board:
-----------------------------
| 3 | 8 | -----------------------------
| | 7 | 5 -----------------------------
| 1 | | -----------------------------
-----------------------------
| | | 3 6 -----------------------------
| 2 | 4 | -----------------------------
| 7 | | -----------------------------
-----------------------------
| | 6 | 1 3 -----------------------------
| 4 5 | 2 | -----------------------------
| | | 8 -----------------------------
-----------------------------
Final Output:
-----------------------------
| 3 2 4 | 1 8 5 | 6 7 9 -----------------------------
| 6 8 9 | 7 2 3 | 4 1 5 -----------------------------
| 1 5 7 | 4 9 6 | 2 8 3 -----------------------------
-----------------------------
| | | 3 6 -----------------------------
| 2 | 4 | -----------------------------
| 7 | | -----------------------------
-----------------------------
| | 6 | 1 3 -----------------------------
| 4 5 | 2 | -----------------------------
| | | 8 -----------------------------
-----------------------------
void board::clearCell(int i, int j)
{
int intVal;
if (i >= 1 && i <= BoardSize && j >= 1 && j <= BoardSize)
{
if (value[i][j] != -1)
{
intVal = value[i][j];
rowConf[i][intVal] = false;
colConf[j][intVal] = false;
squConf[squareNumber(i, j)][intVal] = false;
value[i][j] = -1;
}
}
else
{
throw rangeError("bad value in setCell");
}
}
clearCell
函数。 - phant0m