算法笔记：回溯法：n皇后问题与0-1背包问题

1、n后问题

问题描述： 在一个由n \times n个小方格组成的棋盘上布置n个互不攻击之皇后的任务，在国际象棋规则下是如此：每枚皇后能够威胁位于其同行、同列或对角线上的任意一枚棋子。相应地，在一个由若干小方格构成的大方格中安置若干互不攻击之皇后的任务等同于在一个由相同数量的小方格组成的方阵中布置相同数量之皇后的任务，并且任何两枚皇后的位置都不可能位于同行、同列或是共用一条对角线之上。

问题解析： 使用一维数组x[1:n]来表示n后问题的解。其中x[i]表示皇后i位于棋盘的第i行x[i]列的位置。由于规定不能有两个皇后位于同一列上，则解向量中所有x[i]都不相同。如果我们把n \times n棋盘视为一个二维矩阵形式，在行列编号方面是从上至下、从左至右依次为1, 2, \dots, n。假设两皇后的坐标分别为(i,j)与(k,l)的位置，则当且仅当两皇后处于对角线上时（即它们的位置连线斜率为\pm 1），有|j - l| = |i - k|成立

![](https://ad.itadn.com/c/w