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 - 在主函数中，将棋盘创建为二维布尔切片，并使用board、row、output数组和大小作为参数调用solveN_queens

• 步骤8 - 最后，遍历outputs列表，并使用fmt包的Println函数将输出打印到控制台

示例

在本例中，我们将编写一个使用回溯算法递归地在NXN棋盘上实现N皇后问题的Go语言程序。

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皇后问题可以帮助您提高问题解决和算法设计的能力。