N-Queens

Hard

The problem

Place n queens on an n × n chessboard so that no two queens attack each other (no two share a row, a column or a diagonal). Return every valid board, drawn as a list of strings where "Q" is a queen and "." is an empty square.

Example 1
Input: n = 4
Output: [[".Q..", "...Q", "Q...", "..Q."], ["..Q.", "Q...", "...Q", ".Q.."]]
There are exactly two ways to place 4 queens safely on a 4 × 4 board.
Example 2
Input: n = 1
Output: [["Q"]]

Limits

1 ≤ n ≤ 9
The order of the boards does not matter
If no board works return an empty list

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

Place one queen per row. How can you detect in O(1) that a column or diagonal is taken?

The idea

DFS row by row; keep sets for columns, r+c diagonals and r−c anti-diagonals. Place, recurse, remove. Record the board when all rows are filled.

Target: O(n!) time

Go function shape

func solveNQueens(n int) [][]string

Reference solution

Tested with go test. Try it yourself first, then compare.

// SolveNQueens: all placements of n queens with no two attacking.
// One queen per row; three boolean sets make the "is it safe?" check O(1).
func SolveNQueens(n int) [][]string {
	res := [][]string{}
	cols := make([]bool, n)
	diag := make([]bool, 2*n) // r+c
	anti := make([]bool, 2*n) // r-c+n
	queens := make([]int, n)  // queens[r] = column of the queen in row r
	var dfs func(r int)
	dfs = func(r int) {
		if r == n {
			board := make([]string, n)
			for i, c := range queens {
				row := make([]byte, n)
				for j := range row {
					row[j] = '.'
				}
				row[c] = 'Q'
				board[i] = string(row)
			}
			res = append(res, board)
			return
		}
		for c := 0; c < n; c++ {
			if cols[c] || diag[r+c] || anti[r-c+n] {
				continue // prune: attacked square
			}
			cols[c], diag[r+c], anti[r-c+n] = true, true, true
			queens[r] = c
			dfs(r + 1)
			cols[c], diag[r+c], anti[r-c+n] = false, false, false
		}
	}
	dfs(0)
	return res
}

Read the lesson: Backtracking