（计算机软件与理论专业论文）n皇后问题解的构造及等价性分析.pdf

摘要 本文主要研究了n 皇后问题似q p ) 解的构造及等价性分析。迄今为止，八皇 后问题以及n 皇后问题已经被讨论和研究了近1 6 0 年时间。主要的研究范围是 在给定的正整数n 的条件下：求n 皇后问题的一个解；求n 皇后问题的所有解； 求n 皇后问题的一组基础解。已有多位研究者使用公式方法直接构造出n 皇后 问题的一个解，不需要对其解空间进行搜索。但求解所有解和基础解目前还只能 依靠回溯算法对其解空间进行搜索，已求得n q p 所有解的有记载的最大n 值仅 为2 5 ，但其解的总数已经多达2 2 0 7 8 9 3 4 3 5 8 0 8 3 5 2 ，所耗费的时间相当于约共5 3 年c p u 时间。n q p 没有获得重大的突破性进展。近年来，n q p 主要被用于人工 智能领域测试各种智能搜索算法。 本文首先回顾了关于n q p 的一些主要文献，介绍了n q p 几种不同角度的定 义、构造n q p 的部分解的多种构造算法以及搜索n q p 所有解和基础解的算法。 本文通过对n q p 解的特点进行分析，以n q p 的函数定义为工具，论证了n q p 解的二维旋转变换和三维旋转变换等几何变换及其复合变换，提出确立基础几何 变换的方法，分析给出几何变换的时间复杂度为o ( n ) ，并论述了几何等价关系。 本文进一步研究并提出n q p 解的线性变换和线性等价关系，以滑动窗口为工 具论证了x u 滑动变换、y u 滑动变换、w 滑动变换及其之间的关系，分析给出 了最坏情况下线性变换的时间复杂度为o ) ，提出并论述了线性基础解。 本文构造了与已有研究成果不等价的n q p 的部分解，设计给出时间复杂度为 。洲2 ) 的从n 一1 问题域到n 问题域的递推算法，最后综合了几何变换、线性变换 以及递推算法设计并实现一个推导算法可以从n q p 解的集合f m 推导出基于f m 的一簇解f n 。 关键词：n 皇后问题，几何等价，线性等价，构造解，递推算法 a bs t r a c t t t l i sd i s s e n 纰i o nm a i l l l yd i s c u s s e st h ec o n s t r u c t i o na i l de q u i v a l e n c e 锄a l y s i so f t h e s o l u t i o n st ot h en q 啊e e i l sp r o b l e m ( n q p ) s 0 蠡玛8 一q u e e n sp r o b l e ma n dn q u e e l l s p r o b l e ml l a v ea k e a d yb e e nd i s c u s s e da n ds t u d i e d 南ra p p r o x i 眦t e l y16 0y e a r s 1 k m a i l ls c o p eo ft h es t l l d yu n d e rt h ec o n d i t i 0 i 岱o fp o s i t i v e 缸e g e rni s ：as o l u t i o nt o n q ea l ls o l u t i o l l st on q 只a n da 印u po f 向n 出l m e n t a ls o l u t i 0 璐t on q pm 锄y r e s e a r c h e r sh a v eu s e dt h e 向m m l ai n e t l l o dt od 沁c t l yc o 喊m c to n es o l u t i o nt on q 只 w i t h o u tt h en e e dt os e a r c ht h es p a c eo fs o l u t i o n s h o w e v e r ，南ra us o l u t i o i l sa n da g r o u po fm n d a m e n t a ls o l u t i o i l s ，t h eo n l yv a l i dm e t h o di sb a c h r a c k i i l ga 埯o m l 蚰f 0 r a l ls o l u t i o l l st on q 只t h em a ) 【i m 啪nv a l u er e c o r d e di sm e r e l y2 5w i t ht h e 姗m b e ro f s o l u t i o n s2 2 0 7 8 9 3 4 3 5 8 0 8 3 5 2 ，w l l i c ht a l ( e sac p ut i l l l eo f a b o u t5 3y e a r s t h e r ei sn 0 m 勾o rb r e 出h r o u 曲南rn q pi nr e c e my e a r s ，n q ph a sb e e nm a i l l l yu s e d 南rv a r i o u s 缸e l l i g e n c es e a r c ha l g o 瑚吼t e s t 堍i i la n i 丘c i a l 缸e n i g e n tf i e l d 1 k sd i s s e r t a t i o n 缸s tr e v i e w sl i t e r a t u r ec o n c e m i l l gn q pa i l di n t r o d u c e s t h e d e f m i t i o n so fn q p 劬md i 虢r e mp e r s p e c t i v e s ，d i v e r s ec o 蜮r u c t i o na l g o r “ho f c o n s t r u c t i i l gs o m es 0 1 u t i o i l st on q 只a n d t h ea k o r i t h mo f s e a r c h i l l ga l ls o l u t i o n sa n d f h n d 锄e n t a ls o l u t i o n st on q p t h e nt h r o u 曲t h ea 1 1 a l y s i so ft h ec 1 1 a r a c t e r i s t i c so ft h es o l u t i o i l st on q ew e d i s c | u s sp r o o 蠡o ft h eg e o m e t r i c a lt r a i l s f o r i l l ，i 1 1 c l u d i l l gt h et w o d 油e n s i o m la n dt 1 1 r e e d i m e n s i o m lr o t a t i o nt r a n s f o r m s ，觚dt h e i rc o 瑚l p l e xt r a i l s 南n 】 1 s ，w “ht h et 0 0 1o f f h n c t i o nd e f - m i t i o no fn q pw 宅a l s 0b r i i l gf o r v 旧r dt h em e t h o d st oe s t a b l i s h 如n d a m e n t a lg e o m e t r i c a lt r 甜1 s 南r m ， a 1 1 a l y z et h et i m ec o i n p l e x i t yo fg e o m e t r i c a l t f a i l s 南肌b e i l l go ( n ) ，觚dd i s c u s st h eg e o m e t r i c a le q u i v a l e n c er e l a t i o n s l l i p w r e 胁h e ri i l v e s t 适a t ea n da d v a n c et h er e l a t i o n s l l i pb e t w e e nl i l l e a r 仃a i l s 南珊a r l d l i n e a re q u i v a l e n c eo fs o l u t i o l l st on q p w i t hs l i d i n gw i n d o wa st o o l ，w ep r o v et h ex u s l i d i l l gt r a l l s f o m ，y us l i d i l l gt m n s 南m ，w i l vs l i d i i l gt 瑚s 幻r n l ，a 1 1 dt h er e l a t i o i l s l l i p a m o n gt h e m b e s i d e s ，、ea m l y z ea 1 1 dp u tf b n a r dt h a tu n d e rt h e 、o r s tc o n d i t i o n ，t h e t i l i l ec o i n p l e 妞yo ft h el i n e a rt r a n s f o r i l li so ( n 3 ) ，a i l da d v 锄c ea n dp r o v et h el i i l e a r 亿n d 锄m e m a ls o l u t i o n s w h a t sm o r e ，t l l i sd i s s e n a t i o nc o n s t m c t ss 0 m es o l u t i o l l st on q pn o te q l l i v a l e n tt o t h ep r i o fr e s e a r c hr e s u h s ，锄dd e s 适1 1 st h er e c u r r e n c ea l g o r i t l l i i l 舶mn - ld o 脚i l lt on d o i m i i lw i t ht i i i l ec o n 】p l e 妣yo ( n 2 ) f i n a l l y 、v ei n t e g r a t eg e o m e t r i c a lt r a n s 南锄， l i n e a rt r 吼s f o 姗，a i l dr e c u r r e i l c ea l g o 血ht od e s i g n 觚di m p l e m e n tad e m l c i i l g a l g o r i t l l 】【1 1 ，w i t hw h i c hw ec a nd e d u c eac 奴e ro fs o l u t i o n sf n 舶mf m ，t h es e to f s o l m i o i l s t 0 n q p k e yw o r d s ：n q u e e l l sp r o b l e m ，g e o m e t r i c a le q u i v a l e n c e ，l i n e a re q u i v a l e n c e ， c o i l s t n 自c t i o ns o l u t i o n ，r e c u r r e n c ea l g o r i t h l ：n 论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论 文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文 的研究作出重要贡献的个人和集体，均己在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：钇肜等 醐：唠严月7 日 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学 校有权保留学位论文并向国家主管部门或其指定机构送交论文的电 子版和纸质版，有权将学位论文用于非赢利目的的少量复制并允许论 文进入学校图书馆、院系资料室被查阅，有权将学位论文的内容编入 有关数据库进行检索，可以采用复印、缩印或其他方法保存学位论文。 学雠文作者虢百主啤导师虢维歹纲 f 1 期：啊年丫月7 日 日期：a 诞年，月，日 | 1 。1 研究背景 第一章概述 n 皇后问题( n q p ) 可以描述为：在n n 国际象棋棋盘上放置n 个皇后，使 其不能互相攻击。由于国际象棋中的皇后可以在同一行、或同一列、或同一斜线 上行走，因此在同一行、或同一列、或同一斜线上不能放置多于个皇后。 n 皇后问题( n q p ) 是由八皇后问题扩展而来的。八皇后问题最早在1 8 4 8 年由 一个德国的国际象棋爱好者m b e z z e l 首先提出并发表，接着从1 8 5 0 年开始c f g a u s s 对八皇后问题有比较深入的研究 1 】。f n a u c k 首先完全求解了八皇后问题 的全部9 2 个解【2 】。 迄今为止，八皇后问题以及n 皇后问题( n q p ) 已经被讨论和研究了近1 6 0 年 时间。主要的研究范围是在给定的正整数n 的条件下：求n 皇后问题的一个解； 求n 皇后问题的所有解；求n 皇后问题的一组基础解。已有多位研究者使用公 式方法直接构造出n 皇后问题的一个解，不需要对其解空间进行搜索。但求解 所有解和基础解目前还只能依靠回溯算法对其解空间进行搜索，已求得n q p 所 有解的有记载的最大n 值仅为2 5 ，但其解的总数己多达2 2 0 7 8 9 3 4 3 5 8 0 8 3 5 2 ，所 耗费的时间相当于约共5 3 年c p u 时间 3 】。n q p 没有获得重大的突破性进展。 近年来，n q p 主要被用于人工智能领域测试各种智能搜索算法。已知的n q p 其他应用还有：奇偶校验编码【4 】、图的着色 5 】、质数理论的证明 6 】、超大规模 集成电路( v l s l ) 测试【7 】以及并行内存存取模式设计 8 】等。 1 2 研究目的 本文在已有研究成果的基础上，专注于研究n q p 解的构造问题以及等价性问 题，分析n q p 解本身所具有的本质特点，找出n q p 解之间的内在关系，研究其 等价性，并根据其特点，设计构造与已有研究成果不等价的n q p 部分解。 总的思路就是避免对n q p 的全部解空间进行蛮力枚举搜索，通过公式在多项 式时间复杂度构造出多个解，然后通过各种变换派生出另外一些等价的解，所有 这些能够在多项式时间复杂度构造和推导出的解，虽然不是n q p 的全部解，但 数量并不少。 本文的研究方法和研究成果可以对n q p 其它方面的研究提供理论支持，也能 有助于其它类似领域的研究。例如棋类对弈、排课算法设计等领域，实际应用中 不一定需要找到满足约束条件的所有解，但如果能够在足够快的时间内找到数量 并不少的一部分解，再从中挑选一个最优解，则可以在有限时间内相对完美地解 决计算规模比较大的问题。 1 3 本文结构 第一章介绍了n q p 的研究背景、研究目的以及本文结构。 第二章回顾了关于n q p 的一些主要文献，介绍了n q p 的定义、构造部分解 的算法以及求解所有解和基础解的算法。 第三章以n q p 的函数定义为工具，论证了n q p 解之间的几何变换及其复合 变换，提出确立基础几何变换的方法，分析几何变换的时间复杂度，并论述了几 何等价关系。 第四章进一步研究并提出n q p 解的线性变换和线性等价关系，以滑动窗口为 工具论证了x u 滑动变换、y u 滑动变换、w u 。v 滑动变换及其之间的关系，分析最 坏情况下线性变换的时间复杂度，提出并论述了线性基础解。 第五章构造了与已有研究成果不等价的n q p 的部分解，设计从n l 问题域到 n 问题域的递推算法，最后综合了几何变换、线性变换以及递推算法设计一个推 导算法可以从n q p 解的集合f m 推导出基于f m 的一簇解f n 。 2 2 1n q p 的定义 第二章文献回顾 2 1 1 标准n 皇后问题 标准n 皇后问题( s t a n d a r dn q u e e i l sp r o b l e m ，s n q p ) ，简称n 皇后问题 ( n q u e e 璐p r o b l e i n ，n q p ) 。下面从不同角度给出n q p 的定义。 2 1 1 。1 代数定义 n q p 的代数定义( a l g e b r a i cd e f m i t i 0 1 1 ) 可描述如下： 记整数集合a _ 0 ，1 ，2 ，n - 1 ) 。a 的笛卡尔乘积记为b ，即b = a a = 。从集合b 中选择n 个 元素组成集合c ，若c 的笛卡尔乘积c c 中的每一个元素( ( i l 【，j k ) ，( 毛，j d ) ，能满 足以下的所有条件或是每个条件都不能满足： i k i g j k j g 不在同一列上 不在同一行上) i k + j k i g + j g 不在同一对角线上 i k - j k i g - j g 不在同一对角线上) 那么集合c 就是n q p 的一个解【9 】。 2 1 1 2 模运算定义 n q p 的模运算定义( m o d u l a r 时i t h m e t i cd e f m i t i o n ) 可描述如下【1 0 】： 记整数集合a _ 0 ，1 ，2 ，n 2 1 ) 。从集合a 中选择n 个元素组成a 的子集， 记为b 。若b 的笛卡尔乘积b x b 中的每一个元素( x ，满足以下的所有条件： ( ) ( 瑚d ( ym o dn ) x n y n 不在同一列上 不在同一行上) x n + ( xm o dn ) y n + ( ym o dn ) 不在同一对角线上 i x n 一1 n o dn ) l l y n 一( yl n o dn ) l 不在同一对角线上 那么集合b 就是n q p 的一个解。其中，x y ，符号“li 表示求绝对值， 符号“”表示整数除法。 2 1 1 3 约束满足问题 n q p 也可以表述为约束满足问题( c o 蜮r a 缸s a t i s 觚i o np r o b l e l t l ，c s p ) 【1 1 】。 约束满足问题的常规定义可描述如下： c s p 由元组 n ，硒，r l ，r n 1 ，p o 】，p 0 2 ，p n 2 ，n 1 ) 构成，且： ( 1 ) 整数n 表示变量( 】【o ，x l x n 1 ) 的个数； ( 2 ) r i 是一个集合，其元素可以赋值给变量x j ； ( 3 ) 笛卡尔乘积r i r 的子集表示约束关系。 n q p 使用c s p 定义可描述如下： 令r 0 - r l - = r n 1 = r ，p i j = r i 玛一p i j ) ，其中p i j = ( x ，y ) r i r j ，l x y i - | i - j iu x + y = 川ux = y 。显然，p i j = p ! i i 。对于一组赋值皑a o ，a l ，a n 1 ) ，若满足： ( 1 ) 对于所有i ，a i 是r 的一个元素 ( 2 ) 对于所有i j ，( a i ，码) ，其中0 岣n 一1 那么a 就是n q p 的一个解。例如：令n = 4 ，那么肛r l = r 2 = r 3 = 0 ，1 ，2 ，3 ) ， 且p o l = ( o ，2 ) ，( o ，3 ) ，( 1 ，3 ) ，( 2 ，0 ) ，( 3 ，0 ) ，( 3 ，1 ) ， p 铲 ( 0 1 ) ，( o ，3 ) ，( 1 ，o ) ，( 1 ，2 ) ，( 2 ，1 ) ，( 2 ，3 ) ，( 3 ，o ) ，( 3 ，2 ) ) ， p 0 3 = ( o ，1 ) ，( o ，2 ) ，( 1 ，0 ) ，( 1 ，2 ) ，( 1 ，3 ) ，( 2 ，0 1 ) ，( 2 ，1 ) ，( 2 ，3 ) ，( 3 ，1 ) ，( 3 ，2 ) ) ， p 1 2 = ( o ，2 ) ，( 0 ，3 ) ，( 1 ，3 ) ，( 2 ，o ) ，( 3 ，0 ) ，( 3 ，1 ) ) ， p 1 3 2 ( o ，1 ) ，( 0 ，3 ) ，( 1 ，o ) ，( 1 ，2 ) ，( 2 ，1 ) ，( 2 ，3 ) ，( 3 ，0 ) ，( 3 ，2 ) ) ， 4 p 2 3 = ( 0 ，2 ) ，( o ，3 ) ，( 1 ，3 ) ，( 2 o ) ，( 3 ，0 ) ( 3 ，1 ) ， 若有集合a ( 例如a = 1 ，3 ，0 ，2 ) ) 满足所有的约束条件，那么a 就是n q p 的一 个解。文献【1 2 】使用不同于此的其他表述形式来描述c s p 。文献【1 3 】应用分布式 条件使用c s p 定义和求解n q p 。 2 1 1 4 最大稳定集问题 最大稳定集问题( m a ) 【咖ms t a b l e s e tp r o b l e m ) ，也称最大独立集问题 ( m a ) ( i m u mi n d e p e n d e n ts e tp r o b l e m ) ，其定义可描述如下【1 4 】： 给定一个图g = e ) ，其中，v 是顶点的集合，e 是边的集合。若v 的子集 v 中任何两个顶点都不连接于e 中的任何一条边，则称v 是图g 的稳定集。图 g 的稳定集的最大基数称为图g 的稳定数。具有最大基数的稳定集就称为最大 稳定集。 要把n q p 映射为最大稳定集问题，可以把棋盘描述为图g ：棋盘的每个方格 抽象为顶点，这些顶点的集合组成v ；任何处于同一行或同一列或同一对角线上 的两个顶点之间连接一条边，这些边的集合组成e 。n ( n 4 ) 是图g 的稳定数。 图g 的任何一个最大稳定集都是n q p 的一个解。 2 1 1 5 最大团问题 既然n q p 可以定义为最大稳定集问题，那么同样也可以定义为最大团问题。 最大团问题( m a x i i n u mc l i q u ep r o b l e m ) 的定义可描述如下【1 5 】： 给定一个图g = ( v ，e ) ，其中，v 是顶点的集合，e 是边的集合。若v 的子集 v 中任何一个顶点都连接于e 中的边，则称v 是图g 的团。具有最大基数的团 称为最大团。 要把n q p 映射为最大团问题，可以把棋盘描述为图g ：棋盘的每个方格抽象 为顶点，这些顶点的集合组成v ；任何不处于同一行或同一列或同一对角线上的 两个顶点之间连接一条边，这些边的集合组成e 。基数为n ( n 4 ) 的团就是n q p 的一个解。 5 2 1 1 6 整数规划问题 n q p 也可以定义为整数规划问题( i n t e g e rp r 0 争a 删= n i l l gp r o b l e m ) 【1 5 】： 国际象棋棋盘的每个方格记为酗，其中i ，j = 0 ，1 ，n l 。那么n q p 可以映 射为如下定义的模型： 求最大值： 却 i ，j = o ，l ，n - 1 l j 同时满足： 1 2 y 澍：l j - o 。 ，= l y 勘：1 j 一 。 f = l i = o ，1 ，n 一1 j = 0 ，l ，n 一1 3 耐1 k = l ，2 ，2 n - 3 f + = 1 7 - 、 4 ：勋lk = 一n - 2 ，j n + 3 ，n - 2 一 j 一= 七 其中，对于所有的i 和j ，x 旷o 或确= l 。 条件1 和2 保证了每行和每列分别只能摆放一个皇后，条件3 和4 保证了每 个对角线上最多只有一个皇后。满足此模型的一个解就是n q p 的一个解。 2 1 2 模n 皇后问题 与标准n 皇后问题类似，模n 皇后问题( m o d u l on q u e e n sp r o b l e i i l ，m n q p ) 也可以从不同角度给出定义。下面给出其代数定义： 记整数集合a = 0 ，1 ，2 ，n 1 ) 。a 的笛卡尔乘积记为b ，即b = a a = ( o ，0 ) ， ( o ，1 ) ，( 0 ，n 1 ) ，( 1 ，0 ) ，( 1 ，1 ) ，( n 1 ，0 ) ，科一l ，n - 1 ) 。从集合b 中选择n 个 元素组成集合c ，若c 的笛卡尔乘积c c 中的每一个元素( ( i k ，j k ) ，( i g ，j g ) ) ，能满 足以下的所有条件或是每个条件都不能满足： ( 1 ) k 连 ( 2 ) j k j g 不在同一列上 不在同一行上) 6 ( 3 ) 破j l 【硼g ( m 1 ) dn ) 不在同一延伸对角线上) ( 4 ) 诮k i 西g( 1 d 不在同一延伸对角线上) 那么集合c 就是m n q p 的一个解；同时，c 也是n q p 的一个解。反之则不 一定成立。 2 2 求n q p 的部分解 2 2 1 构造算法 构造算法( c o n s t m c t i o n 趟g o r i t h m ) 是不需要搜索解空间，直接使用函数或公式 给出问题的结果的一类型算法的统称。 根据文献【1 】的研究整理，p 枷s 首先成功证明了定理2 1 【1 6 】。 定理2 1对于给定的整数n 3 ，n q p 至少存在一个解。 p a u l s 并给出了n q p 的构造解【1 7 】，如表2 1 所示。 表2 1p a u l s 的n q p 构造解 缓缓麟 n = 6 k ，6 k 十4 么= ( 2 l d l l f 兰 ，彳z = ( 2 f 一1 ，詈+ d 1 1 冬f 兰) ， 胙鼢，1 ) ，肛他卅1 ) 1 1 螂等) ， n = 6 k + l ，6 “5 趾犯，等删姚争， c t = = ( 4 ，1 ) ) ，c z = ： ( ，z ，1 ) ，c ，= ： ( 2 ，三) ) ， c 。= ( 以一l ，三+ 1 ) ，c s = ( 1 ，詈+ 2 ) ) ，c s = ( 甩一3 ，刀) ， n = 6 k + 2 c ，= 跏锄，) 1 1 f 詈- 3 ) ， c s = ( 刀一2 f 一3 ，兰+ f + 2 ) 1 1 f 三一3 ， 在n n 棋盘的左下角先构造( n 1 ) 皇后问题的解，然后在棋盘右上角 n = 6 k + 3 方格放置最后一个皇后。 7 此后，f r 锄e l 也使用模6 的剩余类分类给出了n q p 的一种形式的解 18 】，如 表2 2 所示。 表2 2f 陷n e i 的n q p 构造解 蘩鹚麟 噔悄h ) m o 弧训l 鲻詈 ， n 三2 ，4 ( m o d6 ) 唔+ 2 f + 1m o d 坞f + 争1 1 f 争， ( 1 ，1 ) ) ， n 兰3 ( m o d6 ) ( ( 字+ 2 ( ) m o 坼圳+ 1 ，川) 1 1 鲻孚) ， ( ( 竿秘m o _ 1 ) ) + 1 ，z + 掣) 1 1 姚孚 ， n e l ，5 ( m o d6 ) 驴+ 2 fm o d f ) 1 1 s f 刀 ，是任意整数， 力墨争， n e 0 ( m o d 回 ( 2 h 0 + 扣姚争， 后来，s c h e i d 又以模1 2 的剩余类分类给出了n q p 的另一种形式的解【1 9 】， 如表2 3 所示。 表2 3s c h e i d 的n q p 构造解 魏獬麓荔豢_ ，1 糍鬻鬈鬻鬟荔磁囊麓糕戮鬃缓篱翳j j 戮 n = 4 + 6 j( 2 ，4 ，l l ，l ，3 ，n - 1 ) ， n = 5 垧( 2 ，4 ，n - l ，1 ，3 ，n ) ， n _ - 舌峋( 2 ，4 ，n l ，3 ，n 1 ) ， n = 7 + 6 j( 2 ，4 一，n 1 ，l ，3 ，n ) ， n = 8 + 1 2 j( 2 ，4 ，i l 3 ，1 ，7 ，5 ，n - l ，n 3 ) ， n = 9 + 1 2 j( n ，4 6 ，n - l ，3 ，l ，7 5 ，n - 2 ，n 4 ，2 ) n = 1 4 + 1 2 i( n - l ，2 ，4 ，n ，3 ，l ，7 ，5 ，n 3 ，n - 5 ) ， n - 1 5 + 1 2 j( n ，n 幺2 ，4 ，m l ，3 ，l ，n 4 ，n 蛾 f a l k o w 晒和s c l l n 血z 共同给出了一种分为7 种类型的解【2 0 】，如表2 - 4 所示。 后来经过邬家邦改进，归纳为5 种类型【2 1 】，如表2 - 5 所示。 8 表2 4f 名的n q p 构造解 瀚麟憋溯滋麓麓簇缀鞫缀缀簇缀缓豢鬻懑矮缁鞠翳鬻黝缀簇缓囊黝缀戮戮蒸黧 球嗷。 ( 2 汕f 三田， ( 2 h 专刀+ 呻f 丢咄 6 1 吨 n 予6 k - 1 ， ( 2 d 1 1 f 主( 行一1 ) ) ， ( 刀，刀) ， 6 k + l ( 2 h ，吉仍- 1 ) + 呻s f 扣一城 ( 2 f + 1 ) i l f 言行 ， ( 4 f + 3 ，主刀+ 2 ( f + 1 ) ) l 。f 言( 疗一4 ) ， 萨1 2 k _ 4 ( 4 f + l ，丢，l + 2 ( f + 1 ) + 1 ) i o f 丢( 刀一8 ) ， ( ，z 一3 ，1 ) ， ( 2 f ，f + 1 ) i l f 圭，l ， ( 4 f + 3 ，三忍+ 2 ( f + l ”l o f s 丢( 力一6 ) ) ， n = 1 2 l h 2 ”川，三胆+ 2 ( ) + 1 ) i o f s 丢( 力一6 ) ) ，跏- 1 1 ) ) ， ( 2 川，) i l i s 丢( 刀- 1 ) ， n = 1 2 k + 3 ( 4 f + 4 ，兰( 刀一1 ) + 2 ( f + 1 ) ) i o f 丢( 玎一7 ) ， ”f + 2 ，三( n _ 1 ) + 2 ( 川) + 1 ) i o f s 丢( 刀一7 ) ) ，跏- 1 ，聃， ( 2 f + l ，丢( 3 船+ 1 ) 一f ) lo s f 吉( 行一1 ) ， ( 4 ，三( 拧一1 ) 一2 ( f 1 ) ) l o f 吉( ，z 一1 ) ) ， n = 2 4 k 15 ”沪2 ( f 书+ 7 ) = i ) l 孚姚扛1 ) ， ( 4 f + 2 ，丢( 以一5 ) 一2f ) lo f 吉( ”一9 ) ) ， ( 4 m ，川- 2 ( f 一言( ”) l 等f 三( 咒棚) ， ( 2 f + 1 ，言( 3 ，? + 1 ) 一d i 。f 丢( 以一1 ) ， ( 4 t 言( 胛+ 3 ) 一1 2 ( f 一1 ) ) 1 1 f 言( 刀+ 3 ) ) ， n = 2 4 k 3 - 2 ( f 一吉( 川1 ) ) ) l 半螂丢( 川) ) ， ( 4 f + 2 ，三( 刀一5 ) 一2 f ) l o f 吉( 疗一1 3 ) ) ， ( 4 m 扩2 ( f 一吉( 稍) ) ) l 孚姚丢( 硝) ) 9 表2 - 5 邬家邦的n q p 构造解 缓缴糕 带锨，6 妣 肛嘏2 洲剑血= 畸+ 删_ 1 ) l l 姚争， 西= ( 劲峪f 争， f 户6 k l ，6 k + l 曰z = i 掣+ 锄柚峪f 争， n = 8从8 个皇后的9 2 种布局任取其一即可。 凸= ( 1 ，拧一1 ) ，( 2 ，狞一5 ) ，( 刀，刀一3 ) ， d 2 = ( f + 2 ，2 f 一1 ) l l s f 争3 ) ， l r = 6 i 汁8 伤2 畸+ ，z 一6 秘) i 3 ) ， a = 噎m 2 ，2 洲姚争3 ， 西= ( 1 ，刀一2 ) ，( 2 ，力，p 芋，z 一1 ) ) ， 珏= 6 k + 3 e 2 = o + 2 ，2 z 1 ) 1 f s 兰一3 ： 凸= 掣m 1 渤雌f 三q ， h o 妇丘i l a n 、l o e s s i 和m o o r e 也共同给出了一种只需要分为3 种类型的解【2 2 】， 如表2 6 所示。 表2 - 6h l - m 的n q p 构造解 i 鬻i 灏鹈辅| 篓黍囊鬻黧鬓鬣瀵鬻戮鬻缓鬓鬻澎鳓躐繁蒸鬻麟熬缀鬻荔鬓鬓鬈鬻 ，2 川1 歹争， n = 6 k6 l c + 4 ( 三“2 川) l l 歹争， 幻，j + 【2 ( j f _ 1 ) + 争1 ( m 。d 纠) 1 1 歹 n = 6 k + 2 ，6 k + 4 鼢+ 1 刀_ 【2 ( 歹- 1 ) + 争1o n o d 枷b ，兰 ， n ；2 _ k + l 先构造( n 1 ) 皇后闯题的解，然后在方格( 坞n ) 摆放一个皇后。 l o a m 硇画d m 和i m m 也共同给出了一种只需要分为3 种类型的解【2 3 】， 如表2 7 所示。 表2 - 7 均l o m 的n q p 构造解 豢灞黧 n 嗡k 6 k m 仰埘+ l ，d i l j 争， ( 2 拧砌+ 2 ，圳詈+ l f 刀 ， 。划+ 2 0 1 2 i 三一2 ， l l = = 6 l 对2 ( 2 刀一2 f + 1 ，d i 兰+ 3 f 行一1 ) ， ( 4 ，1 ) ( 殇三- 1 ) ，( 2 ，争如- 1 ，三+ 叭三+ 2 ) 和_ 3 ，砒 n ：2 k + 1 先构造( n 1 ) 皇后问题的解，然后在方格沁n 耀放一个皇后。 丘维声使用模1 2 的剩余类分类给出了n q p 的另一种形式稍微复杂的解【2 4 】， 如表2 8 所示。 表2 - 8 丘维声的n q p 构造解 鬻爹i 黪溺麓豢嚣鬻谬缪臻，粼。誊黪i 虢鬻；攀鬻薯墨曩篓簦鬻帮簪j 露骖魏熊篙il ? 鍪囊登罄。曩誊鬈薹i ! 蓊熬鬻j 黪。雾嬲麟 n 三l ，5 ，7 ，l l ( m o d1 2 )y = 截x k ) + k ( m o dn ) ，1 x 玛船- 2 ，3 ，且0 k n - l n 5 4 ，6 ，lo ，1 2 ( m o d1 2 ) y = 淑( m o dn 十1 ) ，1 x n ，拮2 ，3 ，删除( 叶l ，n + 1 ) y 一3 x + n 2 ，i x l l ，3 1 ； y = 3 ，x 2 i l ，3 ； n e 3 ( m o d1 2 )y 一3 x - 2 n + 2 ，n ，3 + l x 2 n 3 ； y = 卅2 ，x = 2 n ，3 + l ； y = 3 x + 3 n + 6 ，2 n 倍+ 2 x n ； y 一2 x + ( i 卜1 ) ，2 ，l x ( n - 5 ) 4 ； y = ( n i ) 2 ，x ， n ：6 k + l ，6 k l a s ( n ) = s 1 2 s n 2 ，g c d ( s ( s - 1 ) ( s + 1 ) ，n ) = 1 ) ， ( n 2 ) ) 竹三c ( m o dn ) ，x = o ，n ，2 - 1 ，c s ( 1 妒： s 1 3 s m 5 ， n ；6 k + 2 ，6 k - 2 ( n - 2 ) x + y 兰c ( m o dn ) ，脊：n ，2 ，m 1 ，c s ( n ) ( n - 3 ) x + y 毫c ( m o dn ) ，) ，n ，3 - l ，c s ( n 户 s 1 4 s n - l o ) ， n = 6 k + 3 ( n 3 ) x + y j i c + 4 ( m o dn ) ，x = 1 1 3 ，力n 3 一l ，c s ( n ) ， ( n 3 ) x + y 毫c + 8 ( m o dn ) x - 2 们，n 1 ，c s ( 咄 ( n 2 ) x + y 兰l ( m o dn ) ，x = 0 ，n ，2 - l ， n = 6 l ( 6 k 2 ( n 2 ) x + y 三0 ( m o dn ) ，x = n ：2 ，i 卜1 ， ( n - 3 ) x + y 三c ( m o dn ) ，x = = 0 ，n ，3 - 1 ，c s ( n ) = ( ( 】【l + 3 ) 2 ，( 】【1 + 5 ) 2 ) ) ， n = 1 2 k 3 ( n 3 ) x + y 兰c - l ( m o dn ) ，x = 1 l 3 ，2 n 3 - l ，c s ( n ) ， ( n 3 ) x + y 三c - 2 ( m o dn ) ，x - 2 们，m 1 ，c s ( n ) ， 由于模n 皇后问题的约束条件强于标准n 皇后问题，因此模n 皇后问题的 任何解也是标准n 皇后问题的解。根据文献【l 】的研究整理，p 6 1 y a 首先证明如下 的定理2 2 【2 5 】。 定理2 2 模n 皇后问题存在至少一个解当且仅当g c d 仳6 ) = 1 。 特别地，当n 是质数p 时，b u s s e y 【2 6 】和s 如r z a 2 7 】先后给出m n q p 的解： f 【x ) 量时b ( m c h dp ) ，其中a ，b 是整数且a 一l ，o ，1 。 对于给定的p ，按上式可以构造出p ( p 一3 ) 个解。例如，对于m n q p ，当n _ 5 时，可以构造出1 0 个解；当n _ 7 时，可以构造出2 8 个解。 对于n q p ，当n _ 5 时所构造出的1 0 个解刚好是n q p 在n _ 5 时的所有解。n 取其它值时则不然，例如n _ 7 时n q p 共有4 0 个解，而此只能构造出2 8 个解。 基于心q p 的求解，a b f a m s o n 和g 给出并证明了一种求n q p 解的分治 法算法【2 8 】，可以构造出除了2 、3 、8 、9 、1 4 、1 5 、2 6 、2 7 、3 8 、3 9 外的任意n 值的n q p 解。图2 1 给出n = 5 5 时n q p 的一个分治法解。 1 2 _ _ _ _ _ _ _ _ _ _ _ 2 2 2 搜索算法 图2 1n = 2 5 时n q p 的一个分治法解 除了通过函数关系直接求出n q p 解的构造算法外，其它的算法广义上可以统 称为搜索算法( s e a r c ha l g o r i t h m ) 。 2 2 2 1 非确定性算法 非确定性算法( n o n d e t e m l i i l i s t i ca l g o 血h m ) 的非确定性在于其包含有一特殊的 基原c h o i c e ( n ) ，用于从n 个待选元素中作出一个选择。其算法思想是：从每行 中选择一个方格，要注意避免选中两个在同一列或同一对角线上的两个方格。选 出一行的某个方格后，输出该结果，然后转向处理下一行【9 】。算法如图2 2 所 示。 1 3 图2 - 2 非确定性算法 非确定性算法可以很容易转换为回溯算法 2 9 】。 2 2 2 2 回溯算法 回溯算法( b a c l 【t r a c k i i l g 砧g o r i t l l l l l ) 可以应用于搜索n q p 的所有解，也可以修 改结束条件，使其在搜索到一个解后就停止。经典回溯算法一般是配合深度优先 搜索算法实现。实验结果表明，使用经典回溯算法求n q p 的一个解，其时间复 杂度随问题规模的增长呈指数增长【3 0 】；在n 1 7 时， 求解n q p 所有解的时间完全取决于计算节点的数量，且成线性关系【4 3 】。目前 能够求得且有记载的最大n 值为2 5 ，对应的n q p 解的个数是2 2 0 7 8 9 3 4 3 5 8 0 8 3 5 2 ， 总共耗费的时问相当于约共5 3 年c p u 时间【3 】。 2 4 求n q p 的基础解 对于给定整数n 的n q p 所有解中，有些解是可以通过另一个解作几何上的 对称变换和旋转变换而得到的。能够相互通过对称变换和旋转变换而得到的两个 解是同构解【4 4 】。 例如，n