算法设计与分析中使用分支限界法来解决n皇后问题

一、问题描述

_问题描述：在n×n格的棋盘上安排n个互不攻击的皇后。根据国际象棋规则，皇后能够攻击与其处于同一行、同一列或同一斜线上的棋子。因此，n皇后问题可以转化为在n×n的棋盘上布置n个皇后，确保任意两个皇后都不位于同一行、同一列或同一斜线上。

_算法设计：构建一种基于队列式分支限界法的算法，用于求解在n×n的棋盘上放置互不攻击的n个皇后的一种可行方案。

*数据输入：输入数据来源于文件input.txt。文件第一行包含一个正整数n。

*结果输出：将计算得到的一个互不攻击的n个皇后的放置方案写入文件output.txt。文件第一行展示该放置方案的具体内容。

输入文件：

input.txt

5

output.txt

1 3 5 2 4

二、问题分析
1.题目分析：

对于每一个可能的放置位置而言，需要判断四个方向是否存在其他皇后。这四个方向包括行列以及两个对角线方向（45度和135度）。

行：每一行只能放置一个皇后，当最后一个皇后被成功放置于最后一行的合适位置时，算法终止。

列：判断是否在同一列只需比较列坐标j是否相同即可。

45度斜线和135度斜线：约束条件为当前棋子与已放置好的棋子之间不能满足行差绝对值等于列差绝对值的情况。若出现这种情况，则说明两者位于同一条斜线上。

2.算法选择：

采用分支限界法来处理该问题。此问题具备两种树