N-Queens

package main

import "fmt"

func solveNQueens(n int) [][]string {
	result := [][]string{}
	cols := make(map[int]bool)
	diag1 := make(map[int]bool) // row - col
	diag2 := make(map[int]bool) // row + col
	board := make([][]byte, n)
	for i := range board {
		board[i] = make([]byte, n)
		for j := range board[i] {
			board[i][j] = '.'
		}
	}

	var backtrack func(row int)
	backtrack = func(row int) {
		if row == n {
			snapshot := make([]string, n)
			for i := range board {
				snapshot[i] = string(board[i])
			}
			result = append(result, snapshot)
			return
		}
		for col := 0; col < n; col++ {
			if cols[col] || diag1[row-col] || diag2[row+col] {
				continue
			}
			board[row][col] = 'Q'
			cols[col] = true
			diag1[row-col] = true
			diag2[row+col] = true

			backtrack(row + 1)

			board[row][col] = '.'
			cols[col] = false
			diag1[row-col] = false
			diag2[row+col] = false
		}
	}

	backtrack(0)
	return result
}

func main() {
	solutions := solveNQueens(4)
	for _, sol := range solutions {
		for _, row := range sol {
			fmt.Println(row)
		}
		fmt.Println()
	}
	// .Q..
	// ...Q
	// Q...
	// ..Q.
	//
	// ..Q.
	// Q...
	// ...Q
	// .Q..
}