N Queens 問題アルゴリズムの JavaScript 実装パズルソリューション_JavaScript スキル

パズル

N クイーンの問題。 NxN チェスボード上に N 個のクイーンを配置します。このとき、互いに攻撃できないように、同じ行、列、または対角線上に 2 つのクイーンが存在しません。

戦略

バックトラッキング方法。

JavaScript ソリューション

8 クイーンズ問題を例に挙げます:

コードをコピー コードは次のとおりです:

/**
 * 2014 年 12 月 28 日に cshao によって作成されました。
 */

関数 getNQueens(order) {
if (順序 console.log('3 を超える注文には N クイーンズ問題が適用されます');
戻る;
}

var nQueens = [];
var backTracking = false;
行ループ:
for (var row=0; row If (nQueens[row] === 未定義) {
nQueens[行] = [];
}

for (varcol=0;col If (nQueens[row][col] === 0) {
続行;
} else if (backTracking && nQueens[row][col] == 1) {
If (col === order-1) {
resetRow(nQueens, order, row);
行 = 行 - 2;
continue rowLoop;
}
nQueens[行][列] = 0;
backTracking = false;
続行;
}

nQueens[行][列] = 1;
If (isQueenValid(nQueens, row,col)) {
rowLoop を継続します;
} else if (col == order-1) {
backTracking = true;
resetRow(nQueens, order, row);
行 = 行 - 2;
rowLoop を継続します;
} else {
nQueens[行][列] = 0;
続行;
};
}
}

nQueens を返します;
}

関数resetRow(nQueens, order, row) {
for (varcol=0;col nQueens[行][列] = 未定義;
}
}

関数 isQueenValid(nQueens, row,col) {
for (var i=0; i

If (nQueens[row][i] == 1) {
false を返します;
}
}
for (var j=1; j if (nQueens[row-j][col]==1 || (nQueens[row-j][col-j]!=未定義 && nQueens[row-j][col-j]==1) || ( nQueens[row-j][col j]!=未定義 && nQueens[row-j][col j]==1)) {
false を返します;
}
}
true を返します;
}

関数 printQueens(queens) {
for (var row=0; row var rowText = '';
for (varcol=0;col If (queens[row][col]===未定義) {
クイーン[行][列] = 0;
}
rowText = rowText queens[row][col] ' ';
}
console.log(rowText);
}
}

var queens = getNQueens(8);
printQueens(クイーン);

結果

コードをコピー コードは次のとおりです:

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