回溯法解决数独问题
最近快被这个问题急死了，调试的时候总是卡在回溯这一步，却也不清楚出了什么问题，求教！{: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;
}
{:10_266:}{:10_266:}{:10_266:} 附上测试用例一个：
0 0 5 3 0 0 0 0 0
8 0 0 0 0 0 0 2 0
0 7 0 0 1 0 5 0 0
4 0 0 0 0 5 3 0 0
0 1 0 0 7 0 0 0 6
0 0 3 2 0 0 0 8 0
0 6 0 5 0 0 0 0 9
0 0 4 0 0 0 0 3 0
0 0 0 0 0 9 7 0 0
@各路大神{:10_266:}{:10_266:}{:10_266:} {:9_222:}
不是不想回，算法没有多少人会 本帖最后由 claws0n 于 2018-8-30 18:22 编辑
#include<iostream>
using namespace std;
int puzzle;
void out()
{
cout << "Puzzle Solved Successfully!" << endl;
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
cout << puzzle << ' ';
if (j == 2 || j == 5)
cout << "| ";
}
cout << endl;
if (i == 2 || i == 5)
cout << "**********************\n";
}
}
bool isfull()
{
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
if (puzzle == 0)
return false;
}
}
return true;
}
bool judge(int i0, int j0, int number)
{
int x = i0 / 3 * 3;
int y = j0 / 3 * 3;
int i, j;
for (i = x; i < x+3 && i < 9; i++)
{
for (j = y; j < y+3 && j < 9; j++)
{
if (puzzle == number)
return false;
}
}
for (x = 0; x < 9; x++)
{
if (puzzle == number)
return false;
}
for (y = 0; y < 9; y++)
{
if (puzzle == number)
return false;
}
return true;
}
void solveSudoku(int i, int j)
{
if ( isfull() )
{
out();
return;
}
else
{
if (puzzle)
{
if (j <8) {j++;}
else {i++; j = 0;}
solveSudoku(i,j);
}
else
{
int p;
for (p = 1; p <= 9; p++)
{
if (judge(i,j,p))
{
puzzle = p;
solveSudoku(i,j);
}
}
puzzle = 0;
}
}
}
int main()
{
puzzle = 0;
puzzle = 0;
puzzle = 5;
puzzle = 3;
puzzle = 0;
puzzle = 0;
puzzle = 0;
puzzle = 0;
puzzle = 0;
puzzle = 8;
puzzle = 0;
puzzle = 0;
puzzle = 0;
puzzle = 0;
puzzle = 0;
puzzle = 0;
puzzle = 2;
puzzle = 0;
puzzle = 0;
puzzle = 7;
puzzle = 0;
puzzle = 0;
puzzle = 1;
puzzle = 0;
puzzle = 5;
puzzle = 0;
puzzle = 0;
puzzle = 4;
puzzle = 0;
puzzle = 0;
puzzle = 0;
puzzle = 0;
puzzle = 5;
puzzle = 3;
puzzle = 0;
puzzle = 0;
puzzle = 0;
puzzle = 1;
puzzle = 0;
puzzle = 0;
puzzle = 7;
puzzle = 0;
puzzle = 0;
puzzle = 0;
puzzle = 6;
puzzle = 0;
puzzle = 0;
puzzle = 3;
puzzle = 2;
puzzle = 0;
puzzle = 0;
puzzle = 0;
puzzle = 8;
puzzle = 0;
puzzle = 0;
puzzle = 6;
puzzle = 0;
puzzle = 5;
puzzle = 0;
puzzle = 0;
puzzle = 0;
puzzle = 0;
puzzle = 9;
puzzle = 0;
puzzle = 0;
puzzle = 4;
puzzle = 0;
puzzle = 0;
puzzle = 0;
puzzle = 0;
puzzle = 3;
puzzle = 0;
puzzle = 0;
puzzle = 0;
puzzle = 0;
puzzle = 0;
puzzle = 0;
puzzle = 9;
puzzle = 7;
puzzle = 0;
puzzle = 0;
printf("Solving sudoku puzzle.....\n");
solveSudoku(0,0);
return 0;
}
{:9_221:} 77 - 79 可以换成这样，比较好
if (j < 8) {solveSudoku(i, j+1);}
else {solveSudoku(i+1, 0);} 可以的 学习
页:
[1]