Published on

# N Queens

Authors
• Name
Moch Lutfi
@kaptenupi

## 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

`_7For n = 1, the output should be_7solution(n) = [];_7_7For n = 4, the output should be_7_7 solution(n) = [[2, 4, 1, 3],_7 [3, 1, 4, 2]]`

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

`_4" . Q . . "_4" . . . Q "_4" Q . . . "_4" . . Q . "`

## Solution

`_42func solution(n int) [][]int {_42 res := [][]int{}_42 solve(n, 0, []int{}, &res)_42 return res_42}_42_42func solve(n int, row int, queens []int, res *[][]int) {_42 if row == n {_42 board := []int{}_42 for _, queen := range queens {_42 board = append(board, queen+1)_42 }_42 *res = append(*res, board)_42 return_42 }_42 _42 for col := 0; col < n; col++ {_42 queens = append(queens, col)_42 if isValid(queens) {_42 solve(n, row+1, queens, res)_42 }_42 queens = queens[:len(queens)-1]_42 }_42}_42_42func isValid(queens []int) bool {_42 row := len(queens) - 1_42 for i := 0; i < row; i++ {_42 diff := abs(queens[i] - queens[row])_42 if diff == 0 || diff == row-i {_42 return false_42 }_42 }_42 return true_42}_42_42func abs(x int) int {_42 if x < 0 {_42 return -x_42 }_42 return x_42}`