C++ 利用回溯算法 算数独出错,求解答
小弟是新手,要做一个数独的游戏,参照了一个求解数独的经典代码。但发现必须在debug里输入元素才能求解,我尝试把pu[9][9]变成pu[9][9]={{}}(里面的数字省略了,绝对是正确的数独)后。发现无法在debug里显示任何东西,请问是怎么回事。
#include <iostream>
#include <stdio.h>
using namespace std;
static int pu[9][9];
int isvalid(const int i, const int j)
{
const int n = pu[i][j];
const static int query[] = {0, 0, 0, 3, 3, 3, 6, 6, 6};
int t, u;
for (t = 0; t < 9; t++)
if (t != i && pu[t][j] == n || t != j && pu[i][t] == n)
return 0;
for (t = query[i]; t < query[i] + 3; t++)
for (u = query[j]; u < query[j] + 3; u++)
if ((t != i || u != j) && pu[t][u] == n)
return 0;
return 1;
}
void output(void)
{
static int n;
printf("Solution is:\n");
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++)
cout<< pu[i][j] << " ";
cout << endl;
}
cout << endl;
}
void Try(const int n)
{
if (n == 81)
{output();
return;
}
const int i = n / 9, j = n % 9;
if (pu[i][j] != 0)
{
Try(n + 1);
return;
}
for (int k = 0; k < 9; k++) {
pu[i][j]++;
if (isvalid(i, j))
Try(n + 1);
}
pu[i][j] = 0;
}
int main(void)
{
int i,j;
for (i=0;i<9;i++)
{
for (j=0;j<9;j++)
{
cin>>pu[i][j];
}
}
Try(0);
return 0;
}(这是原程序)
我把这程序改成了:
#include <iostream>
#include <stdio.h>
using namespace std;
static int pu[9][9]={{0,1,4,0,5,0,0,0,3},{6,0,0,0,0,9,4,2,0},{8,0,0,1,0,0,0,9,0},{0,0,5,0,9,0,0,4,0},{4,0,0,7,0,8,0,5,2},{0,7,0,0,2,0,6,0,0},{0,9,0,0,0,1,0,0,5},{0,2,8,3,0,0,0,0,4},
{5,0,0,0,6,0,7,1,0}};
int isvalid(const int i, const int j)
{
const int n = pu[i][j];
const static int query[] = {0, 0, 0, 3, 3, 3, 6, 6, 6};
int t, u;
for (t = 0; t < 9; t++)
if (t != i && pu[t][j] == n || t != j && pu[i][t] == n)
return 0;
for (t = query[i]; t < query[i] + 3; t++)
for (u = query[j]; u < query[j] + 3; u++)
if ((t != i || u != j) && pu[t][u] == n)
return 0;
return 1;
}
void output(void)
{
static int n;
printf("Solution is:\n");
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++)
cout<< pu[i][j] << " ";
cout << endl;
}
cout << endl;
}
void Try(const int n)
{
if (n == 81)
{output();
return;
}
const int i = n / 9, j = n % 9;
if (pu[i][j] != 0)
{
Try(n + 1);
return;
}
for (int k = 0; k < 9; k++) {
pu[i][j]++;
if (isvalid(i, j))
Try(n + 1);
}
pu[i][j] = 0;
}
int main(void)
{
int pu[9][9]={{0,1,4,0,5,0,0,0,3},{6,0,0,0,0,9,4,2,0},{8,0,0,1,0,0,0,9,0},{0,0,5,0,9,0,0,4,0},{4,0,0,7,0,8,0,5,2},{0,7,0,0,2,0,6,0,0},{0,9,0,0,0,1,0,0,5},{0,2,8,3,0,0,0,0,4},
{5,0,0,0,6,0,7,1,0}};
Try(0);
return 0;
}
后果就是debug里面什么都没有,请问是怎么一回事
[解决办法]
把main改成这样试试:
int main(void)
{
int m_pu[9][9] =
{
{0,1,4,0,5,0,0,0,3},
{6,0,0,0,0,9,4,2,0},
{8,0,0,1,0,0,0,9,0},
{0,0,5,0,9,0,0,4,0},
{4,0,0,7,0,8,0,5,2},
{0,7,0,0,2,0,6,0,0},
{0,9,0,0,0,1,0,0,5},
{0,2,8,3,0,0,0,0,4},
{5,0,0,0,6,0,7,1,0}
};
for (int i = 0; i < 9; ++i)
{
for (int j = 0; j < 9; ++j)
{
pu[i][j] = m_pu[i][j];
}
}
Try(0);
return 0;
}
数独,在回溯过程中,应用一些“余数法”,比如:显式唯一余数、隐式唯一余数、对数法、宫格删除法等,可以把计算效率提升很多的(是减少了很多的尝试)。
我算了一下,你这个数独有唯一解:
9 1 4 2 5 6 8 7 3
6 5 7 8 3 9 4 2 1
8 3 2 1 4 7 5 9 6
2 8 5 6 9 3 1 4 7
4 6 9 7 1 8 3 5 2
3 7 1 5 2 4 6 8 9
7 9 6 4 8 1 2 3 5
1 2 8 3 7 5 9 6 4
5 4 3 9 6 2 7 1 8