八皇后算法解析

今天研究力扣的一道题死活写不出来对应的算法，没办法自己算法基础太差。于是看了下答案，发现使用什么回溯算法，菜鸟表示平时开发期间写的最复杂的程序就是写了两层for循环，已经很牛逼了有木有？这个回溯算法什么鬼？于是乎百度了下，算是了解了回溯算法是什么玩意儿。这里分析一波八皇后算法来加深一下理解。

八皇后算法描述如下：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法！

下面来分析一波，假设此时我们想要在黑色方块位置放置一个皇后： 如果一列一列的放置皇后的话，图中黑色位置能放置一个皇后的合法性条件为： 1、绿色线条经过的方格没有皇后 （不处于同一斜线） 2、红色线条经过的方格没有皇后 （不处于同一行） 3、紫色线条经过的方格没有皇后 （不处于同一斜线）

也就是说如果以黑色方块位置为参照原点：（0,0）坐标点，紫色和绿色两个线条分别是斜率为1和-1的两个函数，如下图： 紫色线所代表的函数是：y = -x; 绿色先所代表的函数是：y=x; （横坐标是列，纵坐标为行，注意行从上到下递增） 凡是位于这两条函数线上的位置（点）以及横坐标（说明位于同一行）都不能有皇后。

所以假设某一列皇后的位置用行来记录，比如queen[column] = row,意思是第column列的皇后的位置在第row行。 同行的逻辑很好判断，那么我们想要在黑色方块位置放置一个皇后，怎么判断前面几列是否在绿色线条和紫色线条上已经有了皇后呢？思路也很简单： 假设黑色方块的位置为n列，nRow行，假设位于m列的所在的行是否有皇后位于紫色线或者绿色上，那么就符合下面条件：

//假设此时即将在n列放置一个皇后,n>m

]//获取m列上皇后所在的行
int mRow = queen[m]
int nRow = queen[n]；
//行的差值
int rowDiff = nRow - mRow;

//列的差值
int columnDiff = n-m;

上面代码中 rowDiff的绝对值等于columnDiff的绝对值的话，说明点位于y=x或者y=-x的函数线上： 就说明此时黑色方块的位置是不能放置皇后的，因为在紫色或者绿色线上已经有了皇后。

那么用代码来（currentColumn,curreentRow）是否可以放置皇后的方法如下

	/**
     * 判断当（currentRow,currentColumn)是否可以放置皇后
     * @param currentColumn 
     * @return
     */
    public boolean isLegal(int currentRow,int currentColumn) {
    	//遍历前面几列
    	for(int preColumn=0;preColumn target) {
				break;
			}

			newCandidates.add(num);
		} // end for
         

通过上面的步骤我们拿到了一个从小到大排列的无重复数组newCandidates，数组中的元素都 target) { return res; } int len = candidates.length; // 取小于target的数 足证一个临时数组 for (int i = 0; i < len; i++) { int num = candidates[i]; if (num > target) { break; } temp.add(num); } // end for // find(res, new ArrayList(), temp, target, 0); return res; } public void find(List res, List tmp, List candidates, int target, int start){ //target==0.找到一个新的解 if (target == 0) { res.add(new ArrayList(tmp)); }else if(target>0){ for (int i = start; i < candidates.size(); i++) { int num = candidates.get(i); if(num