高碑店住房和城乡建设局网站,wordpress技术站主题,网站全面详细创建步骤,php网站栏目 添加和删除文章目录 题目描述测试样例算法原理算法实现参考资料 题目描述
在nxn格的棋盘上放置彼此不受攻击的n格皇后。按照国际象棋的规则#xff0c;皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在nxn格的棋盘上放置n个皇后#xff0c;任何2个皇后不放在同… 文章目录 题目描述测试样例算法原理算法实现参考资料 题目描述
在nxn格的棋盘上放置彼此不受攻击的n格皇后。按照国际象棋的规则皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在nxn格的棋盘上放置n个皇后任何2个皇后不放在同一行或同一列或同一斜线上。
当n6时一个如下的 6×6 的跳棋棋盘 上面的布局可以用序列 2 4 6 1 3 5 来描述第 i 个数字表示在第 i 行的相应位置有一个棋子。这只是棋子放置的一个解。请编一个程序找出所有棋子放置的解。并把它们以上面的序列方法输出解按字典顺序排列。请输出前三个解。最后一行是解的总个数。
测试样例
输入 6 输出 2 4 6 1 3 5 3 6 2 5 1 4 4 1 5 2 6 3 4 算法原理 使用回溯法对解空间进行深度优先搜索遍历同时要满足规则任何两个皇后不放在同一行或同一列或同一斜线上为节省时间我创建了四个数组x[1000], y[1000], zr[1000], zl[1000]分别存储横轴、纵轴、左对角线、右对角线上是否已被占用的信息。其中x[i]j表示在第i行第j个位置放置一个皇后方便输出结果y[j]1表示第j列已被占用zr[i - j n]1表示这条从左上到右下的对角线已被占用所有处于同一条左上到右下对角线上元素的横坐标减纵坐标都相同为了让索引为正所以加nzl[ij]1表示这条从右上到左下的对角线已被占用所有处于同一条右上到左下对角线上元素的横坐标加纵坐标都相同。
算法实现
#includebits/stdc.h
using namespace std;int n, num 0;
int x[1000], y[1000], zr[1000], zl[1000];
void print()
{if (num 3){for (int i 1; i n; i)cout x[i] ;cout endl;}num;
}
void dfs(int i)
{if (i n){print();return;}else{for (int j 1; j n; j){if ((!y[j]) (!zr[i - j n]) (!zl[i j])){x[i] j;//i行第j个y[j] 1;zr[i - j n] 1;zl[i j] 1;dfs(i 1);//递归y[j] 0;zr[i - j n] 0;zl[i j] 0;}}}
}
int main()
{cin n;dfs(1);cout num;return 0;
}参考资料
回溯法之n皇后问题总结_用回溯法求解n皇后问题的思路
