1var assert = require('assert');
2
3function solveNQueens(n) {
4  var board = new Array(n);
5  // Setup thhe board
6  for (i = 0; i < n; i++) {
7    board[i] = new Array(n);
8    for (j = 0; j < n; j++) {
9      board[i][j] = '.';
10    }
11  }
12
13  res = recursiveSolveNQueens([], board, 0);
14  console.log('board', res);
15  return res;
16}
17
18function copyBoard(board) {
19  let newBoard = new Array(board.length);
20  for (i = 0; i < board.length; i++) {
21    newBoard[i] = new Array(board[i].length);
22    for (j = 0; j < board[i].length; j++) {
23      newBoard[i][j] = board[i][j];
24    }
25  }
26  return newBoard;
27}
28
29function recursiveSolveNQueens(res, board, row, cols = []) {
30  if (row === board.length) {
31    // A solution! add a copy of it
32    res.push(copyBoard(board));
33    return res;
34  }
35  for (col = 0; col < board.length; col++) {
36    if (validateBoard(board, row, col)) {
37      // Put a queen and move forward
38      board[row][col] = 'Q';
39      cols.push(col);
40      res = recursiveSolveNQueens(res, board, row + 1, cols);
41      col = cols.pop();
42      // Now backtrack
43      board[row][col] = '.';
44    }
45    // Return all the collected good board copies
46  }
47  return res;
48}
49
50function validateBoard(board, row, col) {
51  // Check if row is valid
52  for (row_it = 0; row_it < row; row_it++) {
53    if (board[row_it][col] === 'Q') {
54      return false;
55    }
56  }
57
58  // Check if first diagonal is valid
59  for (
60    row_it = row - 1, col_it = col - 1;
61    row_it >= 0 && col_it >= 0;
62    row_it--, col_it--
63  ) {
64    if (board[row_it][col_it] === 'Q') {
65      return false;
66    }
67  }
68
69  // Check if second diagonal is valid
70  for (
71    row_it = row - 1, col_it = col + 1;
72    row_it >= 0 && col_it < board.length;
73    row_it--, col_it++
74  ) {
75    if (board[row_it][col_it] === 'Q') {
76      return false;
77    }
78  }
79
80  // Everything is valid, so return true
81  return true;
82}
83
84// test cases
85
86try {
87  res = solveNQueens(4);
88  shouldbe = [
89    [
90      ['.', 'Q', '.', '.'],
91      ['.', '.', '.', 'Q'],
92      ['Q', '.', '.', '.'],
93      ['.', '.', 'Q', '.'],
94    ],
95    [
96      ['.', '.', 'Q', '.'],
97      ['Q', '.', '.', '.'],
98      ['.', '.', '.', 'Q'],
99      ['.', 'Q', '.', '.'],
100    ],
101  ];
102
103  assert.deepEqual(shouldbe, res);
104
105  console.log('PASSED: ' + 'With n=4, there should be 2 solution boards.');
106} catch (err) {
107  console.log(err);
108}
109
110try {
111  res = solveNQueens(6);
112  shouldbe = [
113    [
114      ['.', 'Q', '.', '.', '.', '.'],
115      ['.', '.', '.', 'Q', '.', '.'],
116      ['.', '.', '.', '.', '.', 'Q'],
117      ['Q', '.', '.', '.', '.', '.'],
118      ['.', '.', 'Q', '.', '.', '.'],
119      ['.', '.', '.', '.', 'Q', '.'],
120    ],
121    [
122      ['.', '.', 'Q', '.', '.', '.'],
123      ['.', '.', '.', '.', '.', 'Q'],
124      ['.', 'Q', '.', '.', '.', '.'],
125      ['.', '.', '.', '.', 'Q', '.'],
126      ['Q', '.', '.', '.', '.', '.'],
127      ['.', '.', '.', 'Q', '.', '.'],
128    ],
129    [
130      ['.', '.', '.', 'Q', '.', '.'],
131      ['Q', '.', '.', '.', '.', '.'],
132      ['.', '.', '.', '.', 'Q', '.'],
133      ['.', 'Q', '.', '.', '.', '.'],
134      ['.', '.', '.', '.', '.', 'Q'],
135      ['.', '.', 'Q', '.', '.', '.'],
136    ],
137    [
138      ['.', '.', '.', '.', 'Q', '.'],
139      ['.', '.', 'Q', '.', '.', '.'],
140      ['Q', '.', '.', '.', '.', '.'],
141      ['.', '.', '.', '.', '.', 'Q'],
142      ['.', '.', '.', 'Q', '.', '.'],
143      ['.', 'Q', '.', '.', '.', '.'],
144    ],
145  ];
146
147  assert.deepEqual(shouldbe, res);
148
149  console.log('PASSED: ' + 'With n=6, there should be 4 solution boards.');
150} catch (err) {
151  console.log(err);
152}