N Queens
February 6, 2023
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 besolution(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}