Skip to content

Instantly share code, notes, and snippets.

@brugnara
Last active December 11, 2020 21:05
Show Gist options
  • Save brugnara/85a1d871d49abee9e2d17e7c285f61ac to your computer and use it in GitHub Desktop.
Save brugnara/85a1d871d49abee9e2d17e7c285f61ac to your computer and use it in GitHub Desktop.
Place N Queens on a NxN chessboard, with Go!
func totalNQueens(n int) int {
if n == 1 {
return 1
}
board := make([][]bool, n)
for i:=0;i<n;i++ {
board[i] = make([]bool, n)
}
count := 0
for i:=0;i<n;i++ {
placeQueen(0, i, &count, &board)
removeQueen(0, i, &board)
}
return count
}
func removeQueen(row, col int, board *[][]bool) {
(*board)[row][col] = false
}
func placeQueen(row, col int, count *int, board *[][]bool) {
(*board)[row][col] = true
// uncomment if you want to see how the board builds
// p(*board)
for _, x := range available(row + 1, board) {
if row + 1 == len(*board) - 1 {
*count += 1
// no need to place queens on last row but every slot counts
// as a final solution
// remove this "continue" if you want to also log the last row filled with the last queen
continue
}
placeQueen(row + 1, x, count, board)
removeQueen(row + 1, x, board)
}
}
func available(row int, board *[][]bool) (ret []int) {
// move through the line --->
for i:=0;i<len(*board);i++ {
valid := true
// then looping the rows
for y:=0;y<row;y++ {
// left diagonal
left := i - (row - y)
if left >= 0 {
if (*board)[y][left] {
valid = false
break
}
}
// right diagonal
right := i + (row - y)
if right < len(*board) {
if (*board)[y][right] {
valid = false
break
}
}
// column
if (*board)[y][i] {
valid = false
break
}
}
//
if !valid {
continue
}
//
ret = append(ret, i)
}
return
}
func p(matrix[][]bool) {
fmt.Println("----------")
for _, row := range matrix {
line := "| "
for _, c := range row {
if c {
line += " X "
} else {
line += " O "
}
line += " | "
}
fmt.Println(line)
}
fmt.Println("----------")
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment