P1219 [USACO1.5] 八皇后 Checker Challenge

难度： 普及/提高−
算法标签： 深度优先搜索、回溯、N 皇后
来源： 洛谷 P1219

题目背景

本题围绕“[USACO1.5] 八皇后 Checker Challenge”所描述的场景展开。在一个 $n\times n$ 棋盘上放置 $n$ 个皇后，要求每一行、每一列以及每一条与主对角线平行的斜线上至多有一个皇后。

下面的题面采用非逐字重述方式整理，但保留原题中的全部判定条件、边界含义、输入输出要求与特殊约定。

题目描述

在一个 $n\times n$ 棋盘上放置 $n$ 个皇后，要求每一行、每一列以及每一条与主对角线平行的斜线上至多有一个皇后。用长度为 $n$ 的序列描述一个方案：第 $i$ 个数表示第 $i$ 行皇后所在的列。请按字典序寻找全部方案，输出最前面的三个方案，并输出方案总数。

完整规则与任务要求

处理本题时，必须同时满足下列全部要求，不能只实现其中一部分：

• 在一个 $n\times n$ 棋盘上放置 $n$ 个皇后，要求每一行、每一列以及每一条与主对角线平行的斜线上至多有一个皇后。
• 用长度为 $n$ 的序列描述一个方案：。
• 第 $i$ 个数表示第 $i$ 行皇后所在的列。
• 请按字典序寻找全部方案，输出最前面的三个方案，并输出方案总数。
• 每一行与每一列恰好放一个皇后，每条对角线至多一个。
• 方案用每一行皇后所在列组成的序列表示。
• 按字典序输出前三个方案，最后输出方案总数。

程序应完整读取“输入格式”中规定的所有数据，并严格按照“输出格式”给出结果。题目中的区间端点、编号起点、排序优先级、同分处理、空结构处理、取模方式和特殊字符串，均以本题面明确写出的规则为准。

所有算法还必须覆盖“数据范围”中的最小规模、最大规模及边界情况，不能只针对样例或小数据。

输入格式

输入一行一个正整数 $n$。

输出格式

前三行分别输出字典序最小的三个方案，方案中的列号以空格分隔。最后一行输出合法方案总数。

输入输出样例

样例 1

6

2 4 6 1 3 5
3 6 2 5 1 4
4 1 5 2 6 3
4

样例说明

样例棋盘大小为 $6$，输出前三个字典序最小的合法方案，并在最后一行给出全部 $4$ 个方案。

数据范围

$6\le n\le13$。在此范围内至少存在三个合法方案。

边界与子任务说明

• 测试数据可能覆盖题面允许的最小值、最大值、重复值、空结果、无解或极端结构等边界情形。
• 若原题未额外列出分档子任务，则所有测试点统一遵守上述完整数据范围；若题面已经列出比例或分档条件，则这些条件均应视为题面的一部分。
• 不能根据公开样例推断未写出的额外限制。

本题面依据洛谷 P1219 的公开题目信息重新整理，为内容完整的非逐字重述版。