算法"/>
回溯算法
1.问题描述
四皇后问题：在4 ×4 的方格棋盘上放置4个皇后，使得没有两个皇后在同一行、同一列、也不在同一条45度的斜线上。问有多少种可能的布局？
解是4维向量
比如上面这个解<2,4,1,3> 分别表示圆圈的第2列、第4列等
还可以得到另一解 3,1,4,2> 表示把上面的图按照以下左右翻转得到的值
搜索空间：4叉树
- 每个结点都有4个儿子，分别代表选择1,2，3,4列的位置
- 第i层选择解向量中第i个分量的值
- 最深层的树叶是解，比如上图最深层的是《2,4,1,3》
- 按照深度优先的遍历树，找到所有的解
在回溯算法里采用的策略，搜索树的空间的一种搜索方法
对皇后一来说，有4种放法，可以放在第1，2，3，4列。对皇后二而言，如果皇后一放在了第1列，那皇后二只能放在第3，4列
更多推荐
回溯算法
发布评论