魔方阵回溯和递归 C++

Question

我正在尝试使用C ++中的回溯和递归来解决幻方问题。特别是针对一个4x4的数组。

一个4x4幻方解决方案的例子如下，其中每行，每列和对角线加起来为34:

我需要进行的更改是：用户输入一些数值，这将启动算法。

我的算法如下：

在这里

，你可以更好地欣赏图片。

我对使用回溯和递归解决幻方问题的算法有一定的了解，但是我遇到了一些问题。

其中一个问题是：

如何使我的算法“忽略”用户已经输入的值。

我的C++代码在这个链接里。下面是代码：

#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

就像我之前所说的，当我发现用户已经分配了一个值时，我会遇到问题。 这是我第一次使用回溯算法，所以我觉得有点困难。谢谢。

- Jonatan Lavado

---

如果您有可用的代码，可以在SE Code Review上寻求改进。但我非常怀疑您的问题是否会对Stack Overflow的c++标签来说过于宽泛。 - πάντα ῥεῖ

了解有关continuations、continuation-passing style、Prolog和当然还有backtracking的内容。 - Basile Starynkevitch

我需要帮助改进或给我解决回溯和递归问题的想法。这并不是很清楚，而且相当广泛。请编辑您的帖子以提出一个具体的编程问题。 - Baum mit Augen

@L.Flor “我需要帮助解决这个问题” 这不是一个非常具体的“编程问题”。 - πάντα ῥεῖ

你的“回溯(backtracking)”中存在许多问题：在每个代码路径中都没有返回值、没有移动行、在尝试和失败后没有重置输入（entry）、没有检查递归调用的返回值等等... 你是否尝试过理解一个简单的递归函数呢？你需要像Basile建议的那样去学习，但也许可以先从递归教程开始。 - BeyelerStudios

Answer 1

好的，是的，

最近不得不做类似的事情，以下是一些解决方法：

首先从一个位图（1-16）开始，用于标记在网格中已经分配了数字的位置。即用户输入的那些位置已经被标记为“已使用”。 只将未在该位图中标记的数字分配给网格。如果使用非递归方法，需要使用堆栈来知道哪些已经被测试并在回溯时“取消设置”。如果使用递归方法（仅16次深度递归;)），则将位图和已放置的正方形作为副本而非引用传递;)

- Hvisage