-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy path8Queens.js
62 lines (56 loc) · 1.23 KB
/
8Queens.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
let solutionCount = 0;
function countPrint() {
return ++solutionCount;
}
function buildArrs() {
let arrs = [];
for (let i=8; i>0; i--) {
let arr = [];
for (let j=8; j>0; j--) {
arr.push(0);
}
arrs.push(arr);
}
return arrs;
}
function printArrs(arrs) {
console.log("------------------------------ count=", countPrint());
for (let i=0; i<arrs.length; i++) {
let arr = arrs[i];
let row = arr.map(item => {
return !!item ? ' ● ' : ' ○ ';
}).join("");
console.log(row);
}
}
function isConflict(arrs, rowIndex, colIndex) {
const target = arrs[rowIndex][colIndex];
for (let i=rowIndex-1; i>=0; i--) {
let row = arrs[i];
let j = row.indexOf(1);
if (j==colIndex || (rowIndex-i == Math.abs(colIndex-j)))
return true;
}
return false;
}
function clearDirtyRow(row) {
row.fill(0);
}
function findQueens(arrs, rowIndex) {
if (rowIndex>=8) {
printArrs(arrs);
return;
}
for (let i=0; i<arrs[rowIndex].length; i++) {
if (!isConflict(arrs, rowIndex, i)) {
clearDirtyRow(arrs[rowIndex]);
arrs[rowIndex][i] = 1;
findQueens(arrs, rowIndex+1);
}
}
}
function start() {
let plate = buildArrs();
solutionCount = 0;
findQueens(plate, 0);
}