论文部分内容阅读
八皇后问题首先是由高斯提出来的,是回溯法算法的典型例题.随后,这个问题扩展为n皇后问题.在1969年,由Hoffman、Loessl和Moore给出了n×n棋盘问题的排列方法.本论文研究的是棋盘衍生为三角形棋盘时可以排放的最多的点的数目。 本论文研究的问题是:给定一个两直角边长都为n的直角三角形网格,令N(n)表示可以放到这个直角三角形网格中的最多的点的数目,并且使每一行、每一列、每一个东南到西北方向的斜和每一个西南到东北方向的斜至多可以放一个点,求N(n).已经证明:当n=3t+1时,N(3t+1)=2t+1(t≡0,2(mod3));2t≤N(3T+1)≤2t+1(t≡1(mod3),并且给出了一些计算机搜索的例子.当n=3t时,N(3t)=2t(t≡0,2(mod3));2t-1≤N(3t)≤2t(t≡1(mod3),并且给出了一些计算机搜索的例子.当n=3t+2时,N(3t+2)=2t+1。 全文共分四章。 第一章,综述了n皇后问题的研究背景,并给出了相关概念的具体定义以及当前领域的研究成果。 第二章,用不等式方法给出了三角棋盘中Brook的布置的证明。 第三章,对三角棋盘中皇后的布置给予了研究,分为n=3t,3t+1,3t+2三种情况分别讨论.对于n=3t(t≡1(mod3))或3t+1(t≡1(mod3))没有研究出来的情况也给予了范围的界定和计算机搜索的小例子。 第四章,对文章进行了总结,概述了文章的主要结论。