用遗传算法解决 n 皇后问题 （李怀远） 一、问题提出 N 皇后问题描述如下：在nn格棋盘上放置彼此不受攻击的 n 个皇后。按国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。N 皇后问题等价于在以下三个约束条件下：约束○1 任何 2 个皇后不放在同一行；约束○2 任何 2 个皇后不放在同一列；约束○3 任何 2 个皇后不放在同斜线；找出一种合法的放置方案。 我们把nn的棋盘看作二维方阵，其行号从上到下列号从左到右依次编号为 0，1，…，n-1.。设任意两个皇后，皇后 1 和皇后 2 的坐标分别是（i,j）和（k,l），则如果这两个皇后在从棋盘左上角到右下角的主对角线及其平行线（斜率为-1 的线）上，有 i-j=k-l=0 ；如果这两个皇后在斜率为＋1 的每一斜线上，有 i+j=k＋l；以上两个方程分别等价于 i-k=j-l 和 i-k=l-j因此任两皇后的在同一斜线上的充要条件是||||ljki 式○1 因此满足两个皇后不在同一斜线上的条件表示为： ||||ljki 式○2 两皇后不在同一行用式表示为：ki 式○3 两皇后不在同一列用式表示为：lj 式○4 此属 NP 问题不易求解，现在我们把任意 n 个皇后的任意一种放置办法当作一个个体（染色体），把其中的任意一个皇后当作一个基因，用遗传算法来解决该问题。 二、编码方案 对于此问题我提出两种编码方案。 A. 编码方案 1：排列编码 用一维 n 元数组x[0:n-1]来表示一个个体，其中1}-n,{0,1,x[i]，x[i]表示皇后 i 放在棋盘的第i 行第x[i]列，即第i 行第x[i]列放置一个皇后。例如，x[0]=0 表示棋盘的第0 行第0 列放一个皇后。数组第i 个元素表示第i 行的放置情况，可以看作一个基因。这种编码可以自然的解决了某一行只能放一个皇后的约束，如果数组的每一个元素x[i]都不重复，可以看成0——n-1 的一种排列，就自然保证每一列只能放一个皇后。因此在交叉变异和产生个体时必须注意 x[i]的唯一性。 B. 编码方案 2：二进制编码 用一维数组x[0:n2-1]表示一个个体，其中}1,0{][ ix。设cnri，其中}10|{} ,10|{nxZxxcnxZxxr，r 表示行号是 n 整除 i 的整数部分，c 是余数表示列号，如果 x[i]=1 表示棋盘的第r 行第c 列放有某一个皇后，如果 x[i]=0 表示棋盘的第r 行第c 列没有放置皇后。因为它使用了二进制编码，所以这种编码方法可以借用通用的二进制编码的交叉变异方法...
