回溯法在算法设计中用于解决n皇后问题

一、什么是N皇后问题？

在n×n的棋盘上，需要安置n个皇后，使得这些皇后之间不会互相攻击。根据国际象棋的规则，皇后具有攻击同一行、同一列以及同一斜线上的棋子的能力。因此，N皇后问题可以被理解为在n×n的棋盘上安排n个皇后，确保任意两个皇后都不处于同一行、同一列或同一斜线上。

问题解析：采用n元数组x[1:n]来描述n后问题的解集。其中，x[i]表示第i个皇后在棋盘第i行的第x[i]列位置。由于规则规定不允许两个皇后位于同一列，因此解向量中所有x[i]的取值必须互不相同。若将n*n的棋盘视为一个二维矩阵，行号自上而下依次为1至n，列号自左向右同样编号为1至n。假设某两个皇后的坐标分别为(i,j)与(k,l)，当它们处于同一条斜线时，则由这两点所确定的直线斜率应为1或-1。由此可得：

     由此约束条件剪去不满足行、列和斜线约束的子树。程序的递归回溯实