数独求解器程序
Sudoku Solver Program
solveSudoku 函数从 main() 函数调用。
我写了以下函数来解决数独问题：
#include <iostream>
#include <vector>
using namespace std;
int isvalid(char k, vector<vector<char> > A, int i, int j) { //Checking if putting the current element is not in same row, column or box
for(int t = 0; t < 9; t++) {
if(A[t][j] == k) //Checking jth column
return 0;
if(A[i][t] == k) //Checking ith row
return 0;
if(A[(i/3)*3+t/3][(j/3)*3+t%3] == k) //Checking current box
return 0;
}
return 1;
}
bool sudoku(vector<vector<char> > &A, int i, int j) {
if(i > 8 || j > 8) //If coordinates of the matrix goes out of bounds return true
return true;
if(A[i][j] == '.') {
for(char k = '1'; k <= '9'; k++) { //Trying to put every character possible
if(isvalid(k, A, i, j)) { //If putting character `k` doesn't makes the sudoku invaild put it
A[i][j] = k;
if(sudoku(A, i+1, j) && sudoku(A, i, j+1) && sudoku(A, i+1, j+1))//Check further if the sudoku can be solved with that configuration by going to the right block, down block and bottom-right block
return true;
else
A[i][j] = '.'; //Reset(If the sudoku can't be solved with putting `k` in `i, j` th index replace the '.' character at that position)
}
}
}
else {
if(sudoku(A, i+1, j) && sudoku(A, i, j+1) && sudoku(A, i+1, j+1))
return true;
}
return false;//This should trigger backtracking
}
void solveSudoku(vector<vector<char> > &A) {
sudoku(A, 0, 0);
}
int main() {
vector<vector<char> > A = {{'5','3','.','.','7','.','.','.','.'}, {'6','.','.','1','9','5','.','.','.'}, {'.','9','8','.','.','.','.','6','.'},
{'8','.','.','.','6','.','.','.','3'}, {'4','.','.','8','.','3','.','.','1'}, {'7','.','.','.','2','.','.','.','6'},
{'.','6','.','.','.','.','2','8','.'}, {'.','.','.','4','1','9','.','.','5'}, {'.','.','.','.','8','.','.','7','9'}}; //Input sudoku
solveSudoku(A);
for(int i = 0; i < 9; i++) {
for(int j = 0; j < 9; j++) {
cout<<A[i][j]<<" ";
}
cout<<"\n";
}
return 0;
}
输出
5 3 . . 7 . . . .
6 . . 1 9 5 . . .
. 9 8 . . . . 6 .
8 . . . 6 . . . 3
4 . . 8 . 3 . . 1
7 . . . 2 . . . 6
. 6 . . . . 2 8 .
. . . 4 1 9 . . 5
3 1 4 5 8 2 6 7 9
预期输出
5 3 4 6 7 8 9 1 2
6 7 2 1 9 5 3 4 8
1 9 8 3 4 2 5 6 7
8 5 9 7 6 1 4 2 3
4 2 6 8 5 3 7 9 1
7 1 3 9 2 4 8 5 6
9 6 1 5 3 7 2 8 4
2 8 7 4 1 9 6 3 5
3 4 5 2 8 6 1 7 9
当在 main() 函数中调用 solveSudoku 时，输入数独作为参数给出。它由1到9的字符和代表空字符的.组成。 solveSudoku 函数的工作是正确填充数独中的所有元素（更改 A 中的值）。但我得到错误的答案。假设给出的输入数独是可解的
正如 Fezvez 所说，我也认为我的算法中的问题在于此语句 if(sudoku(A, i+1, j) && sudoku(A, i, j+1) && sudoku(A, i+1, j+1))。我认为在用有效字符填充单元格后，此语句应递归检查右侧、下方和对角线上的块是否也被填充。如果是，则数独已解决，它应该 return true 但如果三个中的任何一个失败，它应该回溯。但是为什么不这样做呢？
你需要一个堆栈。然后你需要穷举1-9，如果都无效就放松。如果全部无效，则需要继续上一关，如果1-9全部无效，则重新展开。
但这是一个无望的算法。虽然它最终会用于一个简单的数独游戏，但它的执行时间太长了。
重做答案 : sudoku(A, i, j) 有在 A 中写入数据的副作用。
当您调用 if(sudoku(A, i+1, j) && sudoku(A, i, j+1) && sudoku(A, i+1, j+1)) 并点击第二个检查 sudoku(A, i, j+1) 时，它不再是原来的 A 并且您没有在测试您的想法。我通过更改 if 出现的两行并只进行一次检查来修复它：sudoku(A, (i+1)%9, j+(i+1)/9)
旧答案：您的代码失败，因为 sudoku 的行为与您想象的不同。您应该通过深度优先搜索探索进行回溯。但是你没有这样做：if(sudoku(A, i+1, j) && sudoku(A, i, j+1) && sudoku(A, i+1, j+1)) 既不是 BFS 也不是 DFS，它会使你的算法失败
这是一个稍微修改过的版本，我用 sudoku(A, (i+1)%9, j+(i+1)/9) 替换了有问题的部分并且它有效。
编辑：if(sudoku(A, i+1, j) && sudoku(A, i, j+1) && sudoku(A, i+1, j+1)) 是违规者，原因如下：
如果从 (i,j) 到右下角的任何矩形包含有效填充，则 sudoku(A, i, j) 为真。也就是说，您可以输入数字，它们不会违反数独规则。确实，您要计算的是 sudoku(A,0,0)- 但我将举一个失败的例子：假设您正在计算
if(sudoku(A,1,0) && sudoku(A,0,1) && sudoku(A,1,1))。您从 sudoku(A, 1, 0) 和 returns 开始。您现在已经填充了几乎所有的 A（顶行除外）。你继续计算 sudoku(A,0,1) 但如果你之前几乎完成的填充实际上是无效的（没有办法填充第一行）你的算法立即失败
- 换句话说，您的代码失败是因为调用
sudoku(A, i, j) 有副作用（在 A 中写入数据），并且当您在 if 中点击第三个布尔值的第二个时，您没有处理正确的 A
这是使用您的示例更新的代码
#include <iostream>
#include <vector>
using namespace std;
int isvalid(char k, vector<vector<char> > A, int i, int j) { //Checking if putting the current element is not in same row, column or box
for(int t = 0; t < 9; t++) {
if(A[t][j] == k) //Checking jth column
return 0;
if(A[i][t] == k) //Checking ith row
return 0;
if(A[(i/3)*3+t/3][(j/3)*3+t%3] == k) //Checking current box
return 0;
}
return 1;
}
bool sudoku(vector<vector<char> > &A, int i, int j) {
if(i > 8 || j > 8) //If coordinates of the matrix goes out of bounds return true
return true;
if(A[i][j] == '.') {
for(char k = '1'; k <= '9'; k++) { //Trying to put every character possible
if(isvalid(k, A, i, j)) { //If putting character `k` doesn't makes the sudoku invaild put it
A[i][j] = k;
if(sudoku(A, (i+1)%9, j+(i+1)/9))// CHANGE ONE
return true;
else
A[i][j] = '.'; //Reset(If the sudoku can't be solved with putting `k` in `i, j` th index replace the '.' character at that position)
}
}
}
else {
if(sudoku(A, (i+1)%9, j+(i+1)/9)) // CHANGE TWO
return true;
}
return false;//This should trigger backtracking
}
void solveSudoku(vector<vector<char> > &A) {
sudoku(A, 0, 0);
}
int main() {
vector<vector<char> > A = {{'5','3','.','.','7','.','.','.','.'}, {'6','.','.','1','9','5','.','.','.'}, {'.','9','8','.','.','.','.','6','.'},
{'8','.','.','.','6','.','.','.','3'}, {'4','.','.','8','.','3','.','.','1'}, {'7','.','.','.','2','.','.','.','6'},
{'.','6','.','.','.','.','2','8','.'}, {'.','.','.','4','1','9','.','.','5'}, {'.','.','.','.','8','.','.','7','9'}}; //Input sudoku
solveSudoku(A);
for(int i = 0; i < 9; i++) {
for(int j = 0; j < 9; j++) {
cout<<A[i][j]<<" ";
}
cout<<"\n";
}
return 0;
}
输出
5 3 4 6 7 8 9 1 2
6 7 2 1 9 5 3 4 8
1 9 8 3 4 2 5 6 7
8 5 9 7 6 1 4 2 3
4 2 6 8 5 3 7 9 1
7 1 3 9 2 4 8 5 6
9 6 1 5 3 7 2 8 4
2 8 7 4 1 9 6 3 5
3 4 5 2 8 6 1 7 9
我重写了您的代码并替换了一些内容以使其更易于调试。它看起来不像典型的递归函数，因为只有一个参数作为引用传递，但它确实是，因为它使用 y、x 和 k 的堆栈。 （更正）
这是修改后的函数：
bool sudoku(vector<vector<char> > &A)
{
//Test full sudoku field to see if all fields can be filled with valid numbers:
for (int y = 0; y < 9; y++)
{
for (int x = 0; x < 9; x++)
{
if (A[x][y] == '.') //Startpoint to find a valid replacement:
{
for (char k = '1'; k <= '9'; k++)//At least one character has to be possible
{
if (isvalid(k, A, x, y)) //If putting character `k` doesn't makes the sudoku invaild put it in:
{
A[x][y] = k;
//Try solving sudoku with new value:
if (sudoku(A))
return true;
}
}
//Reset to unsolved:
A[x][y] = '.';
return false;
}
}
}
//Reachable, if all fields are filled. [Corrected]
//Assumption: Initialized with a valid field.
//So a valid start field + valid adds ->always valid filled field
//Otherwise you will have to test the complete field here.
return true;
}
输出为：
我很确定你的问题是这段代码：
if(sudoku(A, i+1, j) && sudoku(A, i, j+1) && sudoku(A, i+1, j+1))//Check further if the sudoku can be solved with that configuration by going to the right block, down block and bottom-right block
return true;
如果您查看您的输出和您想要的输出，您会发现底线是唯一完全填充的。这是反馈条件损坏的指示器，但很难调试。这就是为什么我选择大量重写并删除不必要的代码。
solveSudoku 函数从 main() 函数调用。
我写了以下函数来解决数独问题：
#include <iostream>
#include <vector>
using namespace std;
int isvalid(char k, vector<vector<char> > A, int i, int j) { //Checking if putting the current element is not in same row, column or box
for(int t = 0; t < 9; t++) {
if(A[t][j] == k) //Checking jth column
return 0;
if(A[i][t] == k) //Checking ith row
return 0;
if(A[(i/3)*3+t/3][(j/3)*3+t%3] == k) //Checking current box
return 0;
}
return 1;
}
bool sudoku(vector<vector<char> > &A, int i, int j) {
if(i > 8 || j > 8) //If coordinates of the matrix goes out of bounds return true
return true;
if(A[i][j] == '.') {
for(char k = '1'; k <= '9'; k++) { //Trying to put every character possible
if(isvalid(k, A, i, j)) { //If putting character `k` doesn't makes the sudoku invaild put it
A[i][j] = k;
if(sudoku(A, i+1, j) && sudoku(A, i, j+1) && sudoku(A, i+1, j+1))//Check further if the sudoku can be solved with that configuration by going to the right block, down block and bottom-right block
return true;
else
A[i][j] = '.'; //Reset(If the sudoku can't be solved with putting `k` in `i, j` th index replace the '.' character at that position)
}
}
}
else {
if(sudoku(A, i+1, j) && sudoku(A, i, j+1) && sudoku(A, i+1, j+1))
return true;
}
return false;//This should trigger backtracking
}
void solveSudoku(vector<vector<char> > &A) {
sudoku(A, 0, 0);
}
int main() {
vector<vector<char> > A = {{'5','3','.','.','7','.','.','.','.'}, {'6','.','.','1','9','5','.','.','.'}, {'.','9','8','.','.','.','.','6','.'},
{'8','.','.','.','6','.','.','.','3'}, {'4','.','.','8','.','3','.','.','1'}, {'7','.','.','.','2','.','.','.','6'},
{'.','6','.','.','.','.','2','8','.'}, {'.','.','.','4','1','9','.','.','5'}, {'.','.','.','.','8','.','.','7','9'}}; //Input sudoku
solveSudoku(A);
for(int i = 0; i < 9; i++) {
for(int j = 0; j < 9; j++) {
cout<<A[i][j]<<" ";
}
cout<<"\n";
}
return 0;
}
输出
5 3 . . 7 . . . .
6 . . 1 9 5 . . .
. 9 8 . . . . 6 .
8 . . . 6 . . . 3
4 . . 8 . 3 . . 1
7 . . . 2 . . . 6
. 6 . . . . 2 8 .
. . . 4 1 9 . . 5
3 1 4 5 8 2 6 7 9
预期输出
5 3 4 6 7 8 9 1 2
6 7 2 1 9 5 3 4 8
1 9 8 3 4 2 5 6 7
8 5 9 7 6 1 4 2 3
4 2 6 8 5 3 7 9 1
7 1 3 9 2 4 8 5 6
9 6 1 5 3 7 2 8 4
2 8 7 4 1 9 6 3 5
3 4 5 2 8 6 1 7 9
当在 main() 函数中调用 solveSudoku 时，输入数独作为参数给出。它由1到9的字符和代表空字符的.组成。 solveSudoku 函数的工作是正确填充数独中的所有元素（更改 A 中的值）。但我得到错误的答案。假设给出的输入数独是可解的
正如 Fezvez 所说，我也认为我的算法中的问题在于此语句 if(sudoku(A, i+1, j) && sudoku(A, i, j+1) && sudoku(A, i+1, j+1))。我认为在用有效字符填充单元格后，此语句应递归检查右侧、下方和对角线上的块是否也被填充。如果是，则数独已解决，它应该 return true 但如果三个中的任何一个失败，它应该回溯。但是为什么不这样做呢？
你需要一个堆栈。然后你需要穷举1-9，如果都无效就放松。如果全部无效，则需要继续上一关，如果1-9全部无效，则重新展开。
但这是一个无望的算法。虽然它最终会用于一个简单的数独游戏，但它的执行时间太长了。
重做答案 : sudoku(A, i, j) 有在 A 中写入数据的副作用。
当您调用 if(sudoku(A, i+1, j) && sudoku(A, i, j+1) && sudoku(A, i+1, j+1)) 并点击第二个检查 sudoku(A, i, j+1) 时，它不再是原来的 A 并且您没有在测试您的想法。我通过更改 if 出现的两行并只进行一次检查来修复它：sudoku(A, (i+1)%9, j+(i+1)/9)
旧答案：您的代码失败，因为 sudoku 的行为与您想象的不同。您应该通过深度优先搜索探索进行回溯。但是你没有这样做：if(sudoku(A, i+1, j) && sudoku(A, i, j+1) && sudoku(A, i+1, j+1)) 既不是 BFS 也不是 DFS，它会使你的算法失败
这是一个稍微修改过的版本，我用 sudoku(A, (i+1)%9, j+(i+1)/9) 替换了有问题的部分并且它有效。
编辑：if(sudoku(A, i+1, j) && sudoku(A, i, j+1) && sudoku(A, i+1, j+1)) 是违规者，原因如下：
-
如果从 (i,j) 到右下角的任何矩形包含有效填充，则
sudoku(A, i, j)为真。也就是说，您可以输入数字，它们不会违反数独规则。确实，您要计算的是sudoku(A,0,0)- 但我将举一个失败的例子：假设您正在计算
if(sudoku(A,1,0) && sudoku(A,0,1) && sudoku(A,1,1))。您从sudoku(A, 1, 0)和 returns 开始。您现在已经填充了几乎所有的 A（顶行除外）。你继续计算sudoku(A,0,1)但如果你之前几乎完成的填充实际上是无效的（没有办法填充第一行）你的算法立即失败 - 换句话说，您的代码失败是因为调用
sudoku(A, i, j)有副作用（在 A 中写入数据），并且当您在if中点击第三个布尔值的第二个时，您没有处理正确的A
这是使用您的示例更新的代码
#include <iostream>
#include <vector>
using namespace std;
int isvalid(char k, vector<vector<char> > A, int i, int j) { //Checking if putting the current element is not in same row, column or box
for(int t = 0; t < 9; t++) {
if(A[t][j] == k) //Checking jth column
return 0;
if(A[i][t] == k) //Checking ith row
return 0;
if(A[(i/3)*3+t/3][(j/3)*3+t%3] == k) //Checking current box
return 0;
}
return 1;
}
bool sudoku(vector<vector<char> > &A, int i, int j) {
if(i > 8 || j > 8) //If coordinates of the matrix goes out of bounds return true
return true;
if(A[i][j] == '.') {
for(char k = '1'; k <= '9'; k++) { //Trying to put every character possible
if(isvalid(k, A, i, j)) { //If putting character `k` doesn't makes the sudoku invaild put it
A[i][j] = k;
if(sudoku(A, (i+1)%9, j+(i+1)/9))// CHANGE ONE
return true;
else
A[i][j] = '.'; //Reset(If the sudoku can't be solved with putting `k` in `i, j` th index replace the '.' character at that position)
}
}
}
else {
if(sudoku(A, (i+1)%9, j+(i+1)/9)) // CHANGE TWO
return true;
}
return false;//This should trigger backtracking
}
void solveSudoku(vector<vector<char> > &A) {
sudoku(A, 0, 0);
}
int main() {
vector<vector<char> > A = {{'5','3','.','.','7','.','.','.','.'}, {'6','.','.','1','9','5','.','.','.'}, {'.','9','8','.','.','.','.','6','.'},
{'8','.','.','.','6','.','.','.','3'}, {'4','.','.','8','.','3','.','.','1'}, {'7','.','.','.','2','.','.','.','6'},
{'.','6','.','.','.','.','2','8','.'}, {'.','.','.','4','1','9','.','.','5'}, {'.','.','.','.','8','.','.','7','9'}}; //Input sudoku
solveSudoku(A);
for(int i = 0; i < 9; i++) {
for(int j = 0; j < 9; j++) {
cout<<A[i][j]<<" ";
}
cout<<"\n";
}
return 0;
}
输出
5 3 4 6 7 8 9 1 2
6 7 2 1 9 5 3 4 8
1 9 8 3 4 2 5 6 7
8 5 9 7 6 1 4 2 3
4 2 6 8 5 3 7 9 1
7 1 3 9 2 4 8 5 6
9 6 1 5 3 7 2 8 4
2 8 7 4 1 9 6 3 5
3 4 5 2 8 6 1 7 9
我重写了您的代码并替换了一些内容以使其更易于调试。它看起来不像典型的递归函数，因为只有一个参数作为引用传递，但它确实是，因为它使用 y、x 和 k 的堆栈。 （更正）
这是修改后的函数：
bool sudoku(vector<vector<char> > &A)
{
//Test full sudoku field to see if all fields can be filled with valid numbers:
for (int y = 0; y < 9; y++)
{
for (int x = 0; x < 9; x++)
{
if (A[x][y] == '.') //Startpoint to find a valid replacement:
{
for (char k = '1'; k <= '9'; k++)//At least one character has to be possible
{
if (isvalid(k, A, x, y)) //If putting character `k` doesn't makes the sudoku invaild put it in:
{
A[x][y] = k;
//Try solving sudoku with new value:
if (sudoku(A))
return true;
}
}
//Reset to unsolved:
A[x][y] = '.';
return false;
}
}
}
//Reachable, if all fields are filled. [Corrected]
//Assumption: Initialized with a valid field.
//So a valid start field + valid adds ->always valid filled field
//Otherwise you will have to test the complete field here.
return true;
}
输出为：
我很确定你的问题是这段代码：
if(sudoku(A, i+1, j) && sudoku(A, i, j+1) && sudoku(A, i+1, j+1))//Check further if the sudoku can be solved with that configuration by going to the right block, down block and bottom-right block
return true;
如果您查看您的输出和您想要的输出，您会发现底线是唯一完全填充的。这是反馈条件损坏的指示器，但很难调试。这就是为什么我选择大量重写并删除不必要的代码。