51. N-Queens

Then-queens puzzle is the problem of placingnqueens on ann×nchessboard such that no two queens attack each other.

Given an integern, return all distinct solutions to then-queens puzzle.

Each solution contains a distinct board configuration of then-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..",//Solution1"...Q","Q...","..Q."],["..Q.",//Solution2"Q...","...Q",".Q.."]]

题目大意：

给定一个n*n的棋盘，在棋盘里放入n个Q，要求每一行，每一列都只有一个Q，而且每个Q的对角线上只能有一个Q。

思路：

这是一个典型的回溯问题。一条路走到黑，走到黑了退回来一步，然后再走，直到走通一条路。退回来继续寻找其他出路。

解决这个问题需要解决几个关键点：

1.关于保存一个可行路线的数据结构的选择

保存一个可行路线的时候，选择数据结构时选择一个2维数组还是什么这里需要动脑筋了，最后衡量，选择了一维数组。

比如说4-Queue时一个合法路线为

[".Q..",//Solution1"...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<int> &a)

curIndex表示当前要插入的元素在合法数组中的下标，也就是行。val是要插入的列值。n是有多少个Queue，a是保存临时合法路线的一个数组。

判断a[i] == val 相等说明该列重复。

对角线的斜率为1或-1，所以如果 |val - a[i]| / |cur - i| == 1，那么说明在同一对角线上。

3.将合法的路径一个一个的放入结果临时数组中。从结果临时数组转换成结果数组。

代码如下：

classSolution{public://判断当前要插入的值val在这个位置curIndex是否合法boolisValid(intcurIndex,intval,intn,vector<int>&a){if(curIndex<n){for(inti=curIndex-1;i>=0;--i){if(a[i]==val)//判断列上是否有重复的returnfalse;}for(inti=curIndex-1;i>=0;--i){if(abs(val-a[i])==(curIndex-i))//判断斜线上是否有重复的{returnfalse;}}returntrue;}returnfalse;}voidPutQueens(intval,vector<int>&a)//将合法的值放入当前临时结果数组{a.push_back(val);}//start开始的行数，也就是第start+1个Queue的放置voidsolveNQueensToIntVector(intstart,intn,vector<int>&cur,vector<vector<int>>&result)//先转换成int来处理{if(cur.size()==n){result.push_back(cur);return;}if(start==n)return;//典型的回溯套路for(inti=0;i<n;i++){if(!isValid(cur.size(),i,n,cur))continue;vector<int>temp(cur);//保存变化前的vectorPutQueens(i,cur);solveNQueensToIntVector(start+1,n,cur,result);cur.swap(temp);}}vector<vector<string>>solveNQueens(intn){vector<int>cur;vector<vector<int>>tempResult;vector<vector<string>>result;solveNQueensToIntVector(0,n,cur,tempResult);//vector<vector<int>>tempResult转换成目标结果resultfor(inti=0;i<tempResult.size();i++){vector<string>floorVector;stringfloor;for(intj=0;j<tempResult[i].size();j++){for(intk=0;k<tempResult[i][j];k++){floor+=".";}floor+="Q";for(intk=tempResult[i][j]+1;k<n;k++){floor+=".";}floorVector.push_back(floor);floor.clear();}result.push_back(floorVector);floorVector.clear();}returnresult;}};

本题总结：

回溯问题在N-Queue这道题中体现的十分明显。

（3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。

回溯就是让计算机自动的去搜索，碰到符合的情况就结束或者保存起来，在一条路径上走到尽头也不能找出解，就回到原来的岔路口，选择一条以前没有走过的路继续探测，直到找到解或者走完所有路径为止。就这一点，回溯和所谓的DFS（深度优先搜索）是一样的。那现在的关键是，怎么实现搜索呢？回溯既然一般使用递归来实现，那个这个递归调用该如何来写呢？我的理解就是，先判断这一次试探是否有效，如果有效则加入这个元素，然后进行下一次递归，递归后恢复加入这个合法元素之前的状态，进行下一次循环；如果无效则直接进行下一次循环。

2016-08-15 15:53:37