[DSA][Backtracking] N-Queens

Leetcode 51

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, where 'Q' and '.' both indicate a queen and an empty space, respectively.

[What can I ask?]
- Does a valid solution always exist? If no solution exists, should we return an empty list? YES

[Key Idea]
- Use backtracking to place the pieces after checking for conflicts between queens.

[Solution 1] Backtracking

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        res, tmp = [], []
        
        def coordToStr(res):
            strRes = []
            for coord in res:
                tmpRes = []
                for i, j in coord:
                    tmpRes.append("." * j + "Q" + "." * (n - j - 1))
                strRes.append(tmpRes)
            return strRes

        def noAttack(x, y):
            for i, j in tmp:
                if i == x or j == y:
                    return False
                
                if abs((i - x) / (j - y)) == 1:
                    return False
            return True

        def dfs(cnt,i):
            if cnt == n:
                res.append(tmp.copy())
                return
            
            for j in range(n):
                if noAttack(i, j):
                    tmp.append((i, j))
                    dfs(cnt + 1, i + 1)
                    tmp.pop()
            return
        
        for j in range(n):
            tmp.append((0, j))
            dfs(1, 1)
            tmp.pop()
        
        return coordToStr(res)

This solution is a straightforward backtracking approach that directly implements the problem conditions without any additional optimizations.

In the N-Queens problem, no two queens can be placed in the same row, so the search proceeds by placing exactly one queen in each row. For the current row, we iterate through columns 0 to n−1 and check whether a queen can be placed in that position. If the position is valid, we proceed to the next row using DFS.

During the DFS process, we check whether the new queen conflicts with any previously placed queens. To do this, we iterate over all existing queen positions and verify three conditions:

1. Whether it is in the same row.
2. Whether it is in the same column.
3. Whether the absolute difference between the rows equals the absolute difference between the columns (i.e., whether they are on the same diagonal).

If any of these conditions are true, the queen cannot be placed at that position. This process continues recursively. When the number of placed queens (cnt) reaches n, it means all n queens have been placed validly, so we store the current list of coordinates as a solution.

Get Woolaf's Techscope’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

After that, we backtrack by removing the most recently added coordinate and continue searching the next column in the same row.

Once all possibilities have been explored, the stored coordinate solutions are converted into a board representation for each row, using "Q" for a queen and "." for an empty space, and returned as the final result.

[Solution 2] Backtracking + Optimization

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        res = []
        board = [-1] * n # board[row] = col

        cols = set()
        diag1 = set() # row - col
        diag2= set() # row + col

        def dfs(row):
            if row == n:
                res.append(
                    ["." * board[i] + "Q" + "." * (n - board[i] - 1) for i in range(n)]
                )
                return
            
            for col in range(n):
                if col in cols or (row - col) in diag1 or (row + col) in diag2:
                    continue

                board[row] = col
                cols.add(col)
                diag1.add(row - col)
                diag2.add(row + col)

                dfs(row + 1)

                cols.remove(col)
                diag1.remove(row - col)
                diag2.remove(row + col)
        
        dfs(0)
        
        return res

In the first solution, to check for conflicts, we iterate through all previously placed queens each time. This raises several questions:

• Can we determine conflicts more efficiently without iterating through all queens every time?
• Since in the DFS structure each queen is always placed in a different row, is it necessary to check the row?
• Is there a faster way to detect diagonal conflicts?

Based on these observations, we can use set data structures to determine queen conflicts in O(1) time.

First, since the DFS always proceeds to the next row, there is no possibility of placing multiple queens in the same row. Therefore, conflict checks only need to consider columns and the two diagonals.

For column conflicts, instead of iterating over all placed queens’ column coordinates, we can store the columns that are already used in a set and simply check whether the current column exists in the set. This allows column conflict checks in O(1) time.

Diagonal conflicts can be optimized similarly. Two queens are on a diagonal with slope +1 if row1 − row2 = col1 − col2, row1 − col1 = row2 − col2 which can be rewritten as row − col being the same for both queens. For a diagonal with slope −1, row1 − row2 = -col1 + col2, row1 + col1 = row2 + col2 implies row + col is the same. By representing each diagonal using row − col and row + col and storing the used values in sets, diagonal conflicts can also be checked in O(1) time.

Finally, the process of converting coordinates into a string-based board can also be simplified. By storing the column index for each row as board[row] = col, we can generate each row of the board directly with "." * board[row] + "Q" + "." * (n - board[row] - 1) without any additional iteration over coordinates.

⏱️ Time Complexity
Since DFS is performed n times and in each row we choose columns such that no two queens share the same column, the number of available columns decreases as we go deeper. This structure is similar to a permutation search, and in the worst case, the time complexity is O(n!).

🧠 Space Complexity
The set structures and the board array each require at most n space. However, the final result res stores all possible board configurations, each of size n × n. Therefore, the overall space complexity is O(n²).