LESSON 290 OF 414 · BACKTRACKING

N Queens in Scala: Backtracking with ArrayBuffer

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

Guided

Ctrl + Enter to check

SCALA · BACKTRACKING

N Queens in Scala, explained

Problem overview

The method solveNQueens receives an integer n and returns every way to place n queens on an n by n chessboard so that no two queens attack each other. Queens attack along rows, columns and diagonals. Each solution is a sequence in which entry r is the column of the queen on row r. The solutions may come in any order, and the result type is mutable.ArrayBuffer[mutable.ArrayBuffer[Int]].

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

Approach: place one queen per row, undo when stuck

With n queens on n rows and no two sharing a row, every row holds exactly one queen. So the only choice is which column to use in each row. The brute force tries all combinations of a column for each row, n to the power n of them, which is far too many. Backtracking builds the board row by row and abandons a partial board as soon as it contains an attack:

Standing at row, try each column from 0 to n - 1.
If a queen at (row, col) is safe from the queens already placed above, place it and move to the next row.
When the recursion comes back, remove that queen and try the next column.
When row == n, all rows have a queen: record a copy of the board.

"Place, recurse, remove" is the shape of every backtracking solution. Because unsafe squares are rejected right away, whole subtrees of hopeless boards are never visited.

A queen at (row, col) is attacked by the queen in an earlier row i at column placement(i) if they share a column (placement(i) == col) or a diagonal. Two squares are on a diagonal when the row distance equals the column distance, so the test is Math.abs(row - i) == Math.abs(col - placement(i)). Rows can't clash, because only one queen goes in each.

Step by step

Create the result collection in solveNQueens: mutable.ArrayBuffer[mutable.ArrayBuffer[Int]](). Each inner buffer will be one finished board.
Create the working board, mutable.ArrayBuffer[Int](). Its entry r is the column of the queen in row r, and it grows and shrinks as the search moves.
Start the search with backtracking(n, 0, placement, placements), then return placements.
Declare backtracking with n, row, the working board and the result collection, returning Unit.
Complete board: if row == n, add placement.clone() to placements and return. The copy matters because the same buffer keeps changing afterwards.
Loop over the columns with for (col <- 0 until n).
Test the square with isValid(placement, row, col).
Place: append with placement += col.
Recurse: backtracking(n, row + 1, placement, placements).
Undo: placement.remove(placement.size - 1) drops the last entry. On an ArrayBuffer, remove takes an index.
Write isValid. Loop i over the earlier rows, 0 until row. If the queen in row i shares the column or a diagonal, return false. After the loop, return true.

The solution in Scala

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

    def backtracking(n: Int, row: Int,
                     placement: mutable.ArrayBuffer[Int],
                     placements: mutable.ArrayBuffer[mutable.ArrayBuffer[Int]]): Unit = {
        if (row == n) {
            placements += placement.clone()
            return
        }
        for (col <- 0 until n) {
            if (isValid(placement, row, col)) {
                placement += col
                backtracking(n, row + 1, placement, placements)
                placement.remove(placement.size - 1)
            }
        }
    }

    def solveNQueens(n: Int): mutable.ArrayBuffer[mutable.ArrayBuffer[Int]] = {
        val placements = mutable.ArrayBuffer[mutable.ArrayBuffer[Int]]()
        val placement = mutable.ArrayBuffer[Int]()
        backtracking(n, 0, placement, placements)
        return placements
    }
}

Scala details:

The type mutable.ArrayBuffer. It is a growable array, from the package scala.collection.mutable. In a file of your own you need import scala.collection.mutable for this code to compile.
+= adds, and remove takes an index. placement += col appends one element. placement.remove(placement.size - 1) removes the element at that index, here the last one.
clone(). A buffer is a reference. Adding placement itself would store the same object many times, and by the end of the search it is empty, so every stored board would be empty. With a copy, each stored board keeps its contents. Without the copy, the result for n = 4 is two empty buffers.
return inside for. Scala 3 compiles a for over a range into a call with a function body, so the return false in isValid works by throwing an exception that the method catches. The compiler accepts it but warns that non-local returns are no longer supported and suggests scala.util.boundary. An exists call over 0 until row, or a while loop, avoids the warning.
0 until n. It excludes n, which is what a column index needs.

Complexity

Time. There is no tight closed form. At most n choices exist in the first row, at most n - 1 columns are free in the second, and so on, so n! bounds the number of boards the search can reach, and the early rejection cuts that down a great deal. Each safety check costs O(n). The number of solutions itself grows quickly: 1, 0, 0, 2, 10, 4, 40, 92 and 352 for n from 1 to 9.

Space. The working board holds up to n entries and the recursion is n calls deep, so the search uses O(n) memory besides the stored solutions, which take up to n numbers each.

Edge cases and common mistakes

n = 1. The only board is one queen, so the result is [[0]].
n = 2 and n = 3. No placement works, and the result is an empty buffer. The search finishes without ever reaching row == n.
Counts. For n = 4 to n = 9 the result has 2, 10, 4, 40, 92 and 352 boards.
Order. Columns are tried from 0 upward, so the boards come out in increasing order. For n = 4 the first is [1, 3, 0, 2], and for n = 6 it is [1, 3, 5, 0, 2, 4].
Forgetting to undo. Without the remove, leftover queens from a failed branch stay in the buffer and later checks compare against queens that are no longer there.
Storing the working buffer. Skipping clone() corrupts the results, as above.
Checking only the column. A diagonal attack is a row difference equal to a column difference. For the partial board [1, 3], column 2 on row 2 is rejected because the queen at row 1, column 3 is one row and one column away.

Testing

n = 1 gives [[0]].
n = 2 and n = 3 give no solutions.
n = 4 gives [[1, 3, 0, 2], [2, 0, 3, 1]].
n = 6 gives 4 solutions, and n = 8 gives 92.

Keep going with ScalaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free