首页 > 代码库 > N皇后问题--回溯法 （循环递归）

N皇后问题--回溯法 （循环递归）

2024-07-10 07:57:39   220人阅读

N皇后问题


问题描述：
N皇后问题是一个经典的问题，在一个N*N的棋盘上放置N个皇后，每行一个并使其不能互相攻击（同一行、同一列、同一斜线上的皇后都会自动攻击）


思路 （回溯法，循环递归）：
0. 初始化棋盘（全部为0）
1. 依次将第一列棋子置为1
2. 放完棋子执行横向，纵向，斜向的update，把不能放棋子的位置置为2
3. 从第二列棋子开始，递归执行
4. 执行到最后一列，退出递归
5. 执行第一列的第二个棋子


实现：



var N = 4;


Array.prototype.count = function(c){
var count = 0;
for(var i = 0; i< this.length; i++){if(c(this[i])){count ++;}}
return count ;
}


//init map 
var arr = new Array();
for(var i = 0 ;i < N;i ++){
var arr1 = new Array();
for(var j = 0;j < N; j++){arr1.push(0);}
arr.push(arr1);
}


var sln = new Array();
var queen = function q(col,done){


//find a vacancy
var zeroIndex = 0;


while(zeroIndex < N && arr[zeroIndex][col] != 0){zeroIndex ++;}


if(zeroIndex < N){
arr[zeroIndex][col] = 1;
//update positions
updatePosition(zeroIndex,col);
done ++;
}


if(col == N ){return ;}


/* debugging 
console.log("arr : ");
for(var i = 0 ;i < arr.length; i++){
console.log (arr[i]);
}
*/


if(done == N-1){
var ar = new Array();
for(var i = 0 ;i < arr.length; i++){
var ar1 = new Array();
for(var j = 0;j < arr[i].length; j++){
ar1.push(arr[i][j]);
arr[i][j] = 0;
}
ar.push(ar1);
}
sln.push(ar);
}


col ++;
q(col,done);


}


var updatePosition = function (r,c){


// hor
for(var i = 0 ;i < c; i++){if(arr[r][i] == 0) {arr[r][i] = 2;}}
for(var i = c ;i < N; i++){if(arr[r][i] == 0) {arr[r][i] = 2;}}


//ver
for(var i = 0 ;i < r; i++){if(arr[i][c] == 0) {arr[i][c] = 2;}}
for(var i = r ;i < N; i++){if(arr[i][c] == 0) {arr[i][c] = 2;}}


//r+,c+; r-,c-
for(var i = r,j = c;i < N && j < N; i++, j++){if(arr[i][j] == 0){arr[i][j] = 2;}}
for(var i = r,j = c;i >=0 && j >= 0; i--, j--){if(arr[i][j] == 0){arr[i][j] = 2;}}


//r+,c-;r-,c+
for(var i = r,j = c;i < N && j >= 0; i++, j--){if(arr[i][j] == 0){arr[i][j] = 2;}}
for(var i = r,j = c;i >=0 && j < N; i--, j++){if(arr[i][j] == 0){arr[i][j] = 2;}}


}


for(var i = 0 ;i < N; i++){
arr[i][0] = 1;
updatePosition(i,0);
queen(1,0);
//console.log("================================");
for(var j = 0; j < arr.length; j++){for(var k = 0 ;k  <arr[j].length; k++){arr[j][k] = 0;}}
}


console.log("for " + N + " - " + N + " queen , solutions : ") ;
for(var i = 0 ; i< sln.length ;i++){
console.log("=========sln : " + (i+1) + "====================");
for(var j = 0; j < sln[i].length; j++){
console.log(sln[i][j].join(" "));
}


}


联系
我们