八皇后问题.ppt.ppt

八皇后问题;韩奇 刘源奇 鹿尧; 八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。 高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。计算机发明后，有多种计算机语言可以解决此问题。 ——《百度百科》;八皇后问题的一个解;作为例子，我们将8皇后问题简化为4皇后问题; 这是一颗四叉树，树上每个结点表示一个局部布局或一个完整的布局，根结点表示棋盘的初始状态：棋盘上无任何棋子。没个棋子都有四个可选择的位置，但在任何时刻，棋盘的合法布局都必须满足3??约束条件，即任何两个棋子都不能处于同一行、同一列或同一斜线上; ;*;程序实现： 这里我们用递归法和非递归法并进行比较; 递归法 VS 非递归法;;;;递递递递递递归法;;; 非递归法;*;*;*;以上