我正在尝试通过递归来解决数独问题。该程序运行良好。问题是堆栈只能保持 4-6K 递归。这意味着如果我要让数独游戏中有超过 6-7 个空单元格，则解决它所需的组合是:
4^7 = 16384 > 4-5K...
如何改进我的程序以减少调用次数？该程序很好地解决了这个问题。函数:
void solve_soduku(int soduku[][N*N], int &row, int &col, const bool fix_v[][N*N])
是所有业务。
我在这里为您提供正确数独所需的所有数字，以免浪费您的时间。您可以取出其中的一些，看看它是如何工作的:
0 0 1
0 1 2
0 2 3
0 3 4
1 0 4
1 1 3
1 2 2
1 3 1
2 0 3
2 1 1
2 2 4
2 3 2
3 0 2
3 1 4
3 2 1
3 3 3
-1
和代码:
#include <iostream>
using namespace std;
const int N = 2;
void zero_soduku(int soduku[][N*N]);
void zero_arr(int temp_arr[], int size);
void get_input(int soduku[][N*N], bool fixed_values[][N*N]);
void solve_soduku(int soduku[][N*N], int &row, int &col, const bool fix_v[][N*N]);
bool check_soduku(const int soduku[][N*N]);
bool check_rows(const int soduku[][N*N]);
bool check_cols(const int soduku[][N*N]);
bool check_sub_interval(const int soduku[][N*N]);
void print_soduku(const int soduku[][N*N]);
int main() {
int soduku[N*N][N*N] = { 0 }, row = 0, col = 0;
bool fixed_values[N*N][N*N] = { false };
get_input(soduku, fixed_values);
solve_soduku(soduku, row, col, fixed_values);
cout << endl;
print_soduku(soduku);
system("pause");
return EXIT_SUCCESS;
}
bool check_soduku(const int soduku[][N*N]) {
if (check_rows(soduku) && check_cols(soduku) && check_sub_interval(soduku))
return true;
return false;
}
bool check_rows(const int soduku[][N*N]) {
int temp_arr[N*N] = { 0 };
for (auto i = 0; i < N*N; i++) {
zero_arr(temp_arr, N*N);
for (auto j = 0; j < N*N; j++)
temp_arr[soduku[i][j] - 1]++;
for (auto k = 0; k < N*N; k++)
if (temp_arr[k]>1)
return false;
}
return true;
}
bool check_cols(const int soduku[][N*N]) {
int temp_arr[N*N] = { 0 };
for (auto i = 0; i < N*N; i++) {
zero_arr(temp_arr, N*N);
for (auto j = 0; j < N*N; j++)
temp_arr[soduku[j][i] - 1]++;
for (auto k = 0; k < N*N; k++)
if (temp_arr[k]>1)
return false;
}
return true;
}
bool check_sub_interval(const int soduku[][N*N]) {
int temp_arr[N*N] = { 0 };
for (auto rows_intervals = 0; rows_intervals < N; rows_intervals++)
for (auto cols_intervals = 0; cols_intervals < N; cols_intervals++)
for (auto i = rows_intervals*N; i < rows_intervals*N + N; i++)
for (auto j = cols_intervals*N; j < cols_intervals*N + N; j++) {
temp_arr[soduku[i][j] - 1]++;
//end of interval, check if !good interval
if (i == rows_intervals*N + N - 1 && j == cols_intervals*N + N - 1) {
for (auto k = 0; k < N*N; k++)
if (temp_arr[k]>1)
return false;
zero_arr(temp_arr, N*N);
}
}
return true;
}
void solve_soduku(int soduku[][N*N], int &row, int &col, const bool fix_v[][N*N]) {
static int counter = 0;
counter++;
cout << endl << counter << endl;
//Not empty cell
if (soduku[row][col] != 0)
//Not end of line
if (col < N*N - 1) {
col++;
solve_soduku(soduku, row, col, fix_v);
}
else
//Not end of rows
if (row < N*N - 1) {
row++;
col = 0;
solve_soduku(soduku, row, col, fix_v);
}
else
//end of soduku
if (check_soduku(soduku)) {
print_soduku(soduku);
return;
}
/////// Finishd soduku but answaer not good //////////////////
else
//Last cell not max
if (soduku[row][col] < N*N - 1) {
soduku[row][col]++;
print_soduku(soduku);
cout << endl;
solve_soduku(soduku, row, col, fix_v);
}
//Last cell max, going back...
else {
while (soduku[row][col] == N*N || fix_v[row][col]) {
if (!fix_v[row][col]) {
soduku[row][col] = 1;
print_soduku(soduku);
cout << endl;
}
if (col > 0) {
col--;
continue;
}
if (col == 0 && row > 0) {
col = N*N - 1;
row--;
}
}
if (!fix_v[row][col]) {
soduku[row][col]++;
print_soduku(soduku);
cout << endl;
}
solve_soduku(soduku, row, col, fix_v);
}
//////////////////////////////////////////////////////////////////////////
//Empty cell
else {
soduku[row][col]++;
print_soduku(soduku);
cout << endl;
solve_soduku(soduku, row, col, fix_v);
}
}
void zero_arr(int temp_arr[], int size) {
for (auto i = 0; i < size; i++)
temp_arr[i] = 0;
}
void zero_soduku(int soduku[][N*N]) {
for (int i = 0; i < N*N; i++)
for (int j = 0; j < N*N; j++)
soduku[i][j] = 0;
}
void get_input(int soduku[][N*N], bool fixed_values[][N*N]) {
cout << endl << "Please enter locatin and nums into soduku: ";
int row = 0, col, value;
while (row != -1) {
cin >> row;
if (row == -1)
return;
cin >> col >> value;
soduku[row][col] = value;
fixed_values[row][col] = true;
}
}
void print_soduku(const int soduku[][N*N]) {
for (auto i = 0; i < N*N; i++)
for (auto j = 0; j < N*N; j++) {
cout << soduku[i][j] << " ";
if (j == N*N - 1)
cout << endl;
}
//system("pause");
}`enter code here`
最佳答案
您的算法似乎大致是:
1) 依次尝试每一步
2)检查整个板子是否有效
3) 重复直到填满整个棋盘
这显然是非常低效的。代码将进行许多非法的移动，然后才意识到这一点，事后才迟到。
我会建议你完全摆脱这个，并尝试实现一些更有效的东西。尝试思考碳基生命形式如何解决数独难题，并实现相同的算法。当您解决数独难题时，您是否也采用上述方法？当然不是。你做这样的事情:
1) 对于棋盘上的每个位置，不是只存储该位置的当前数字，如果有的话，还存储附加信息:即，如果该位置没有数字，还存储所有可能合法的数字为那个位置移动。
例如，对于一个完全空的棋盘，数独棋盘上的每个位置都将包含所有值 1-9。由此，我们进行下一个合乎逻辑的步骤:
2) 当移动并在某个位置放置一个值时，比如 4，您将从其 3x3 正方形中的所有其他单元格中删除值 4，并从同一行和列中的所有其他单元格中删除 4。因为该数字将不再是这些单元格中的有效移动。相反，当撤消移动并从单元格中删除 4 时，这意味着值 4 现在在其 3x3 正方形及其行和列中的所有单元格中都是合法的，因此您可以将此值放在所有这些位置，作为一个数字，现在在这些位置上是合法的举动。
3) 在决定下一步行动时，首先扫描棋盘，寻找任何只有一个可能的合法数字的单元格。当然，这意味着这是该单元的唯一合法移动，所以你做到了。
4) 如果您发现任何单元格没有剩余的合法值，这意味着您已达到无法解决的状态，因此您将撤消上一步，然后从该点开始尝试下一个有效的步法。
5) 否则，你应该只选择一个剩余可能的合法移动最少的单元格，进行第一步移动，然后继续前进，然后如果你达到无法解决的状态，并返回到此移动，你撤消它, 然后尝试下一步。
在我看来，这应该是一种更有效的方法，因为它最终应该使非法移动次数最少。
它也非常模仿碳基生命体如何自己解决数独难题。
附言要用预填数字初始化一个新的数独谜题，只需从一个空的数独板开始，所有单元格都允许所有数字 1-9 作为合法移动，然后如上所述进行每个移动以填写数独板上的初始数字.
关于c++ - 递归数独求解器几乎可以工作，但空网格会出现堆栈溢出，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/34964519/