[C ++ Sudoku Solver使用递归回溯不起作用

Question

我正在尝试使用递归和回溯编码数独求解器。但是我的代码总是返回false。 SudokuSolver（）仅遍历第一行到第四列，然后停止并开始回溯。问题在于回溯将持续到第一个单元格，最后返回false。结果，没有任何空单元格（值为“ -1”的单元格）被任何其他数字（1-9）替换，并且面板保持原样。

编译器显示[Done]在0.557秒内以代码= 0退出

#include<iostream>
using namespace std;
# define N 9

bool SolveSudoku();
pair<int,int> FindUnassigned();
void PrintBoard();
bool NoConflict(int, int, int);
bool inRow(int,int);
bool inCol(int, int);
bool inGrid(int, int, int);
bool isFilled(pair<int,int>);

//board[row][col]==-1 indicates an empty position

int board[N][N] = {{3,-1,6,5,-1,8,4,-1,-1},
                   {5,2,-1,-1,-1,-1,-1,-1,-1},
                   {-1,5,7,-1,-1,-1,-1,3,1},
                   {-1,-1,3,-1,1,-1,-1,8,-1},
                   {9,-1,-1,8,6,3,-1,-1,5},
                   {-1,5,-1,-1,9,-1,6,-1,-1},
                   {1,3,-1,-1,-1,-1,2,5,-1},
                   {-1,-1,-1,-1,-1,-1,-1,7,4},
                   {-1,-1,5,2,-1,6,3,-1,-1}};


int main() {
    if(SolveSudoku()) 
        PrintBoard();
    return 0;
}


bool SolveSudoku() {
    pair<int,int> pos = FindUnassigned();
    int row=pos.first;
    int col=pos.second;
    if(isFilled(pos)) { return true; }
      for(int num=1; num<=9; num++) {
        if(NoConflict(num,row,col)) {
            board[row][col]=num;
            SolveSudoku();
            board[row][col]=-1;
        }  
      }
    return false;
}

pair<int,int> FindUnassigned() {
    pair<int,int> pos;
    pos.first=-1;
    pos.second=-1;
    for(int r=0; r<N; r++) {
        for(int c=0; c<N; c++) {
            if(board[r][c]==-1) {
                pos.first=r;
                pos.second=c;
                return pos;
            } 
        }
    }
    return pos;
}

bool isFilled(pair<int,int> pos) {
    return (pos.first==-1 && pos.second==-1);
}

bool NoConflict(int num, int r, int c) {
    return ((!inRow(numenter code here,r)==false) && (!inCol(num,c)==false) && (!inGrid(num,r-r%3,c-c%3)==false));
}

bool inRow(int num, int r) {
    for(int c=0; c<N; c++) {
        if(board[r][c]==num) return true;
    }
    return false;
}

bool inCol(int num, int c) {
    for(int r=0; r<N; r++) {
        if(board[r][c]==num) return true;
    }
    return false;
}

bool inGrid(int num, int rf, int cf) {
    for(int r=0; r<3; r++) {
        for(int c=0; c<3; c++) {
            if(board[r+rf][c+cf]==num) return true;
        }
    }
    return false;
}

void PrintBoard() {
    for(int r=0; r<N; r++) {
        for(int c=0; c<N; c++) {
            cout<<board[r][c]<<"\t";
        }
 enter code here       cout<<endl;
    }
}

Answer 1

递归函数的工作方式与非递归函数完全相同。（这是了解递归最重要的事情。）

这里：

board[row][col]=num;
SolveSudoku();
board[row][col]=-1;

您忽略函数调用的结果，因此您将递归进行操作，直到木板被填满，然后完全回溯，最后是return false;。

您可能想要的是（未经测试）：

if (SolveSudoku())
{
    return true;
}

NoConflict中还存在一个错误，等同于

bool NoConflict(int num, int r, int c) {
    return inRow(num,r) && inCol(num,c) && inGrid(num,r-r%3,c-c%3);
}

即，并且仅当num已存在于行，列和网格中时，才没有冲突。 [您可能是说num不应在任何地方找到：

bool NoConflict(int num, int r, int c) {
    return !inRow(num,r) && !inCol(num,c) && !inGrid(num,r-r%3,c-c%3);
}

可能有比这更多的错误。