[已解决]回溯法解决数独问题（求助）

Alkane

上一次发帖也没人回我，本着不要脸的原则，再发一次
问题就在于回溯的那一步总是卡住，不清楚是那儿出了错
拜托各位啦！！！

#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[9][9];
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[i][j] == number)return false;
                }
        }
        j = jj;
        //对列判断
        for (i = 0; i < 9; i++)
        {
                if (num[i][j] == number)return false;
        }
        i = ii;
        //对行判断
        for (j = 0; j < 9; j++)
        {
                if (num[i][j] == number)return false;
        }
        return true;
}
bool isfull()
{
        for (int i = 0; i < 9; i++)
        {
                for (int j = 0; j < 9; j++)
                {
                        if (num[i][j] == 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[i][j] << ' ';
                }
                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[i][j]) 
                        {
                                if (j <8)dfs(i, j + 1);
                                if (j >= 8)dfs(i + 1, 0);
                                continue;
                        }
                        if (judge(i,j,p))
                        {
                                num[i][j] = p;
                                if (j < 8)dfs(i, j + 1);
                                if (j >= 8)dfs(i + 1, 0);
                        /*
                        放置后记得还原
                        */
                                num[i][j] = 0;
                        }
                }
        }
}
int main()
{
        //输入
        for (int i = 0; i < 9; i++)
        {
                for (int j = 0; j < 9; j++)
                {
                        scanf("%d", &num[i][j]);
                }
        }
        dfs(0, 0);
        
        return 0;
}

最佳答案

月排行榜 / 总排行榜

claws0n

2018-8-30 18:36:38

乖乖，不哭了
上面导入了不必要的头文件
宏定义没有必要
out() 修改一下，输出不好看

关键问题：
judge() 对块的逻辑判断有问题
dfs() p 的循环，位置 i, j 是相对局部，所以没有延续性，应该要相对全局。是可以完成，但进入死循环（虽然答案是错的）。
回溯还原的部分，在 if 判断式内部，不会执行呀

跳转到最佳答案楼层

fc1735

开头加上

#define continue break

还有很多优化的空间，加油吧！

claws0n

乖乖，不哭了
上面导入了不必要的头文件
宏定义没有必要
out() 修改一下，输出不好看

关键问题：
judge() 对块的逻辑判断有问题
dfs() p 的循环，位置 i, j 是相对局部，所以没有延续性，应该要相对全局。是可以完成，但进入死循环（虽然答案是错的）。
回溯还原的部分，在 if 判断式内部，不会执行呀