# N Queens

1 min read Tweet this post
Section titled Problem

## Problem

The n-queens puzzle is the task of positioning n queens on an n x n chessboard in such a way that no two queens threaten each other. In chess, a queen can move in any direction vertically, horizontally, or diagonally, an unlimited number of squares.

Given an integer n, produce all unique solutions to the n-queens puzzle. Each solution should have distinct arrangements of the n queens on the board, represented as arrays with permutations of [1, 2, 3, … n]. The number in the ith element of the result array shows the row location of the queen in the ith column. Solutions should be returned in lexicographical order.

Example

``````For n = 1, the output should be
solution(n) = [[1]];

For n = 4, the output should be

solution(n) = [[2, 4, 1, 3],
[3, 1, 4, 2]]``````

This diagram of the second permutation, [3, 1, 4, 2], will help you visualize its configuration:

``````" . Q . . "
" . . . Q "
" Q . . . "
" . . Q . "``````
Section titled Solution

## Solution

``````func solution(n int) [][]int {
res := [][]int{}
solve(n, 0, []int{}, &res)
return res
}

func solve(n int, row int, queens []int, res *[][]int) {
if row == n {
board := []int{}
for _, queen := range queens {
board = append(board,  queen+1)
}
*res = append(*res, board)
return
}

for col := 0; col < n; col++ {
queens = append(queens, col)
if isValid(queens) {
solve(n, row+1, queens, res)
}
queens = queens[:len(queens)-1]
}
}

func isValid(queens []int) bool {
row := len(queens) - 1
for i := 0; i < row; i++ {
diff := abs(queens[i] - queens[row])
if diff == 0 || diff == row-i {
return false
}
}
return true
}

func abs(x int) int {
if x < 0 {
return -x
}
return x
}``````
go backtracking snippets