-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathNQueensProblem.js
More file actions
48 lines (43 loc) · 1.24 KB
/
NQueensProblem.js
File metadata and controls
48 lines (43 loc) · 1.24 KB
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
function nQueen(N) {
// Return array of queen positions
}
function solve(firstQueen, size) {
// let queens = Array(size).fill(-1);
let queens = [];
let chessboard = Array(size).fill(0).map(a => Array(size).fill('.'));
visalizeQueens();
const result = tryQueen(firstQueen);
visalizeQueens();
console.log({ count });
console.log(result);
return queens;
function tryQueen(candidate) {
console.log({ candidate });
count++;
if (queens.some(queen => isConflict(candidate, queen))) {
return false;
}
queens.push(candidate);
const [x, y] = candidate;
const nextX = (x + 1) % size;
if (nextX == firstQueen[0]) {
return true;
}
for (let i = 0; i < size; i++) {
if (tryQueen([nextX, i])) {
return true;
}
}
queens.pop();
return false;
}
function isConflict([x1, y1], [x2, y2]) {
return y1 == y2 || x1 == x2 || y1 - x1 == y2 - x2 || y1 + x1 == y2 + x2;
}
function visalizeQueens() {
queens.forEach(([x, y]) => {
chessboard[y][x] = 'Q';
});
console.log(chessboard.map(a => a.join(' ')).join('\n'));
}
}