目录
- 引言
- 一、N皇后问题
- 代码实现
- 测试
- 二、数独问题
- 代码实现
- 测试
引言
这个N皇后问题是很典型的一个递归问题,就是还是要掌握,所谓递归其实就是dfs,一层一层深入下去。数独和N皇后的思路是一样的,只不过一些细节不同而已。
一、N皇后问题
首先介绍一下八皇后问题,那么N皇后就是N*N个棋盘里,放入N个棋子,要求同行同列同斜线不能有重复的棋子
代码实现
这个思路就是暴力枚举,从第一行第一列开始,如果满足要求就落棋子,接着进入下一行,如果一直到了第n+1行说明前n行都满足要求,说明符合情况,就次数加一,然后把该情况打印一下。如果该行结束了,那么就回退到上一行中,把之前落得棋子拾起来,然后再判断下一列是否能够放棋子,一直到第一行结束。
跟下图的思想是一样的,唯一不同的是第二行条件不满足的时候,就进入下一列而不进入下一层
#include<iostream>
using namespace std;
const int N = 10;
int g[N][N]; //0代表不落棋子,1代表落棋子
int n, cnt;
int dir[3][2] = { -1,-1, -1,0, -1,1 }; //代表方向,分别是左上、上、右上
bool check(int row, int col)
{
for (int i = 0; i < 3; ++i)
{
int x = row, y = col;
while (1)
{
x += dir[i][0];
y += dir[i][1];
if (x < 0 || x >= n || y < 0 || y >= n) break;
if (g[x][y]) return false;
}
}
return true;
}
void dfs(int row)
{
if (row >= n)
{
cnt++;
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < n; ++j)
{
printf("%d ", g[i][j]);
}
puts("");
}
puts("");
}
for (int j = 0; j < n; ++j)
{
if (check(row, j))
{
g[row][j] = 1;
dfs(row + 1);
g[row][j] = 0;
}
}
}
int main()
{
cin >> n;
dfs(0);
return 0;
}
测试
输入4可以看出是正确的
输入10,并把输出信息改为最后输出cnt,所得结果也是正确的
二、数独问题
9*9的格子里,填充数字1~9,要求同行同列不能重复,同一个田字格也不能重复
代码实现
#include<iostream>
using namespace std;
int g[9][9] = { 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 }; //0代表没放 1~9代表放的该数字
int cnt;
bool check(int row, int col, int num)
{
if (g[row][col]) return false;
for (int i = 0, j = col; i < 9; ++i)
{
if (g[i][j] == num) return false;
}
for (int i = row, j = 0; j < 9; ++j)
{
if (g[i][j] == num) return false;
}
int x1 = row / 3 * 3, y1 = col / 3 * 3;
for (int i = x1; i < x1 + 3; ++i)
{
for (int j = y1; j < y1 + 3; ++j)
{
if (g[i][j] == num) return false;
}
}
return true;
}
void dfs(int row, int col)
{
if (row >= 9)
{
cnt++;
for (int i = 0; i < 9; ++i)
{
for (int j = 0; j < 9; ++j)
{
printf("%d ", g[i][j]);
}
puts("");
}
puts("");
return;
}
if (g[row][col] == 0)
{
for (int num = 1; num <= 9; ++num)
{
if (check(row, col, num))
{
g[row][col] = num;
dfs(row + (col + 1) / 9, (col + 1) % 9);
g[row][col] = 0;
}
}
}
else
{
dfs(row + (col + 1) / 9, (col + 1) % 9);
}
}
int main()
{
dfs(0,0);
//0 1 2 3 4 5 6 7 8
return 0;
}
测试
可以看出来是正确的