資料結構
網路
關係資料庫管理系統(RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究Go語言實現N皇后問題
N皇后問題是一個智力遊戲，需要將N個皇后放置在一個N×N的棋盤上，使得任何兩個皇后都不能處於同一行、同一列或同一對角線上（互相攻擊）。國際象棋中的皇后可以沿任何方向移動（水平、垂直和對角線），因此找到沒有兩個皇后能夠互相攻擊的位置是一項挑戰。在本文中，我們將編寫一個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 - 在主函式中，建立一個布林值的二維切片作為棋盤，並使用棋盤、行、輸出陣列和大小作為引數呼叫`solveN_queens`。
步驟8 - 最後，迭代輸出列表，並使用`fmt`包中的`Println`函式在控制檯上列印輸出。
示例
在這個例子中，我們將編寫一個Go語言程式，使用回溯演算法在一個N×N棋盤上實現N皇后問題，並遞迴地將每個皇后放置在棋盤上。
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皇后問題可以幫助你提高解決問題和演算法設計的能力。
342 次瀏覽
