八皇后问题-百度百科golang代码详解

1.八皇后问题

在8×8格的国际象棋上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。 刚拿到这道题时，思路虽然有了，但是实现起来发现非常麻烦，因为我开始就用了一个[][]int来表示棋盘，然后通过在棋盘中放置皇后来实验是否可以放置。没有解决问题，因为看了百度百科中的解释。但百度百科中的解释不够通俗，代码注释也很少，因此在理解解法和看懂代码后，将此记录。 第一个很好的方式便是，用一个数组来记录，代表每一列的皇后放在第几行。（也可以反过来理解，每一行的皇后都放在第几列）

2.回溯法解法

回溯法： 从第0列开始放，先放第0行，因为自己是第一个放的，位置肯定是可以的。 现在从1列开始放，也是先从第0行开始，发现，和前面列中的同一行了，冲突，所以，往下放，即开始从第1行放。发现，和上一列的在一条斜线了，冲突，接着往下放。 … 如果在放的过程中发现，走到了最后一行，还是不行。那么，说明它的前一列放置的不对。前一列放置的地方需要往放。 … 直到第0列中的皇后放到了最后一行了。结束循环。

怎么判断是否同一行 在前面已经放置过皇后的列中，如果有和自己目前放的行数相同的，说明此位置不行，后面的列还未放置皇后，不用考虑。怎么判断是否同一列 因为数组中的每一项代表了该列中皇后的放置位置，不可能处于同一列了。怎么判断是否同一斜线 当两个皇后的纵向距离和横向 距离相同时，说明处于同一斜线，

3.原始代码

4.注释详解

func main() { //用一个数组来记录即可，代表每一列的皇后放在第几行。 var balance = [8]int{0, 0, 0, 0, 0, 0, 0, 0} queen(balance, 0) } func queen(a [8]int, cur int) { //最后一个皇后放好后，调用该方法时，cur ==8,即8个皇后都放好了，因此可以打印数组了 if cur == len(a) { fmt.Print(a) fmt.Println() return } //i现在代表的是行数，cur代表列数 for i := 0; i < len(a); i++ { //从第0行开始放 a[cur] = i //代表这一行能不能放 flag := true //验证可不可以放 //后面几列还没放，所以不用考虑，j<cur for j := 0; j < cur; j++ { //i 代表本皇后放置的行号，j代表之前的列号，a[j]代表的是 j列的皇后放在了第几行 //若果 a[j] == i 肯定不能放，flag = false，因为同一行有了两个了 //ab代表的是两个皇后之间的行数差距，即纵向距离，如果纵向距离和横向距离相等的话，说明在一条斜线上 ab := i - a[j] temp := 0 //求纵向距离，变成正数，方便比较 if ab > 0 { temp = ab } else { temp = -ab } //a[j] == i 处于同一行了，temp == cur-j 处于同一斜线了，该位置不能放 if a[j] == i || temp == cur-j { flag = false break } } //满足的话，开始放下一列的皇后，不满足，行数往下走一行 if flag { queen(a, cur+1) } } }