时间:2021-05-26
谜题
N皇后问题。将N个皇后放置在NxN的国际象棋棋盘上,其中没有任何两个皇后处于同一行、同一列或同一对角线上,以使得它们不能互相攻击。
策略
回溯法。
JavaScript解
以8皇后问题为例:
复制代码 代码如下:
/**
* Created by cshao on 12/28/14.
*/
function getNQueens(order) {
if (order < 4) {
console.log('N Queens problem apply for order bigger than 3');
return;
}
var nQueens = [];
var backTracking = false;
rowLoop:
for (var row=0; row<order; row++) {
if (nQueens[row] === undefined) {
nQueens[row] = [];
}
for (var col=0; col<order; col++) {
if (nQueens[row][col] === 0) {
continue;
} else if (backTracking && nQueens[row][col] == 1) {
if (col === order-1) {
resetRow(nQueens, order, row);
row = row - 2;
continue rowLoop;
}
nQueens[row][col] = 0;
backTracking = false;
continue;
}
nQueens[row][col] = 1;
if (isQueenValid(nQueens, row, col)) {
continue rowLoop;
} else if (col == order-1) {
backTracking = true;
resetRow(nQueens, order, row);
row = row - 2;
continue rowLoop;
} else {
nQueens[row][col] = 0;
continue;
};
}
}
return nQueens;
}
function resetRow(nQueens, order, row) {
for (var col=0; col<order; col++) {
nQueens[row][col] = undefined;
}
}
function isQueenValid(nQueens, row, col) {
for (var i=0; i<col; i++) {
if (nQueens[row][i] == 1) {
return false;
}
}
for (var j=1; j<row+1; j++) {
if (nQueens[row-j][col]==1 || (nQueens[row-j][col-j]!=undefined && nQueens[row-j][col-j]==1) || (nQueens[row-j][col+j]!=undefined && nQueens[row-j][col+j]==1)) {
return false;
}
}
return true;
}
function printQueens(queens) {
for (var row=0; row<queens.length; row++) {
var rowText = '';
for (var col=0; col<queens.length; col++) {
if (queens[row][col]===undefined) {
queens[row][col] = 0;
}
rowText = rowText + queens[row][col] + ' ';
}
console.log(rowText);
}
}
var queens = getNQueens(8);
printQueens(queens);
结果
复制代码 代码如下:
1 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 1
0 0 0 0 0 1 0 0
0 0 1 0 0 0 0 0
0 0 0 0 0 0 1 0
0 1 0 0 0 0 0 0
0 0 0 1 0 0 0 0
声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。
本文实例讲述了PHP基于回溯算法解决n皇后问题的方法。分享给大家供大家参考,具体如下:这里对于n皇后问题就不做太多的介绍,相关的介绍与算法分析可参考前面一篇C+
N皇后问题问题描述:在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题
关于八皇后问题的JavaScript解法,总觉得是需要学习一下算法的,哪天要用到的时候发现真不会就尴尬了背景八皇后问题是一个以国际象棋为背景的问题:如何能够在8
本文实例展示了C++实现八皇后问题的方法,是数据结构与算法中非常经典的一个算法。分享给大家供大家参考之用。具体方法如下:一般在八皇后问题中,我们要求解的是一个8
本文实例讲述了C语言八皇后问题解决方法。分享给大家供大家参考,具体如下:1.概述:八皇后问题是一个以国际象棋为背景的问题:如何能够在8×8的国际象棋棋盘上放置八