回溯法解决数独问题（求助）
上一次发帖也没人回我，本着不要脸的原则，再发一次{:5_100:}问题就在于回溯的那一步总是卡住，不清楚是那儿出了错
拜托各位啦！！！
#include<iostream>
#include<math.h>
#include<string>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<time.h>
/*
数独问题
*/
#define maxn 400000
using namespace std;
int num;
bool judge(int i, int j, int number)
{
int i0 = i / 3 * 3;
int j0 = j / 3 * 3;
int ii = i; int jj = j;
//对块判断
for (i = i0; i < i0 + 3; i++)
{
for (j = j0; j < j0 + 3; j++)
{
if (num == number)return false;
}
}
j = jj;
//对列判断
for (i = 0; i < 9; i++)
{
if (num == number)return false;
}
i = ii;
//对行判断
for (j = 0; j < 9; j++)
{
if (num == number)return false;
}
return true;
}
bool isfull()
{
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
if (num == 0)return false;
}
}
return true;
}
void out()
{
cout << "结果" << endl;
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
cout << num << ' ';
}
cout << endl;
}
}
void dfs(int i, int j)
{
/*
到达底部时，退出，此时i=j=8；
*/
if (i>= 8&&isfull())
{
out();
return;
}
else {
int p;
for (p = 1; p <= 9; p++)
{
/*
只有行、列、以及块都可以放置这个数的时候我们才放置，
不然就退出此次循环，也就是剪掉这个枝
*/
if (num)
{
if (j <8)dfs(i, j + 1);
if (j >= 8)dfs(i + 1, 0);
continue;
}
if (judge(i,j,p))
{
num = p;
if (j < 8)dfs(i, j + 1);
if (j >= 8)dfs(i + 1, 0);
/*
放置后记得还原
*/
num = 0;
}
}
}
}
int main()
{
//输入
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
scanf("%d", &num);
}
}
dfs(0, 0);
return 0;
} 开头加上
#define continue break
还有很多优化的空间，加油吧！ {:10_308:} 乖乖，不哭了
上面导入了不必要的头文件
宏定义没有必要
out() 修改一下，输出不好看
关键问题：
judge() 对块的逻辑判断有问题
dfs() p 的循环，位置 i, j 是相对局部，所以没有延续性，应该要相对全局。是可以完成，但进入死循环（虽然答案是错的）。
回溯还原的部分，在 if 判断式内部，不会执行呀{:10_245:}
页:
[1]