Start learning free

LESSON 266 OF 348 · BACKTRACKING

N-Queens in Kotlin: Backtracking Row by 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

    KOTLIN · BACKTRACKING

    N Queens in Kotlin, explained

    Problem overview

    Place n queens on an n by n chessboard so that no two attack each other: no two share a row, a column or a diagonal. solveNQueens(n) returns all distinct solutions, in any order. Each solution is a list of n numbers, where entry r is the column of the queen in row r.

    For n = 4 there are two solutions: [[1, 3, 0, 2], [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. The lesson states 1 <= n <= 9.

    Approach

    Since each row must hold exactly one queen (two in a row would attack each other), we can build a solution one row at a time. For row 0 we try every column. For each choice that is safe, we move on to row 1 and try every column that doesn't clash with the queens above, and so on. If we reach row n, every row has a queen and we have found a solution. If a row has no safe column, the search backs up and changes an earlier choice. This is backtracking: add a choice, explore, undo the choice.

    The key is the safety test. A queen at (row, col) attacks a queen at (i, c) if they share a column (c == col) or a diagonal. Two squares are on the same diagonal exactly when the row distance equals the column distance: |row - i| == |col - c|. We never need to test rows, because we place one queen per row.

    Pruning on every row means the search never explores boards that already contain an attack, which is far fewer than all the n^n ways to pick one column per row.

    Step by step

    1. Prepare the containers. placements is a mutableListOf<MutableList<Int>>() that collects the finished boards. placement is a mutableListOf<Int>() holding the columns chosen so far for rows 0, 1, 2, and so on.
    2. Start the search with backtracking(n, 0, placement, placements) and then return placements.
    3. Declare backtracking. Each call handles one row, with placement already holding the columns of the rows above it.
    4. Solution found. If row == n, add a copy of placement to placements and return. The copy matters: placement keeps changing as the search continues, and a stored reference would change with it.
    5. Try each column. Loop col over 0 until n.
    6. Check safety. Only when isValid(placement, row, col) is true do we place a queen.
    7. Choose, explore, undo. Add col to placement, recurse with row + 1, and then remove the last element with removeAt(placement.size - 1).
    8. Write isValid. Loop i over 0 until row. Row i has its queen at placement[i]. Return false for the same column or the same diagonal. If the loop finishes without a clash, return true.

    The solution in Kotlin

    class Solution {
    fun isValid(placement: MutableList<Int>, row: Int, col: Int): Boolean {
        for (i in 0 until row) {
            if (placement[i] == col ||
                    Math.abs(row - i) == Math.abs(col - placement[i])) {
                return false
            }
        }
        return true
    }

    fun backtracking(n: Int, row: Int,
                     placement: MutableList<Int>,
                     placements: MutableList<MutableList<Int>>) {
        if (row == n) {
            placements.add(ArrayList(placement))
            return
        }
        for (col in 0 until n) {
            if (isValid(placement, row, col)) {
                placement.add(col)
                backtracking(n, row + 1, placement, placements)
                placement.removeAt(placement.size - 1)
            }
        }
    }

    fun solveNQueens(n: Int): MutableList<MutableList<Int>> {
        val placements = mutableListOf<MutableList<Int>>()
        val placement = mutableListOf<Int>()
        backtracking(n, 0, placement, placements)
        return placements
    }
}

    Kotlin details:

    • removeAt versus remove. On a MutableList<Int>, removeAt(index) removes by position, while remove(element) removes the first element equal to the value. With [10, 20, 30], removeAt(1) leaves [10, 30] and then remove(30) leaves [10]. Here we want the last position, so removeAt(placement.size - 1) is right.
    • ArrayList(placement) creates a new list with the same elements. Without it, every stored solution would be the same object that the search later empties.
    • 0 until row is a range that excludes row. When row is 0 the range is empty, so the first queen is always safe.
    • Mutable and read-only lists. The parameters are MutableList, so the helper can add and remove elements. A plain List couldn't be changed.
    • Splitting a condition. The line break after || is fine: the operator at the end of the line tells Kotlin that the expression continues.
    • Math.abs comes from Java and works on Int. kotlin.math.abs is the Kotlin equivalent.

    A trace for n = 4

    Row 0 tries column 0. Row 1 can't use column 0 (same column) or column 1 (diagonal), so it takes column 2. Row 2 finds columns 0 and 2 blocked by columns, column 1 and column 3 by diagonals, and has no safe square. The search removes the queen from row 1 and tries column 3, and keeps going until the column-0 branch is exhausted. Row 0 then moves to column 1, which leads to [1, 3, 0, 2].

    Complexity

    Each call tries up to n columns, and isValid costs O(n). A rough bound for the whole search is O(n!) nodes, since the number of safe columns drops with each row, times O(n) per check. The exact count is lower because many branches are cut early. The memory is O(n) for the recursion and the current placement, plus the stored solutions, each of size n.

    The number of solutions grows quickly: n = 1 to 9 give 1, 0, 0, 2, 10, 4, 40, 92 and 352 solutions.

    Edge cases and common mistakes

    • n = 1. One queen on a 1 by 1 board: the result is [[0]].
    • n = 2 and n = 3. No solution exists, so the result is an empty list.
    • Not copying the placement. You would get a list of identical empty lists at the end, because the same object is emptied by the final undo steps.
    • Using remove instead of removeAt. Removing by value deletes the first matching column, which may be a different queen.
    • Forgetting the undo. Later rows would see queens from branches that were already abandoned.
    • Testing only rows and columns. The diagonal check is what makes two queens in (0, 0) and (1, 1) invalid.
    • Looping to row inclusive. Row row has no queen yet, so placement[row] would throw IndexOutOfBoundsException.

    Testing

    • solveNQueens(4) returns [[1, 3, 0, 2], [2, 0, 3, 1]].
    • solveNQueens(6) returns [[1, 3, 5, 0, 2, 4], [2, 5, 1, 4, 0, 3], [3, 0, 4, 1, 5, 2], [4, 2, 0, 5, 3, 1]].
    • solveNQueens(8) has 92 entries.
    • solveNQueens(3) is empty.
    Keep going with KotlinAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free