我正在尝试找到 3X3 幻方的所有可能解决方案。 应该正好有 8 个解决方案。
我的代码得到了所有这些,但有很多重复。我很难跟踪递归步骤以了解为什么我得到所有重复。
// This program finds all solutions to the magic square for a 3X3
// square where each column, row and diagonal sum is equal
#include <iostream>
using namespace std;
#define SQUARE_SIZE 9
int anyLine = 0;
int currLine = 0;
int numSolutions = 0;
// swap two values in the square.
void swap(int arr[], int idxa, int idxb)
{
int tmp = arr[idxa];
arr[idxa] = arr[idxb];
arr[idxb] = tmp;
}
void printArray(int arr[])
{
for (int i = 0; i < SQUARE_SIZE; i++)
{
cout << arr[i] << " ";
if ((i + 1) % 3 == 0)
cout << endl;
}
cout << endl;
}
// this function tests to see if we have a "good" arrangement of numbers
// i.e the sum of each row, column and diagonal is equal
bool checkArr(int arr[])
{
anyLine = arr[0] + arr[1] + arr[2];
currLine = 0;
for (int i = 0; i < SQUARE_SIZE; i++)
{
currLine += arr[i];
if ((i + 1) % 3 == 0)
{
if (currLine != anyLine)
return false;
currLine = 0;
}
}
// check vertically
for (int col = 0; col <3; col++)
{
for (int row = 0; row <3; row++)
{
currLine += arr[col + 3 * row];
}
if (currLine != anyLine)
return false;
currLine = 0;
}
// check the diagonals
if ((arr[2] + arr[4] + arr[6]) != anyLine)
return false;
if ((arr[0] + arr[4] + arr[8]) != anyLine)
return false;
return true;
}
void solve(int arr[], int pos)
{
if (pos == 8)
{
if (checkArr(arr))
{
printArray(arr);
numSolutions++;
}
} else
{
for (int i = 0; i < 9; i++)
{
if (i == pos) continue;
if (checkArr(arr))
{
printArray(arr);
numSolutions++;
}
swap(arr, pos, i);
solve(arr, pos + 1);
}
}
}
int main()
{
int arr[SQUARE_SIZE] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
solve(arr, 0);
cout << "number of solutions is: " << numSolutions << endl;
return 0;
}
最佳答案
基本上,您使用 recursive permutation algorithm 查找数组的所有排列.
您需要更改 4 项内容:
首先,从 pos 开始你的循环,而不是 0
其次,递归(回溯)后将元素交换回来
第三,仅在生成每个完整排列后(当 pos = 8 时)才进行测试,否则您将多次测试相同的排列。
第四,元素与其自身交换(即不交换)是有效的排列,因为允许元素保留在其原始位置。
void solve(int arr[], int pos)
{
if (pos == 8)
{
if (checkArr(arr))
{
printArray(arr);
numSolutions++;
}
}
else
{
for (int i = pos ; i < 9; i++)
{
swap(arr,pos,i);
solve(arr,pos +1);
swap(arr,pos,i);
}
}
}
关于c++ - 递归 3 X 3 幻方,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/30981523/