Start learning free

LESSON 265 OF 347 · BACKTRACKING

N Queens in C#: Backtracking with List<List<int>>

Practice O(n!) Read the full explanation

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle. You may return the answer in any order.

Each solution contains a distinct board configuration of the n-queens' placement, and is represented as an array containing the column for each row of the matrix.

 



Example:

Input: n = 4
Output: [[1, 3, 0, 2], [2, 0, 3, 1]]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above

 

Constraints:

  • 1 <= n <= 9


STEP 1 OF 15
    Ctrl + Enter to check

    C# · BACKTRACKING

    N Queens in C#, explained

    Problem overview

    The method SolveNQueens receives an integer n and must return every way to place n queens on an n by n chessboard so that no two queens attack each other. A queen attacks along its row, its column and both diagonals.

    Each solution is a List<int> that holds the column of the queen in each row: entry 0 is the column in row 0, entry 1 is the column in row 1, and so on, with columns counted from 0. The method returns a List<List<int>> of all such solutions, in any order.

    For n = 4 there are two solutions, [1, 3, 0, 2] and [2, 0, 3, 1]. In the first one the queens are at row 0 column 1, row 1 column 3, row 2 column 0 and row 3 column 2:

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

    Approach: place one queen per row and undo bad guesses

    A board with n queens and no two in the same row must have exactly one queen in each row. That removes one of the three attack rules and gives a natural plan: go row by row, and in each row try every column. If a queen at (row, col) is safe from the queens already placed above, place it and move on to the next row. When a row has no safe column, the recursion simply returns, and the previous row tries its next column. That is backtracking: choose, explore, then undo the choice.

    Checking safety only needs the queens in earlier rows, since later rows are still empty. A new queen at (row, col) conflicts with an earlier queen at (i, placement[i]) in two cases:

    • They share a column: placement[i] == col.
    • They share a diagonal: the distance between the rows equals the distance between the columns, so Math.Abs(row - i) == Math.Abs(col - placement[i]).

    Two queens are never in the same row, because each row receives exactly one.

    When row reaches n, all rows have a queen, and the current placement is a complete solution. It is copied into the result list.

    Step by step

    1. Create the result list in SolveNQueens: a List<List<int>> named placements.
    2. Create the working list, placement. It holds the columns chosen so far, one per row above the current one, and grows and shrinks as the recursion goes deeper and returns.
    3. Start at row 0 with Backtracking(n, 0, placement, placements).
    4. Return placements after the search.
    5. Declare Backtracking. Each call handles one row: it takes n, the current row, the working list and the result list.
    6. Record complete boards. If row == n, add a copy of placement to placements and return. A copy is essential, because the working list keeps changing afterwards.
    7. Try every column of the current row with a loop from 0 to n - 1.
    8. Test it with IsValid(placement, row, col).
    9. Choose: placement.Add(col) puts the queen on the board.
    10. Explore: Backtracking(n, row + 1, ...) fills the next row.
    11. Undo: placement.RemoveAt(placement.Count - 1) removes the queen again so the next column starts from the same state.
    12. Write IsValid. Loop over the earlier rows 0 to row - 1, return false on a column or diagonal clash, and return true if no clash is found.

    The solution in C#

    class Solution {
    public bool IsValid(List<int> placement, int row, int col) {
        for (int i = 0; i < row; i++) {
            if (placement[i] == col ||
                Math.Abs(row - i) == Math.Abs(col - placement[i])) {
                return false;
            }
        }
        return true;
    }

    public void Backtracking(int n, int row, List<int> placement, List<List<int>> placements) {
        if (row == n) {
            placements.Add(new List<int>(placement));
            return;
        }
        for (int col = 0; col < n; col++) {
            if (IsValid(placement, row, col)) {
                placement.Add(col);
                Backtracking(n, row + 1, placement, placements);
                placement.RemoveAt(placement.Count - 1);
            }
        }
    }

    public List<List<int>> SolveNQueens(int n) {
        List<List<int>> placements = new List<List<int>>();
        List<int> placement = new List<int>();
        Backtracking(n, 0, placement, placements);
        return placements;
    }
}

    The C# details worth a closer look:

    • List<T> is a reference type. Adding placement itself to placements would store the same object many times, and by the end all entries would show the same final (empty) list. new List<int>(placement) uses the copy constructor to take a snapshot.
    • RemoveAt versus Remove. RemoveAt(index) deletes the element at a position, and placement.Count - 1 is the last one. Remove(value) deletes the first element equal to a value, which is not what backtracking needs. For a List<int>, it would also be easy to confuse the two, because an index and a value are both int.
    • Counting and indexing. A List<T> uses Count for its size and an indexer placement[i] for access, unlike an array's Length. The indexer throws if i is out of range; IsValid stays within range because placement always has exactly row entries when row row is being tried.
    • Math.Abs. It takes the absolute value of an int, so the diagonal test doesn't care which queen is to the left.
    • The line break in the condition. A C# statement ends at the semicolon, so the || at the end of the first line simply continues the expression onto the next line.

    Complexity

    Time: exponential. Without any checks there would be n to the power n ways to choose a column in every row. The column check alone brings that down to at most n! placements, and the diagonal check prunes far more, because a bad queen stops its whole subtree at once. Each IsValid call costs O(n). No simple closed form exists for how many nodes the search visits, but for the limit of 9 in this lesson, it finishes quickly.

    Space: O(n) besides the output. The recursion is n calls deep and the working list holds at most n columns. The result itself holds one list of n numbers per solution.

    Edge cases and common mistakes

    • n = 1 has one solution, [0].
    • n = 2 and n = 3 have no solutions, so the method returns an empty list, not null.
    • Known counts. For n from 4 to 9 the number of solutions is 2, 10, 4, 40, 92 and 352. These are handy to test against.
    • Forgetting the undo step. Without RemoveAt, the working list keeps stale columns and every later row is checked against queens that are no longer there.
    • Storing the working list directly. As noted above, the result then contains copies of the same list reference.
    • A one-sided diagonal test. Checking row - i == col - placement[i] without Math.Abs only catches one diagonal direction.
    • Looping past row - 1 in IsValid. Rows from row down are empty. Reading placement[row] would throw an ArgumentOutOfRangeException.

    Testing

    • n = 4 gives [1, 3, 0, 2] and [2, 0, 3, 1], in this order, because columns are tried from 0 upward.
    • n = 1 gives [0].
    • n = 3 gives an empty list.
    • n = 8 gives 92 solutions.
    Keep going with C#About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free