蓝桥杯-N皇后问题（DFS经典题目详解）_dfsn皇后

一、题目回顾

在 N×N 的方格棋盘放置了 N 个皇后，使得它们不相互攻击（即任意 2 个皇后不允许处在同一排，同一列，也不允许处在与棋盘边框成 45 角的斜线上。你的任务是，对于给定的 N，求出有多少种合法的放置方法。

输入描述
输入中有一个正整数 N≤10，表示棋盘和皇后的数量

输出描述
为一个正整数，表示对应输入行的皇后的不同放置数量。

输入：

5
 输出：

10

运行限制
最大运行时间：1s
最大运行内存: 128M

下图有个简单的分析过程（图片来自网络）

二、题目分析

• 输入： 整数n，表示N皇后问题中的N。
• 输出： 所有合法的放置方式的数量。
• 限制条件： 皇后不得在同一行、同一列或同一对角线上。

• 回溯算法： 使用回溯算法递归地尝试将皇后放置在每一行的不同列上，然后检查是否满足限制条件。如果满足，则继续递归放置下一个皇后，直到所有皇后都放置完毕，然后增加解的计数器。
• 检查限制条件： 在每次放置皇后时，需要检查当前位置是否满足限制条件，即不在同一列、同一行或同一对角线上。可以通过编写一个 check() 函数来实现这一点。
• 记录解的数量： 使用一个全局变量 sum 来记录解的数量，在每次找到一个合法的解时增加计数器。

以下我将用代码演示解题的过程：

int n;              //表示要输入一个n*n的方格棋盘
int column[12];     //表示列（题目中要求n的值最大为10，所以这里预留12个位置即可。多预留两个，防                
                      止数组越界）
                    //因为放置皇后时会按照从第一行依次向下第二、第三等行放置，所以对于“行”，直 
                      接从1到n递增（row++）即可。
 
int sum = 0;        //记录合法的放置方式
 
int check(int row) {
	for (int i = 1; i <= row - 1; i++) {
 
		//判断对角线上是否有皇后；（在对角线上：abs(行-行)==abs(列-列)）
		if ((column[i] == column[row]) || abs(i - row) == abs(column[i] - column[row])) 
			return 0;		//不合法，返回0
	}
	return 1;               //合法，返回1
 
}
 
void dfs(int row) {    
 
	if (row == n + 1) {    //结束条件（边界）：如果当前“行”大于最后一行，即前n行全部放置完毕   
                             
		sum++;             //放置方式+1
		return;            //回溯（再去找前面的行，看是否还有其他位置可以选择）
	}
	
	for (int i = 1; i <= n; i++) {    //从第一行开始遍历，一直到最后一行
 
		column[row] = i;              //尝试将皇后放置在第row行的第i列
		if (check(row))               //检查放置的位置是否合法
			dfs(row + 1);             //若合法，递归放置下一个皇后
		else
			continue;                 //不合法，跳过当前列
	}
}
 
int main() {
 
	cin >> n;    //输入棋盘规模
 
	dfs(1);      //从第一行开始进入
 
	cout << sum << endl;
 
	return 0;
}

本体的困难点我个人认为：

一是在于：约束条件，包括不能在同一行、同一列或同一对角线上。要找到可以表示条件的关系，用（行-行）的绝对值==（列-列）的绝对值表示不在对角线的位置；

而是在于如何表示行与列，并确保每行每列的位置都能进行判断。