LESSON 260 OF 338 · BACKTRACKING

N Queens in Go: Backtracking with Column Lists

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

GO · BACKTRACKING

N Queens in Go, explained

Problem overview

The n-queens puzzle asks for ways to put n queens on an n by n board so that no two attack each other. Queens attack along rows, columns and diagonals. The method solveNQueens(n) on Solution returns every solution, in any order. Here n is between 1 and 9.

A solution is a []int of length n in which entry r is the column of the queen on row r. For n = 4 there are two solutions, [1, 3, 0, 2] and [2, 0, 3, 1]. In the first, the queens sit at (row 0, column 1), (row 1, column 3), (row 2, column 0) and (row 3, column 2).

Approach: place one queen per row and undo bad choices

Each row must hold exactly one queen, because two queens in a row would attack each other and there are as many queens as rows. So the search can go row by row, and the only choice at each row is the column. That shrinks the problem from choosing n squares out of n² to choosing a column for each row.

The search is backtracking:

For the current row, try each column in turn.
If a queen there is safe from the queens already placed above, place it and move on to the next row.
When the recursion comes back, remove that queen and try the next column.
When every row has a queen, record a copy of the placement.

Checking safety only needs the rows above. A new queen at (row, col) is attacked by the queen of an earlier row i, whose column is placement[i], if either of these holds:

The columns are equal: placement[i] == col.
They share a diagonal, which means the row distance row - i equals the column distance. The column distance is col - placement[i] on one diagonal and placement[i] - col on the other. Since row > i, the row distance is positive, so these two comparisons cover both diagonals without taking an absolute value.

Rows never clash, since each row gets one queen. Checking before placing prunes the search: a bad start for one row cuts off all the boards that could have followed it. The number of solutions for n from 1 to 9 is 1, 0, 0, 2, 10, 4, 40, 92 and 352.

Step by step

Prepare the results. In solveNQueens, declare placements as an empty [][]int to hold every solution.
Prepare the current board. Declare placement as an empty []int. Entry r will be the column chosen for row r.
Start the search with this.backtracking(n, 0, &placement, &placements). The addresses let the helper change both variables.
Return placements.
Declare backtracking with the size, the current row and the two pointers. Each call handles one row, and placement holds the columns for the rows above it.
Complete board. If row == n, every row has a queen. Append a copy of the placement to *placements and return.
Loop over columns. Let col run from 0 to n - 1.
Test the square by calling this.isValid(*placement, row, col). The function takes a plain slice, so the pointer is dereferenced.
Place the queen by appending col and storing the result back through the pointer.
Recurse into row+1. The pointers are passed along as they are.
Undo the choice by reslicing off the last element: (*placement)[:len(*placement)-1].
Declare isValid with the placement so far, the row and the column. It returns a bool.
Scan the earlier rows with i from 0 to row - 1. The queen of row i is at placement[i].
Reject attacks. Return false if the column matches or either diagonal condition holds.
Accept. If the loop ends with no conflict, return true.

The solution in Go

type Solution struct{}

func (this Solution) isValid(placement []int, row int, col int) bool {
	for i := 0; i < row; i++ {
		if placement[i] == col || row-i == col-placement[i] || row-i == placement[i]-col {
			return false
		}
	}
	return true
}

func (this Solution) backtracking(n int, row int, placement *[]int, placements *[][]int) {
	if row == n {
		*placements = append(*placements, append([]int{}, *placement...))
		return
	}
	for col := 0; col < n; col++ {
		if this.isValid(*placement, row, col) {
			*placement = append(*placement, col)
			this.backtracking(n, row+1, placement, placements)
			*placement = (*placement)[:len(*placement)-1]
		}
	}
}

func (this Solution) solveNQueens(n int) [][]int {
	placements := [][]int{}
	placement := []int{}
	this.backtracking(n, 0, &placement, &placements)
	return placements
}

Go details that matter here:

Why pointers to slices. A slice value is a small header holding a pointer to an array, a length and a capacity. Passing it to a function copies the header. Elements written through the copy are visible to the caller, but append can change the length, or move the data to a bigger array, and that change lives only in the callee's copy. With *[]int, the helper updates the caller's own variable.
The copy at a solution. append([]int{}, *placement...) builds a new slice from the elements. Storing *placement itself would save a header that shares the working array, and as the search keeps appending and cutting back, that shared array keeps changing, so every stored solution would be overwritten. A small loop shows the effect: appending to a slice with spare capacity, saving it, cutting it back to length 0 and repeating three times leaves [[2] [2] [2]] in the list instead of [[0] [1] [2]].
Parentheses in the undo step. (*placement)[:len(*placement)-1] first follows the pointer, then slices. Without the parentheses, Go would try to slice the pointer, which doesn't compile.
The receiver. this is just a name for the receiver of a method on Solution, an empty struct. Go doesn't require that name or give it special meaning. There are no classes, only types with methods.
No absolute value for integers. The standard library's math.Abs works on float64. Comparing the two signed differences avoids both a conversion and an import.
The empty result. [][]int{} is an empty, non-nil slice, so n = 2 and n = 3 return a slice of length 0.

Complexity

Time: exponential in n. There are at most n choices per row and n rows, so n^n boards is an upper bound, but the safety test cuts off most of them. Each test costs O(n). For n up to 9, the search finishes quickly.

Space: O(n) for the working placement and the call stack, plus the output itself, which holds one slice of length n per solution.

Edge cases and common mistakes

n = 1. The only board is a single queen, so the result is [[0]].
n = 2 and n = 3. No solutions exist, so the result is empty.
Storing the working slice. Appending *placement without copying makes every saved solution change later, as described above.
Forgetting to undo. If the append is not followed by a cut, the placement keeps growing and later columns are tested against stale queens.
Checking only one diagonal. The two comparisons correspond to the two diagonal directions. With only one of them, some attacked squares are accepted.
Dropping the pointer in the recursive call. Writing &placement inside backtracking would pass a pointer to the local pointer, which doesn't compile.

Testing

solveNQueens(4) returns [[1 3 0 2] [2 0 3 1]], the same order as in this search. solveNQueens(1) returns [[0]]. solveNQueens(5) returns 10 solutions, the first being [0 2 4 1 3]. solveNQueens(8) returns 92 and solveNQueens(9) returns 352.

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

Start learning free