N Queens

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 . "

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
}