幻方回溯与递归C++

Question

我试图用C++中的回溯和递归来解决C++中的幻方问题。特别适用于4x4数组。

4x4幻方解的一个例子如下，其中每行、每列和对角线加34：

我所做的更改是：用户输入一些值，这些值将启动算法。

我的算法是这样的：

在这里你可以更好地欣赏图像。

我有一个概念，算法应该如何工作，以解决幻方的问题，回溯和递归，但我有问题。

其中之一是：

成就并没有让我的算法“忽略”用户已经输入的值。

我在C++中的代码在GitHub的这个链接中。代码如下：

#include <iostream>

using namespace std;

int sudoku[4][4];

int row = 0;
int column = 0;

bool isFull(int s[4][4]){
    for(int i = 0; i < 4; i++){
        for(int j = 0; j < 4; j++){
            if(s[4][4] == 0){
                return false;
            }
        }
    }

    return true;
}

void printMatrix(int s[4][4]){
    for(int i = 0; i < 4; i++){
        for(int j = 0; j < 4; j++){
            cout << sudoku[i][j] << "  ";
        }
        cout << endl;
    }
}

bool isAssigned(int row, int column){
    if(row == 1 && column == 0 ||
       row == 0 && column == 2 ||
       row == 1 && column == 2){
        return true;
    } else return false;
}

bool verify(int s[4][4], int row, int column){

    bool flag = false;

    int sumrow = 0, sumcolumn = 0, sumDiagonal = 0, sumDiagonal2 = 0;
    int value = 3;
    for(int i = 0; i < 4; i++){
        sumrow = sumrow + s[row][i];
        sumcolumn = sumcolumn + s[i][column];
        sumDiagonal = sumDiagonal + s[i][i];
        sumDiagonal2 = sumDiagonal2 + s[i][value];
        value--;
    }

    if(sumrow <= 34 && sumcolumn <= 34 && sumDiagonal2 <= 34 && sumDiagonal2 <= 34){
        return true;
    } else return false;

}

bool backtracking(int s[4][4], int row, int column){

    if(isFull(s) == true){ //verify if there are no zeros in the matrix
        printMatrix(sudoku);
        cout<<"Solution find ";
    }
    else {

        if(isAssigned(row, column) == false){ // verify if the cell is already assigned

            for(int i = 1; i <= 16; i++){

                s[row][column] = i; // assigned value

                if(verify(s, row, column) == true){ // verify that the sum of the column, row and diagonal not greater 34

                    if(column == 4) {
                            row++;
                            column=0;
                    }

                    backtracking(s, row, column + 1); // recursion
                    printMatrix(s); // Print the matrix to see progress
                    cout<<endl;

                } else { // the sum value exceeds 34
                    s[row][column] = 0;
                    return false;
                }
            }
        }
    }
}

int main(){

    sudoku[1][0] = 5;
    sudoku[0][2] = 15;
    sudoku[1][2] = 10;

    backtracking(sudoku, row, column);

    return 0;
}

我的算法主要如下：

显然，本例中有一些特性，但是如果您看到我的代码，您就会意识到我试图做什么。

也许我的解决方法不起作用或不好。

发布这篇文章的原因是，我需要帮助来改进或者需要帮助来解决代码所做的。下面是我运行的主要函数和输出：

bool backtracking(int s[4][4], int row, int column){

    if(isFull(s) == true){ //verify if there are no zeros in the matrix
        printMatrix(sudoku);
        cout<<"Solution find ";
    }
    else {

        if(isAssigned(row, column) == false){ // verify if the cell is already assigned

            for(int i = 1; i <= 16; i++){

                s[row][column] = i; // assigned value

                if(verify(s, row, column) == true){ // verify that the sum of the column, row and diagonal not greater 34

                    if(column == 4) {
                            row++;
                            column=0;
                    }

                    backtracking(s, row, column + 1); // recursion
                    printMatrix(s); // Print the matrix to see progress
                    cout<<endl;

                } else { // the sum value exceeds 34
                    s[row][column] = 0;
                    return false;
                }
            }
        }
    }
}

产出：

3  16  15  0
5  0  10   0
0  0  0    0
0  0  0    0

正如我之前所说的，当我发现一个用户已经被分配的值时，我会遇到问题。这是第一次使用回溯，这就是为什么我觉得有点困难。谢谢你的一切。

Answer 1

嗯，是的，

最近不得不做一些类似的事情，一些地方来“修复”这个问题

从网格中已经分配的数字的位图（1-16）开始。也就是说，用户输入的那些已经标记为“正在使用”。只为该位图中尚未标记的网格分配数字。如果使用非递归方法，则需要使用堆栈来知道哪些已经测试过，以便在回溯时“取消设置”。如果使用递归方法（只有16个深度递归；））将位图和已放置的正方形作为副本传递，而不是引用；）