回溯法之n皇后问题

 1 package main
 2 
 3 import (
 4     "fmt"
 5     "math"
 6 )
 7 
 8 //判断第k行的某一列放置是否合法
 9 func check(col []int, k int) int {
10     for i := 0; i < k; i++ {
11         if col[i] == col[k] || float64(k - i) == math.Abs(float64(col[k] - col[i])) {//与前部分行同列或者列之差的绝对值与两行之差的绝对值相等
12             return 0
13         }
14     }
15     return 1
16 }
17 
18 //迭代实现， 思想原理同着色问题
19 func n_queen(k int) []int{
20     var i int
21     col := make([]int, k)
22     for i = 0; i < k; i++ {
23         col[i] = 0
24     }
25     for i = 0; i >= 0; {
26         for col[i] < k {
27             col[i]++
28             if check(col, i) > 0 {
29                 i++
30             }
31             if i == k {
32                 return col
33             }
34         }
35         col[i] = 0
36         i--
37     }
38     return nil
39 }
40 
41 func main() {
42     k := 29
43     res := n_queen(k)
44     if res != nil {
45         for i := 0; i < k; i++ {
46             fmt.Print(res[i], "	")
47         }
48     }
49 }
50