Problem
该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出的,在8×8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。
算法
约束1:任意两个皇后不能在同一行
因为任意两个皇后不能处于同一行,所以每行需要放且只能放一个皇后,可以用一个长度为 $8$ 的数组来表示每一个解。 $results[i]=j$ 就表示第 $i$ 个皇后放在位置 $(i,j)$ 上。
约束2:任意两个皇后不能在同一列
那么对于任意的 $ i \not= j$,都有 $ results[i] \not= results[j] $
约束3:任意两个皇后不在对角线上
如果不在45度对角线上,那么对任意的 $ i \not= j$,都有 $ results[i] + i \not= results[j] + j $
如果不在135度对角线上,那么对任意的 $ i \not= j$,都有 $ results[i] - i \not= results[j] - j $
求解某一个解的伪代码
1 | while i≤8 do{//当前行号i≤8 |
代码
1 |
|