转载原文链接：https://blog.csdn.net/Tianzez/article/details/80242603
1. 题目： 八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。
2. 解题思路： 创建两个全局变量：一个8*8的int类型数组 int board[8][8]模拟棋盘， 和一个计数器 int sum = 0记录有多少种解法。
放置皇后。每行放置一个皇后，首先从第一行开始放起。判断他能够放在这一行的哪一列。每放置一个皇后就把该位置置为1。
放到第八行时表示八个皇后全部放完，开始回溯，把原本标记的位置进行清理。
注意：
注意边界，不能越界。
注意递归结束的条件。
check()函数检查位置是否合法，要检查这个坐标点所在的列、左下对角线和右下对角线。当前行和上部分的对角线不用检查，因为皇后是逐行放的，上面还没放。
3. < Code >
#include "stdio.h" int board[8][8]; //棋盘 int sum = 0; //计数器 int check(int row, int col) //判断(row, col)位置是否可以放皇后 { int i = 0; int j = 0; for (i = 0; i < 8; i++) { if (board[i][col] == 1) //判断第c列有没有皇后 return 0; } for (i = row, j = col; i >= 0 && j >= 0; i--, j--) //判断左下对角线有没有皇后 { if (board[i][j] == 1) return 0; } for (i = row, j = col; i >= 0 && j < 8; i--, j++) //判断右下对角线有没有皇后 { if (board[i][j] == 1) return 0; } return 1; } void put_queen(int row) //放皇后 { if (row == 8) //递归结束条件 { sum++; //找到一种解法，计数器++ return; } for (int col = 0; col < 8; col++) { if (check(row, col)) { board[row][col] = 1; //放下皇后 put_queen(row + 1); //递归 board[row][col] = 0; //回溯前把之前的皇后标记清零 } } } int main() { put_queen(0); //从第一行开始放皇后 printf("%d\n", sum); //输出八皇后问题解法数量 return 0; }翻来翻去，就这个代码最容易理解，网上的那些代码有的整的太麻烦了，而且有的变量命名无形中增加理解难度，在此记录一下，方便下次翻阅理解
下附python代码实现：
board = [[0 for i in range(0,8)] for i in range(0,8)] cnt = 0 def check(row, col): for i in range(8): for j in range(8): if (board[i][j] == 1) and (abs(i-row) == abs(j-col) ): return False#对角线有皇后 if (board[i][j] == 1) and (i == row): return False#同一行有皇后 if (board[i][j] == 1) and (j == col): return False#同一列有皇后 return True def queen(row): global cnt if 8 == row: cnt += 1 return for col in range(0, 8): if True == check(row, col): board[row][col] = 1 #放下皇后 queen(row + 1) #递归 board[row][col] = 0 #收回皇后 queen(0) print(cnt)
