Start learning free

LESSON 291 OF 415 · BACKTRACKING

N Queens in Swift: Backtracking, One Queen per Row

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

    SWIFT · BACKTRACKING

    N Queens in Swift, explained

    Problem overview

    The method solveNQueens receives an integer n and must find every way to place n queens on an n by n board so that no two queens attack each other. A queen attacks along its row, its column and both diagonals. The constraint is 1 <= n <= 9.

    Each solution is a list of n numbers: entry r is the column of the queen in row r. All solutions are returned as a [[Int]], in any order. For n = 4 there are two: [1, 3, 0, 2] and [2, 0, 3, 1]. In the first, row 0 has its queen in column 1, row 1 in column 3, row 2 in column 0 and row 3 in column 2.

    Approach: build a placement row by row

    Two queens can't share a row, and a board with n queens on n rows must therefore have exactly one per row. That lets the search decide one thing per row: which column holds that row's queen. A partial answer is just the array of columns chosen so far, called placement.

    The search works like this. For row row, try each column from 0 to n - 1. If a queen at (row, col) is safe from the queens in earlier rows, add col to the placement and move on to the next row. When the recursive call comes back, remove col again and try the next column. This "choose, explore, undo" pattern is backtracking. When row reaches n, every row has a queen, so a copy of the placement joins the results.

    The safety test only looks at earlier rows, because later ones are still empty. A queen at (row, col) clashes with a queen at (i, placement[i]) in two ways: the same column, placement[i] == col, or the same diagonal. Two cells share a diagonal exactly when their row distance equals their column distance: abs(row - i) == abs(col - placement[i]).

    Checking every column in each row, but pruning unsafe ones immediately, avoids looking at the roughly n^n arrangements with one queen per row. A branch that has produced a clash is abandoned right there, together with all its extensions.

    Step by step

    1. Create the containers in solveNQueens: a var placements = [[Int]]() for finished boards and a var placement = [Int]() for the board being built.
    2. Start the search with backtracking(n, 0, &placement, &placements), from row 0. Both arrays go in as inout.
    3. Return placements once the search is done.
    4. Declare backtracking above solveNQueens, with n, row and the two inout arrays, all unlabeled.
    5. Finished board: if row == n, append placement to placements and return.
    6. Try every column with for col in 0..<n.
    7. Check safety by calling isValid(placement, row, col).
    8. Commit and recurse. Append col, then call backtracking for row + 1.
    9. Undo. Remove the last element with placement.remove(at: placement.count - 1), restoring the placement for the next column.
    10. Write isValid above backtracking. It loops over earlier rows 0..<row and returns false on a column or diagonal clash, and true if no row clashes.

    The solution in Swift

    class Solution {
    func isValid(_ placement: [Int], _ row: Int, _ col: Int) -> Bool {
        for i in 0..<row {
            if placement[i] == col ||
                    abs(row - i) == abs(col - placement[i]) {
                return false
            }
        }
        return true
    }
    func backtracking(_ n: Int, _ row: Int,
                      _ placement: inout [Int],
                      _ placements: inout [[Int]]) {
        if row == n {
            placements.append(placement)
            return
        }
        for col in 0..<n {
            if isValid(placement, row, col) {
                placement.append(col)
                backtracking(n, row + 1, &placement, &placements)
                placement.remove(at: placement.count - 1)
            }
        }
    }
    func solveNQueens(_ n: Int) -> [[Int]] {
        var placements = [[Int]]()
        var placement = [Int]()
        backtracking(n, 0, &placement, &placements)
        return placements
    }
}

    The Swift details worth a closer look:

    • Arrays copy when assigned. placements.append(placement) stores an independent copy of the current placement, because arrays are value types. Later calls to append and remove change placement but not the solution already saved. In a language with reference arrays, you would have to copy explicitly.
    • inout and &. The recursion shares one placement and one placements through inout parameters. The caller marks each with &, and omitting it is a compile error.
    • The half-open range 0..<row. It is empty when row is 0, so the first queen is always safe. Swift accepts an empty 0..<0 range, whereas a closed range 0...(row - 1) would crash for row = 0, because its upper bound would be below its lower bound.
    • abs is a global function. It works on any signed number, here Int.
    • remove(at:) returns the removed element. The lesson ignores the result. Swift would normally warn about an unused result, but remove(at:) is marked to allow that, so no warning appears. removeLast() does the same job in a more readable way.
    • Line continuation. The condition in isValid and the parameter list of backtracking span several lines. Swift doesn't need a continuation character, because the expressions are open after || and after the comma.

    Complexity

    Time: exponential. At each row up to n columns are tried, each checked in O(row) time. Pruning cuts the number of boards visited far below n^n, but the count of partial placements still grows quickly with n. The number of solutions itself is 1, 0, 0, 2, 10, 4, 40, 92 and 352 for n from 1 to 9, so the output grows too. With n at most 9, the search finishes quickly.

    Space: O(n) beyond the answer. The recursion is n levels deep, and placement holds at most n numbers. The returned list takes O(n) per solution.

    Edge cases and common mistakes

    • n = 1. One queen on a 1 by 1 board is a solution, so the result is [[0]].
    • n = 2 and n = 3. No arrangement works, and both return an empty array [].
    • n = 4. The result holds [1, 3, 0, 2] and [2, 0, 3, 1]. For n = 6 there are 4 solutions, and for n = 8 there are 92.
    • Forgetting the undo. Without remove(at:) after the recursive call, the next column is tried with the old queen still in the placement, and the results are wrong.
    • Only checking columns. Diagonal clashes are the part that is easy to miss. The condition is equal distances, not equal differences with a sign: abs catches both diagonal directions.
    • Checking rows below the current one. isValid reads placement[i] for i < row only. The placement has no entries for later rows yet, and reading one would crash with an index error.
    • Using the same array for results and the working copy. In Swift each is its own variable, which is why two inout parameters are needed.

    Testing

    • n = 1 gives [[0]].
    • n = 2 gives [].
    • n = 3 gives [].
    • n = 4 gives [[1, 3, 0, 2], [2, 0, 3, 1]].
    • n = 6 returns 4 solutions and n = 8 returns 92.
    Keep going with SwiftAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free