我正在尝试使用C ++中的回溯和递归来解决幻方问题。特别是针对一个4x4的数组。
一个4x4幻方解决方案的例子如下,其中每行,每列和对角线加起来为34:
一个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
就像我之前所说的,当我发现用户已经分配了一个值时,我会遇到问题。 这是我第一次使用回溯算法,所以我觉得有点困难。谢谢。