c - C 中的回溯数独求解器

Question

这是我被要求为类(class)做的一个程序，它必须解决大小为 nxn 的数独难题使用回溯算法，但不需要检查子方 block ，只需检查行和列。我的程序的问题是回溯部分永远不会触发:(每当它到达无法继续的点时，它就会停止并打印板，而不是删除最后一次尝试并尝试其他东西。提前抱歉缺少注释，我目前只能访问代码(不在家里)，但它主要是非常简单的函数，问题出在 aux_solveSudoku 和数独函数中，这是代码:

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define UNASSIGNED 0

bool aux_SolveSudoku(int n, int array[][n]);
bool SolveSudoku(int n, int array[][n], int row, int col);
bool check(int n, int array[][n], int row, int col, int number);
bool CheckRow(int n, int array[][n], int row, int number);
bool CheckCol(int n, int array[][n], int col, int number);
bool CheckIfFull(int n, int array[][n]);
void printArray(int n, int array[][n]);

int main()
{
    int n;
    scanf(" %d", &n);
    int array[n][n];

    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            scanf(" %d",&array[i][j]);
        }
    }
    if (aux_SolveSudoku(n, array) == true)
          printArray(n, array);
    else
         printf("No Solution!");


  return 0;
}

bool aux_SolveSudoku(int n, int array[][n]){
    for (int row = 0; row < n; row++){
        for (int col = 0; col < n; col++){
            if (SolveSudoku(n, array, row, col) && CheckIfFull(n, array))
                return true;}
    }
    return false;
}

bool SolveSudoku(int n, int array[][n], int row, int col){
    if(array[row][col] != UNASSIGNED)
        return true;

    for(int i=1; i<=n; i++){
        if(check(n, array, row, col, i)){
            array[row][col] = i;

            if(SolveSudoku(n, array, row, col))
                return true;

            array[row][col] = UNASSIGNED;
        }
    }    
    return false;
}

bool check(int n, int array[][n], int row, int col, int number){
    return (!CheckRow(n, array, row, number) && !CheckCol(n, array, col, number));
} 

bool CheckRow(int n, int array[][n], int row, int number){
    for (int col = 0; col < n; col++){
        if (array[row][col] == number){
            return true;}
    }
    return false;
}

bool CheckCol(int n, int array[][n], int col, int number){
    for (int row = 0; row <  n; row++){
        if (array[row][col] == number){
            return true;}
    }
    return false;

}

bool CheckIfFull(int n, int array[][n]){
    for (int i = 0; i < n; i++){
            for (int j = 0; j < n; j++){
                if(array[i][j] == UNASSIGNED)
                    return false;
                    }
            }
    return true;
}

void printArray(int n, int array[][n]){
    for (int row = 0; row < n; row++){
            for (int col = 0; col < n; col++){
                printf("%d ", array[row][col]);}
            printf("\n");
        }
}

这是该程序的一组示例数据:

5
0 0 0 2 4
3 1 0 0 2
0 2 1 0 5
2 0 3 0 0
0 0 0 0 0

这显然有一个解决方案:

1 3 5 2 4
3 1 4 5 2
4 2 1 3 5
2 5 3 4 1
5 4 2 1 3

不幸的是，程序没有找到解决方案，但我不明白为什么没有。

Answer 1

由于这部​​分代码，回溯无法工作。

bool SolveSudoku(int n, int array[][n], int row, int col){
    if(array[row][col] != UNASSIGNED)
        return true;

    for(int i=1; i<=n; i++){
        if(check(n, array, row, col, i)){
            array[row][col] = i;

            if(SolveSudoku(n, array, row, col))
                return true;

            array[row][col] = UNASSIGNED;
        }
    }    
    return false;
}

具体来说，当check方法返回true时，array[row][col]被设置为i。

在下一个语句中，调用 SolveSudoku，但行和列的值相同。

由于该值并非未分配，SolveSudoku 将返回 true。由于它返回 true，因此每个位置仅尝试一个值。没有以正确的方式利用递归。

我希望这可以解释为什么您的代码中不会发生回溯。祝你好运!如果您还有其他问题，请告诉我...

这里作为我用 Java 编写的示例。 solve 方法不会在嵌套 for 循环中调用，因此某些结束条件会以不同的方式进行计算。你只需用 0, 0 调用这个方法，它就会从那里开始......

void solve(int r, int c)
{
    if(board[r][c] == 0)
    {
        for(int i = 1; i < 10; i++)
        {
            if (!inRow(i, r) && !inCol(i, c) && !inSqr(i, r, c))
            {
                board[r][c] = i;
                if(r == 8 && c == 8)
                {
                    printBoard();
                    System.exit(0);
                }
                else if(c == 8) solve(r + 1, 0);
                else solve(r, c + 1);
            }
        }
        board[r][c] = 0;
    }
    else if(r == 8 && c == 8)
    {
        printBoard();
        System.exit(0);
    }
    else if(c == 8) 
    {
        solve(r + 1, 0);
    }
    else 
    {
        solve(r, c + 1);
    }
}