--description--

The N-Queens problem asks you to place N queens on an N×N chessboard so that no two queens attack each other (no two share a row, column, or diagonal).

For example, if there is a 4x4 board, one valid arrangement is:

[1, 3, 0, 2]

That means that in row 0, the queen is placed in column 1; in row 1, the queen is placed in column 3; in row 2, the queen is placed in column 0; and in row 3, the queen is placed in column 2.

Visually, this arrangement looks like:

. Q . .
. . . Q
Q . . .
. . Q .

Where Q represents a queen and . represents an empty square.

In this lab, you will implement the N-Queens problem solver using the depth-first search approach.

Objective: Fulfill the user stories below and get all the tests to pass to complete the lab.

User Stories:

1. You should have a function named dfsNQueens.
2. The function should accept exactly one argument: an integer n.
3. If n is less than 1, the function should return an empty array ([]).
4. The function should return a list of solutions; each solution is itself a list of length n, where the element at index i is the column index (0-based) of the queen in row i.

--hints--

You should have a function named dfsNQueens that takes one argument.

assert.isFunction(dfsNQueens);
assert.lengthOf(dfsNQueens, 1);

If n is less than 1, the function should return an empty array.

assert.sameDeepOrderedMembers(dfsNQueens(0), []);
assert.sameDeepOrderedMembers(dfsNQueens(-1), []);
assert.sameDeepOrderedMembers(dfsNQueens(-5), []);

The function should return an array of solutions, where each solution is an array of length n.

const output = dfsNQueens(4);
assert.isArray(output);
output.forEach(solution => {
    assert.isArray(solution);
    assert.lengthOf(solution, 4);
})

dfsNQueens(1) should return [[0]].

assert.sameDeepOrderedMembers(dfsNQueens(1), [[0]]);

dfsNQueens(2) should return [].

assert.sameDeepOrderedMembers(dfsNQueens(2), []);

dfsNQueens(3) should return [].

assert.sameDeepOrderedMembers(dfsNQueens(3), []);

dfsNQueens(4) should return [[1, 3, 0, 2], [2, 0, 3, 1]].

assert.sameDeepOrderedMembers(dfsNQueens(4), [[1, 3, 0, 2], [2, 0, 3, 1]]);

dfsNQueens(5) should return [[0, 2, 4, 1, 3], [0, 3, 1, 4, 2], [1, 3, 0, 2, 4], [1, 4, 2, 0, 3], [2, 0, 3, 1, 4], [2, 4, 1, 3, 0], [3, 0, 2, 4, 1], [3, 1, 4, 2, 0], [4, 1, 3, 0, 2], [4, 2, 0, 3, 1]].

assert.sameDeepOrderedMembers(dfsNQueens(5), [[0, 2, 4, 1, 3], [0, 3, 1, 4, 2], [1, 3, 0, 2, 4], [1, 4, 2, 0, 3], [2, 0, 3, 1, 4], [2, 4, 1, 3, 0], [3, 0, 2, 4, 1], [3, 1, 4, 2, 0], [4, 1, 3, 0, 2], [4, 2, 0, 3, 1]]);

dfsNQueens(5).length should be 10.

assert.lengthOf(dfsNQueens(5), 10);

dfsNQueens(8).length should be 92.

assert.lengthOf(dfsNQueens(8), 92);

dfsNQueens should return the correct result.

assert.lengthOf(dfsNQueens(7), 40);
assert.sameDeepOrderedMembers(dfsNQueens(6), [[1, 3, 5, 0, 2, 4], [2, 5, 1, 4, 0, 3], [3, 0, 4, 1, 5, 2], [4, 2, 0, 5, 3, 1]]);

--seed--

--seed-contents--

--solutions--

function dfsNQueens(n) {
  if (n < 1) return [];

  const results = [];

  function isSafe(queens, row, col) {
    for (let r = 0; r < queens.length; r++) {
      const c = queens[r];
      if (c === col || Math.abs(row - r) === Math.abs(col - c)) {
        return false;
      }
    }
    return true;
  }

  function dfs(queens) {
    const row = queens.length;
    if (row === n) {
      results.push(queens.slice());
      return;
    }

    for (let col = 0; col < n; col++) {
      if (isSafe(queens, row, col)) {
        queens.push(col);
        dfs(queens);
        queens.pop();
      }
    }
  }

  dfs([]);
  return results;
}