马上注册，结交更多好友，享用更多功能^_^
您需要 登录 才可以下载或查看，没有账号？立即注册
x
最近快被这个问题急死了，调试的时候总是卡在回溯这一步，却也不清楚出了什么问题，求教！ #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:22 编辑 #include<iostream>
using namespace std;
int puzzle[9][9];
void out()
{
cout << "Puzzle Solved Successfully!" << endl;
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
cout << puzzle[i][j] << ' ';
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[i][j] == 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[i][j] == number)
return false;
}
}
for (x = 0; x < 9; x++)
{
if (puzzle[x][j0] == number)
return false;
}
for (y = 0; y < 9; y++)
{
if (puzzle[i0][y] == number)
return false;
}
return true;
}
void solveSudoku(int i, int j)
{
if ( isfull() )
{
out();
return;
}
else
{
if (puzzle[i][j])
{
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[i][j] = p;
solveSudoku(i,j);
}
}
puzzle[i][j] = 0;
}
}
}
int main()
{
puzzle[0][0] = 0;
puzzle[0][1] = 0;
puzzle[0][2] = 5;
puzzle[0][3] = 3;
puzzle[0][4] = 0;
puzzle[0][5] = 0;
puzzle[0][6] = 0;
puzzle[0][7] = 0;
puzzle[0][8] = 0;
puzzle[1][0] = 8;
puzzle[1][1] = 0;
puzzle[1][2] = 0;
puzzle[1][3] = 0;
puzzle[1][4] = 0;
puzzle[1][5] = 0;
puzzle[1][6] = 0;
puzzle[1][7] = 2;
puzzle[1][8] = 0;
puzzle[2][0] = 0;
puzzle[2][1] = 7;
puzzle[2][2] = 0;
puzzle[2][3] = 0;
puzzle[2][4] = 1;
puzzle[2][5] = 0;
puzzle[2][6] = 5;
puzzle[2][7] = 0;
puzzle[2][8] = 0;
puzzle[3][0] = 4;
puzzle[3][1] = 0;
puzzle[3][2] = 0;
puzzle[3][3] = 0;
puzzle[3][4] = 0;
puzzle[3][5] = 5;
puzzle[3][6] = 3;
puzzle[3][7] = 0;
puzzle[3][8] = 0;
puzzle[4][0] = 0;
puzzle[4][1] = 1;
puzzle[4][2] = 0;
puzzle[4][3] = 0;
puzzle[4][4] = 7;
puzzle[4][5] = 0;
puzzle[4][6] = 0;
puzzle[4][7] = 0;
puzzle[4][8] = 6;
puzzle[5][0] = 0;
puzzle[5][1] = 0;
puzzle[5][2] = 3;
puzzle[5][3] = 2;
puzzle[5][4] = 0;
puzzle[5][5] = 0;
puzzle[5][6] = 0;
puzzle[5][7] = 8;
puzzle[5][8] = 0;
puzzle[6][0] = 0;
puzzle[6][1] = 6;
puzzle[6][2] = 0;
puzzle[6][3] = 5;
puzzle[6][4] = 0;
puzzle[6][5] = 0;
puzzle[6][6] = 0;
puzzle[6][7] = 0;
puzzle[6][8] = 9;
puzzle[7][0] = 0;
puzzle[7][1] = 0;
puzzle[7][2] = 4;
puzzle[7][3] = 0;
puzzle[7][4] = 0;
puzzle[7][5] = 0;
puzzle[7][6] = 0;
puzzle[7][7] = 3;
puzzle[7][8] = 0;
puzzle[8][0] = 0;
puzzle[8][1] = 0;
puzzle[8][2] = 0;
puzzle[8][3] = 0;
puzzle[8][4] = 0;
puzzle[8][5] = 9;
puzzle[8][6] = 7;
puzzle[8][7] = 0;
puzzle[8][8] = 0;
printf("Solving sudoku puzzle.....\n");
solveSudoku(0,0);
return 0;
}
| 
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
狗仔卡
发表于 2018-8-24 08:19:00
置顶卡
千斤顶
显身卡
楼主
发表于 2018-8-30 15:16:23
