--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:

You should have a function named dfs_n_queens.
The function should accept exactly one argument: an integer n.
If n is less than 1, the function should return an empty list ([]).
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 dfs_n_queens that takes one argument.

({ test: () => runPython(`
  import inspect
  assert inspect.isfunction(dfs_n_queens)
  sig = inspect.signature(dfs_n_queens)
  assert len(sig.parameters) == 1
`) })

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

({ test: () => runPython(`
  assert dfs_n_queens(0) == []
  assert dfs_n_queens(-1) == []
  assert dfs_n_queens(-5) == []
`) })

The function should return a list of solutions, where each solution is a list of length n.

({ test: () => runPython(`
  result = dfs_n_queens(4)
  assert isinstance(result, list)
  for solution in result:
    assert isinstance(solution, list)
    assert len(solution) == 4
`) })

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

({ test: () => runPython(`
  assert dfs_n_queens(1) == [[0]]
`) })

dfs_n_queens(2) should return [].

({ test: () => runPython(`
  assert dfs_n_queens(2) == []
`) })

dfs_n_queens(3) should return [].

({ test: () => runPython(`
  assert dfs_n_queens(3) == []
`) })

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

({ test: () => runPython(`
  assert dfs_n_queens(4) == [[1, 3, 0, 2], [2, 0, 3, 1]]
`) })

dfs_n_queens(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]].

({ test: () => runPython(`
  assert dfs_n_queens(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]]
`) })

len(dfs_n_queens(5)) should be 10.

({ test: () => runPython(`
  assert len(dfs_n_queens(5)) == 10
`) })

len(dfs_n_queens(8)) should be 92.

({ test: () => runPython(`
  assert len(dfs_n_queens(8)) == 92
`) })

dfs_n_queens should return the correct result.

({ test: () => runPython(`
  assert len(dfs_n_queens(7)) == 40
  assert dfs_n_queens(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--

def dfs_n_queens(n):
    if n < 1:
        return []

    results = []

    def is_safe(queens, row, col):
        for r, c in enumerate(queens):
            if c == col or abs(row - r) == abs(col - c):
                return False
        return True

    def dfs(queens):
        row = len(queens)
        if row == n:
            results.append(queens[:])
            return
        for col in range(n):
            if is_safe(queens, row, col):
                queens.append(col)
                dfs(queens)
                queens.pop()

    dfs([])
    return results

Implement the N-Queens Algorithm

--description--

--hints--

--seed--

--seed-contents--

--solutions--