Golang 程序实现 N 皇后问题
N 皇后问题是一个难题，其中 N 个皇后被放置在 NXN 棋盘上，使得两个皇后不共享同一行、列和对角线或互相攻击。国际象棋中的皇后可以向任何方向移动，水平、垂直和对角线，因此找到两个皇后不能互相攻击的地方是一项挑战。在本文中，我们将编写一个 Go 语言程序来实现 N 皇后问题。
语法
func make ([] type, size, capacity)
Go 语言中的 make 函数用于创建数组/映射，它接受要创建的变量的类型、其大小和容量作为参数
func append(slice, element_1, element_2…, element_N) []T
append 函数用于将值添加到数组切片。它需要多个参数。第一个参数是我们希望添加值的数组，后面是要添加的值。然后，该函数返回包含所有值的数组的最终切片。
算法
步骤 1 - 创建一个名为 is_safe 的函数来检查在棋盘上的给定位置放置皇后是否安全
步骤 2 - 此函数还检查同一列、左上对角线和右上对角线中是否有皇后
步骤 3 - 创建一个函数solveN_queens，该函数采用棋盘的当前状态、当前行、棋盘的大小 N 以及指向输出的指针。在此步骤中，检查 row==N，如果为真，则将解决方案添加到输出列表中
步骤 4 - 遍历当前行中的所有列并检查在当前位置放置皇后是否安全。如果满足前一个条件，则继续执行下一步
步骤 5 - 将当前位置设置为由皇后占据(board[row][col] = true)。
步骤 6 - 递归调用solveN_queens获取下一行(row+1)，递归调用后，通过将当前位置设置为未占用来回溯，循环结束后，函数solveN_queens在循环结束后返回
步骤 7 - 在主函数中，将棋盘创建为布尔值的 2D 切片，并使用棋盘、行、输出数组和大小作为参数调用solveN_queens
步骤 8 - 最后，遍历输出列表并使用 fmt 中的 Println 函数在控制台上打印输出包
示例
在此示例中，我们将编写一个 Go 语言程序，使用回溯算法实现 N 个皇后，使用 NXN 棋盘并递归地将每个皇后放置在棋盘上。
package main
import "fmt"
func is_safe(board [][]bool, row, col, N int) bool {
for i := 0; i < row; i++ {
if board[i][col] {
return false
}
}
for i, j := row-1, col-1; i >= 0 && j >= 0; i, j = i-1, j-1 {
if board[i][j] {
return false
}
}
for i, j := row-1, col+1; i >= 0 && j < N; i, j = i-1, j+1 {
if board[i][j] {
return false
}
}
return true
}
func solveN_queens(board [][]bool, row, N int, outputs *[][]int) {
if row == N {
var output []int
for i := 0; i < N; i++ {
for j := 0; j < N; j++ {
if board[i][j] {
output = append(output, j+1)
break
}
}
}
*outputs = append(*outputs, output)
return
}
for col := 0; col < N; col++ {
if is_safe(board, row, col, N) {
board[row][col] = true
solveN_queens(board, row+1, N, outputs)
board[row][col] = false
}
}
}
func main() {
n := 5
board := make([][]bool, n)
for i := 0; i < n; i++ {
board[i] = make([]bool, n)
}
var outputs [][]int
solveN_queens(board, 0, n, &outputs)
for _, output := range outputs {
fmt.Println(output)
}
}
输出
[1 3 5 2 4] [1 4 2 5 3] [2 4 1 3 5] [2 5 3 1 4] [3 1 4 2 5] [3 5 2 4 1] [4 1 3 5 2] [4 2 5 3 1] [5 2 4 1 3] [5 3 1 4 2]
输出观察
在第一个解决方案中，皇后排列在第一行的第一列、第二行的第三列、第三行的第五列、第四行的第二列、第五行的第四列。N 皇后问题可能有多个解决方案，上述代码将找到所有有效的解决方案。
结论
在本文中，我们讨论了如何实现 N 皇后问题。我们用一个使用回溯的示例执行了实现 N 皇后问题的程序。实现 N 皇后问题有助于提高您的问题解决和算法设计能力。
