leetCode51.N-Queens|回溯问题(N皇后问题)|hard
51. N-Queens
创新互联建站是专业的叶集网站建设公司,叶集接单;提供网站建设、成都网站制作,网页设计,网站设计,建网站,PHP网站建设等专业做网站服务;采用PHP框架,可快速的进行叶集网站开发网页制作和功能扩展;专业做搜索引擎喜爱的网站,专业的做网站团队,希望更多企业前来合作!
The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.
Given an integer n, return all distinct solutions to the n-queens puzzle.
Each solution contains a distinct board configuration of the n-queens' placement, where 'Q'
and '.'
both indicate a queen and an empty space respectively.
For example,
There exist two distinct solutions to the 4-queens puzzle:
[ [".Q..", // Solution 1 "...Q", "Q...", "..Q."], ["..Q.", // Solution 2 "Q...", "...Q", ".Q.."] ]
题目大意:
给定一个n*n的棋盘,在棋盘里放入n个Q,要求每一行,每一列都只有一个Q,而且每个Q的对角线上只能有一个Q。
思路:
这是一个典型的回溯问题。一条路走到黑,走到黑了退回来一步,然后再走,直到走通一条路。退回来继续寻找其他出路。
解决这个问题需要解决几个关键点:
1.关于保存一个可行路线的数据结构的选择
保存一个可行路线的时候,选择数据结构时选择一个2维数组还是什么这里需要动脑筋了,最后衡量,选择了一维数组。
比如说4-Queue时一个合法路线为
[".Q..", // Solution 1 "...Q", "Q...", "..Q."],
那么它对应的1位数组为{1,3,0,2}
解释:
1是数组第0位,对应二维数组第0行,对应的值是1,表示在第0行时,第1列可以放Q。
3是数组第1位,对应二维数组第1行,对应的值是3,表示在第1行时,第3列可以放Q。
0是数组第2位,对应二维数组第3行,对应的值是0,表示在第2行时,第0列可以放Q。
2是数组第3位,对应二维数组第3行,对应的值是2,表示在第3行时,第2列可以放Q。
数组的下标为行,数组的元素值为列。通过行列来确定Q的位置。
2.关于如何判断要加入的元素是否为合法
要插入一个合法元素到合法位置上,需要判断是否合法,在这里使用了函数
bool isValid(int curIndex, int val ,int n, vector
curIndex表示当前要插入的元素在合法数组中的下标,也就是行。val是要插入的列值。n是有多少个Queue,a是保存临时合法路线的一个数组。
判断a[i] == val 相等说明该列重复。
对角线的斜率为1或-1,所以如果 |val - a[i]| / |cur - i| == 1,那么说明在同一对角线上。
3.将合法的路径一个一个的放入结果临时数组中。从结果临时数组转换成结果数组。
代码如下:
class Solution { public: //判断当前要插入的值val在这个位置curIndex是否合法 bool isValid(int curIndex, int val ,int n, vector&a) { if (curIndex < n ) { for (int i = curIndex - 1; i >= 0; --i) { if (a[i] == val)//判断列上是否有重复的 return false; } for (int i = curIndex - 1; i >= 0; --i) { if (abs(val - a[i]) == (curIndex - i))//判断斜线上是否有重复的 { return false; } } return true; } return false; } void PutQueens(int val , vector &a)//将合法的值放入当前临时结果数组 { a.push_back(val); } //start开始的行数,也就是第start+1个Queue的放置 void solveNQueensToIntVector(int start,int n, vector &cur, vector > &result)//先转换成int来处理 { if (cur.size() == n) { result.push_back(cur); return; } if (start == n) return; //典型的回溯套路 for (int i = 0; i < n; i++) { if (!isValid(cur.size(),i, n, cur)) continue; vector temp(cur);//保存变化前的vector PutQueens(i, cur); solveNQueensToIntVector(start + 1, n, cur, result); cur.swap(temp); } } vector > solveNQueens(int n) { vector cur; vector > tempResult; vector > result; solveNQueensToIntVector(0,n,cur,tempResult); //vector > tempResult 转换成 目标结果result for (int i = 0; i < tempResult.size(); i++) { vector floorVector; string floor; for (int j = 0; j < tempResult[i].size(); j++) { for (int k = 0; k < tempResult[i][j]; k++) { floor += "."; } floor += "Q"; for (int k = tempResult[i][j] + 1; k < n ; k++) { floor += "."; } floorVector.push_back(floor); floor.clear(); } result.push_back(floorVector); floorVector.clear(); } return result; } };
本题总结:
回溯问题在N-Queue这道题中体现的十分明显。
回溯法解题思路(1)针对所给问题,定义问题的解空间;
(2)确定易于搜索的解空间结构;
(3)以深度优先方式搜索解空间,并在搜索过程中用剪枝函数避免无效搜索。
回溯就是让计算机自动的去搜索,碰到符合的情况就结束或者保存起来,在一条路径上走到尽头也不能找出解,就回到原来的岔路口,选择一条以前没有走过的路继续探测,直到找到解或者走完所有路径为止。就这一点,回溯和所谓的DFS(深度优先搜索)是一样的。那现在的关键是,怎么实现搜索呢?回溯既然一般使用递归来实现,那个这个递归调用该如何来写呢?我的理解就是,先判断这一次试探是否有效,如果有效则加入这个元素,然后进行下一次递归,递归后恢复加入这个合法元素之前的状态,进行下一次循环;如果无效则直接进行下一次循环。
2016-08-15 15:53:37
名称栏目:leetCode51.N-Queens|回溯问题(N皇后问题)|hard
URL分享:http://myzitong.com/article/gohcco.html