由于最近课程需要提交“八皇后”代码，特此写下此博客，来做一下关于八皇后的总结。

八皇后问题

八皇后问题，即在一个 8x8 的棋盘上，放置 8 个皇后棋子，其中每个皇后都不能处于同一条横行、纵行上，也不能处于同一条斜线上。

参考视频

在编程过程中，我感觉有些视频讲的很好，这里分享出来：

参考视频：懒猫老师-C 语言-递归函数-八皇后问题(搜索，回溯)

实现代码

这里的代码用的语言是 ToyPL，是吴老师自己手写的玩具语言，里面没有 for，所以用 while 来代替了。（语法简单，不用特意解释就能看懂）

特别说明：由于语言特性，在全局只能声明数组变量，所以下方的 count 为数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
// 第row行皇后所占位置的列号
int queen[8]
// 标志数组，表示第col列是否可用，默认为true（可用）
bool flag[8]
// 表示上对角线是否可用
bool d1[15]
// 表示下对角线是否可用
bool d2[15]
// 解法个数(八皇后有92个解)
int count[2]
fun main()
{
  init()
  generate(0)
  print("共有"+count[1]+"种解法\n")
}
fun init()
{
  // 初始化数组
  int i=0
  while(i<8)
  {
    queen[i]=-1
    flag[i]=true
    i=i+1
  }
  i=0
  while(i<15)
  {
    d1[i]=true
    d2[i]=true
    i=i+1
  }
  count[1] = 0
  print("初始化成功...\n")
}
fun generate(int n)
{
  int col = 0
  // 每个皇后都有8列
  while(col<8)
  {
    // 判断位置是否可用
    if(flag[col]&d1[n-col+7]&d2[n+col])
    {
      // 在n行col列摆放皇后
      queen[n]=col
      // 设置第col列不可用
      flag[col]=false
      // 设置两个对角线不可用
      d1[n-col+7]=false
      d2[n+col]=false
      // 8个皇后没有摆完，递归摆放下一行里面的皇后
      if(n<7)
      {
        generate(n+1)
      }else
      {
        // 皇后都放完了，打印结果
        printQ()
      }
      //回溯，考虑其他的可行方案
      flag[col]=true
      d1[n-col+7]=true
      d2[n+col]=true
    }
    col=col+1
  }
}
fun printQ()
{
  count[1]=count[1]+1
  print("第"+count[1]+"个解法：")
  int i=0
  while(i<8)
  {
    print(queen[i] + "  ")
    i=i+1
  }
  print("\n")
}

__END__