8皇后问题--回溯法 （循环递归）
N皇后问题
问题描述：
N皇后问题是一个经典的问题，在一个N*N的棋盘上放置N个皇后，每行一个并使其不能互相攻击（同一行、同一列、同一斜线上的皇后都会自动攻击）
问题描述：
N皇后问题是一个经典的问题，在一个N*N的棋盘上放置N个皇后，每行一个并使其不能互相攻击（同一行、同一列、同一斜线上的皇后都会自动攻击）
1.由于每个棋子不可能同行，因此可以理解为从棋盘每行拿个棋子出来
2.由于每列棋子也不相同，因此没有同一个数字可以在一个列
3.综合1,2，问题转化为给[0-7]做全排列，然后满足没有两个数字在同一个斜线
4.根据斜率公式 (x1-x2)/(y1-y2)，因此根据这个条件排出同线的组合
5.余下的组合即为每行棋子的列位置，索引，就是行号
var MAX = 8;
var Ann = function a(arr){
if(arr.length == 1){return arr;}
var rr = new Array();
for(var i = 0; i<arr.length;i++){
//get a copy
var ar = new Array();
for(var j = 0; j < arr.length;j++){ar[j] = arr[j];}
//assume i
var current = ar[i];
ar.splice(i,1);
var childRet = a(ar);
for(var k = 0 ;k < childRet.length;k++){
var str = (current + "," + childRet[k]);
if(str.length != 2 * MAX-1 || !sameLine(str)){
rr.push(str);
}
}
}
return rr;
}
var initArr = new Array();
for(var i = 0;i < MAX; i++){initArr.push(i);}
var ret = Ann(initArr);
for(var i = 0;i < ret.length;i++){
outRet(ret[i]);
}
var count = 0;
function outRet(r) {
count = count + 1;
console.log("==============" + "," + count.toString());
var a = r.split(',');
for(var i = 0;i < MAX; i++){
var aa = new Array();
for(var j = 0;j < MAX; j++){
aa.push(0);
}
aa[a[i]] = 1;
console.log(aa);
}
}
function sameLine(str){
var arr = str.split(',');
for(var i = 0;i < arr.length; i++){
for(var j = 0;j < arr.length; j++){
if(i!=j&&Math.abs(i-j) == Math.abs(arr[i]-arr[j])){return true;}
}
}
return false;
}