用回溯法解决数独问题 - C++

Question

所以我正在尝试用回溯法解决数独问题

在这个例子中： example_pic

我用 webSudoku 给定的位置上的数字对二维数组中的一些索引进行了硬编码（上图）。它肯定有解决方案但是，我的代码打印“解决方案不存在

这是我的代码：

#include <stdio.h>
int a[10][10]= {{2,0,0,0,9,0,0,3,1},
            {0,0,3,5,0,6,0,2,0},
            {0,0,8,1,3,0,5,4,0},
            {7,2,0,0,0,9,0,0,4},
            {4,0,0,0,0,0,0,0,8},
            {3,0,0,6,0,0,0,9,5},
            {0,7,6,0,4,5,1,0,0},
            {0,1,0,9,0,7,4,0,0},
            {5,3,0,0,8,0,0,0,6}};

bool is_valid(int x, int y, int value){
    if(a[x][y] != 0) return false;

    //check_row and column
    for(int tmp=1; tmp<=9; tmp++){
        if(value == a[x][tmp]) return false;
    }
    for(int tmp=1; tmp<=9; tmp++){
        if(value == a[tmp][y]) return false;
    }
    //check in 3*3 block
    int x_s = (x-1)/3*3 + 1;
    int y_s = 3*((y+2)/3-1)+1;
    for(int ch_x = x_s; ch_x<x_s+3; ch_x++){
        for(int ch_y=y_s; ch_y<y_s+3; ch_y++){
            if(ch_x!=x && ch_y!=y){
                if(value==a[ch_x][ch_y]) return false;
            }
        }
    }
    return true;
}

bool find(int &x, int &y){
    // check if valid cells are exists
    for(x=1; x<=9; x++){
        for(y=1; y<=9; y++){
            if(a[x][y] == 0)
                return true;
        }
    } 
    return false;
}

bool solve(){
    int x,y;
    //base::case
    if(!find(x,y)) return true;
    for(int cand = 1; cand <=9; cand++){
        if(is_valid(x,y,cand)){
            a[x][y] = cand;
            if(solve()) return true;
            a[x][y] = 0;
        }
    }
    return false;
}

void print(){
    //print the sudoku plate
    for(int i=1;i<=9; i++){
        for(int j=1; j<=9; j++){
            printf("%2d",a[i][j]);
        }
        printf("\n");
    }
    return ;
}

int main(){
    //Fill in some empty grid with the known values
    /*for(int i=1; i<=9; i++){
        for(int j=1; j<=9; j++){
        scanf("%1d",&a[i][j]);
        }
    }*/

    if (solve()) print();
    else printf("No solution exists\n");
    return 0;
}

我想我的 'solve function' 或 'is_valid' 函数无法正常工作。

在'is_valid'函数中，如果有问题就是

bool find(int &x, int &y){
// check if valid cells are exists
    for(x=1; x<=9; x++){
        for(y=1; y<=9; y++){
            if(a[x][y] == 0)
                return true;
        }
    }
    return false;
}

但是，我也对这部分进行了硬编码，在我的范围内它似乎没有问题。

在'solve function'

bool solve(){
    int x,y;
    //base::case
    if(!find(x,y)) return true;
    for(int cand = 1; cand <=9; cand++){
        if(is_valid(x,y,cand)){
            a[x][y] = cand;
            if(solve()) return true;
            a[x][y] = 0;
        }
    }
    return false;
}

我不知道我哪里错了。如果您在 solve() 函数中发现任何其他错误 - 请告诉我。因为我不确定我是否完全理解 "backtracking" 事情...

p.s。 : 参考我阅读 (https://see.stanford.edu/materials/icspacs106b/H19-RecBacktrackExamples.pdf)

Answer 1

有一些错误

您混淆了 (x, y) 和 (row, col) 寻址（行是 y，而不是 x）。选择一个表示并坚持下去
is_valid 中有一个拼写错误，因为 (c, x) 上的检查应该在 (c, y) 上（或 (y, c)，具体取决于惯例，但肯定会使用 y而不是 x 再次)
3x3 子块计算错误...例如，正确的公式可能是 int start_x = (x-1)/3*3 + 1, start_y = (y-1)/3*3 + 1;

修复代码在给定示例中的所有问题

用回溯法解决数独问题 - C++

solve sudoku with backtracking - C++

c++

sudoku

backtracking