当前位置：首页 > news >正文

深入理解N皇后问题：从DFS到对角线优化

news 2025/4/27 22:27:57

N皇后问题是一个经典的算法问题，要求在N×N的棋盘上放置N个皇后，使得它们互不攻击。本文将全面解析该问题的解法，特别聚焦于DFS算法和对角线优化的数学原理。

问题描述

在N×N的国际象棋棋盘上放置N个皇后，要求：

任意两个皇后不在同一行
任意两个皇后不在同一列
任意两个皇后不在同一对角线

数据结构图解

1. 棋盘表示

char g[N][N];  // 棋盘矩阵
'.' 表示空位

'Q' 表示皇后

示例（n=4初始状态）：
. . . .
. . . .
. . . .
. . . .

2. 冲突检测数组

bool col[N];       // 列占用标记
bool dg[N*2];      // 正对角线占用标记
bool udg[N*2];     // 反对角线占用标记

对角线索引计算：

(0,0) (0,1) (0,2) (0,3)
(1,0) (1,1) (1,2) (1,3)
(2,0) (2,1) (2,2) (2,3)
(3,0) (3,1) (3,2) (3,3)

正对角线(dg)：u + i（行+列）

例如：(1,2)的正对角线索引=1+2=3

我们发现同一个对角线的上的坐标的x,y值相加是相等的，所以我们用dg[u+i]去标记

反对角线(udg)：n - u + i

例如：当n=4时，(1,2)的反对角线索引=4-1+2=5

反对角线，我们此时不能再次使用u+i了

但为了确保索引不重叠，我们使用n - u + i：

当u增加时，n - u减小

当i增加时，i增大

这样确保每条反对角线有唯一索引

实际计算示例（n=4）

坐标计算式索引值
(0,3) 4-0+3=7 7
(1,2) 4-1+2=5 5
(2,1) 4-2+1=3 3
(3,0) 4-3+0=1 1

坐标	计算式	索引值
(0,3)	4-0+3=7	7
(1,2)	4-1+2=5	5
(2,1)	4-2+1=3	3
(3,0)	4-3+0=1	1

算法执行流程图解

DFS递归过程

dfs(0)
├─ 尝试第0行第0列
│  ├─ 放置皇后
│  ├─ dfs(1)
│  │  ├─ 尝试第1行第2列
│  │  │  ├─ 放置皇后
│  │  │  ├─ dfs(2)
│  │  │  │  ├─ (冲突，回溯)
│  │  │  └─ 撤销皇后
│  │  └─ 尝试其他列...
│  └─ 撤销皇后
└─ 尝试第0行第1列├─ 放置皇后├─ dfs(1)│  ├─ 尝试第1行第3列│  │  ├─ 放置皇后│  │  ├─ dfs(2)│  │  │  ├─ 找到解│  │  │  └─ 输出棋盘│  │  └─ 撤销皇后│  └─ 尝试其他列...└─ 撤销皇后

示例解（n=4）

有效解之一：

. Q . .
. . . Q
Q . . .
. . Q .

对应的标记数组状态：

col: [1, 0, 1, 0] (第0、2列被占用)
dg: 索引1、3、4被占用
udg: 索引4、5、6被占用

完整代码

/*DFS			深度优先搜索*/
#include <stdio.h>
#include <stdbool.h>#define N 20int n;				//棋盘的大小(n*n)
char g[N][N];		//模拟棋盘,'.'表示空，'Q'表示皇后
//col表示列是否被占用，dg表示正对角线是否被占用，udg表示反对角线是否被占用
bool col[N], dg[N*2], udg[N*2];		void dfs(int u)	//u表示当前处理的行
{if (u == n)		//所有的行处理完毕,输出解,返回递归{for (int i = 0;i < n;i++)	//puts函数输出字符串,自动换行puts(g[i]);				//在二维数组g[][]中,单使用g[i]表示第i行的所有数据puts("");		//打印空格,隔开不同解return;}//尝试在当前行的每一列放置皇后for(int i = 0;i < n;i++)//检查列,正对角线,反对角线是否冲突if (!col[i] && !dg[u + i] && !udg[n - u + i]){g[u][i] = 'Q';		//放置皇后col[i] = dg[u + i] = udg[n - u + i] = true;		//标记占用dfs(u + 1);			//递归处理下一行col[i] = dg[u + i] = udg[n - u + i] = false;	//回溯,撤销原有的标记g[u][i] = '.';		//恢复棋盘}
}int main()
{scanf("%d", &n);//初始棋盘for (int i = 0;i < n;i++)for (int j = 0;j < n;j++)g[i][j] = '.';//从第0行开始DFSdfs(0);return 0;
}