JavaScript实现N皇后问题算法谜题解答_javascript技巧
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了JavaScript实现N皇后问题算法谜题解答_javascript技巧,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1937字,纯文字阅读大概需要3分钟。
内容图文
![JavaScript实现N皇后问题算法谜题解答_javascript技巧](/upload/InfoBanner/zyjiaocheng/324/1520791647b640829a6649435fe24a56.jpg)
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
内容总结
以上是互联网集市为您收集整理的JavaScript实现N皇后问题算法谜题解答_javascript技巧全部内容,希望文章能够帮你解决JavaScript实现N皇后问题算法谜题解答_javascript技巧所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。