“八皇后”问题 18501 崔萌萌 吕金华.

Presentation on theme: "“八皇后”问题 18501 崔萌萌 吕金华."— Presentation transcript:

1 “八皇后”问题 18501 崔萌萌 吕金华

2 问题阐述如何能够在 8×8 的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃
大家跟我一起做吧！！！ 问题阐述如何能够在 8×8 的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃 为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。

3 历史 八皇后问题最早是由国际西洋棋棋手马克斯·贝瑟尔于1848年提出。之后陆续有数学家对其进行研究，其中包括高斯和康托，并且将其推广为更一般的n皇后摆放问题。八皇后问题的第一个解是在1850年由弗朗兹·诺克给出的。诺克也是首先将问题推广到更一般的n皇后摆放问题的人之一。1874年，S.冈德尔提出了一个通过行列式来求解的方法，这个方法后来又被J.W.L.格莱舍加以改进。 艾兹格·迪杰斯特拉在1972年用这个问题为例来说明他所谓结构性编程的能力。 八皇后问题在1990年代初期的著名电子游戏第七访客和NDS平台的著名电子游戏雷顿教授与不可思议的小镇中都有出现。

4 1 明确走法 后（Queen）是最强的棋子，可横走、直走或斜走，移动步数不限，但不可转向或越过其他棋子。可以说是车与象的结合。

5

6 2 分析问题 我们采用逐步试探的方式，先从一个方向往前走，
2 分析问题 我们采用逐步试探的方式，先从一个方向往前走， 能进则进，不能进则退，尝试另外的路径。我们将棋盘看作是一个8*8的数组，这样可以使用一种蛮干的思路去解决这个问题，这样我们就是在8*8=64个格子中取出8个的组合，C(64,80) = ,显然这个数非常大，在蛮干的基础上我们可以增加回溯，从第0列开始，我们逐列进行，从第0行到第7行找到一个不受任何已经现有皇后攻击的位置， 用回溯的方法解决8皇后问题的步骤为： 1）从第一列开始，为皇后找到安全位置，然后跳到下一列 2）如果在第n列出现死胡同，如果该列为第一列，棋局失败，否则后退到上一列，在进行回溯 3）如果在第8列上找到了安全位置，则棋局成功。 8个皇后都找到了安全位置代表棋局的成功，用一个长度为8的整数数组进行回溯，直到为0-7列都找到了安全位置或者找遍这些列都找不到安全位置的时候终止。

7 代码代码！！！ 注意输出分为两部分1 计算排列种数 2 罗列排列方法

8 #include <stdio.h> #include <stdlib.h>
#include <math.h> int n=8;定义的一个全局变量 int x[9];一个含有九个元素的一维数组 元素下角标用来表示皇后所在的列数，由题意知每一列必有一个皇后，所以我们规定皇后的列不变，只进行行移动 int num=0;计数 int place (int k)位置函数 void nqueens (int n)移动函数

9 int main() 简短的主程序。。。。。
{ nqueens(n); return 0; }

10 void nqueens (int n)定义一个函数用来移动皇后的位置
{ int i; x[0]=x[1]=0;第一个皇后和第二个皇后放在同一列 int k=1; while (k>0) x[k]+=1;将第二个皇后移动一行 while (x[k]<=n&&0==place(k))调用函数判断位置是否 { 符合条件 x[k]+=1; }

11 if (x[k]<=n) { 计数结构 if (k==n) { num++; printf ("%d\t",num);

12 for (i=1;i<=n;i++) { printf("%d\t",x[i]);输出第i 个皇后的行位置 } printf ("end\n"); else k++; x[k]=0; k--；回溯结构若X>8时进入此结构，移动上一个皇后的位置

13 int place (int k) 定义一个函数来判断皇后的位置是否符 合条件
{ int i=1; while (i<k) if (x[i]==x[k] 判断同一行是否有两个皇后||(fabs(x[i]-x[k])==fabs(i-k)))判断一个皇后的四个对角方向是否有其他皇后 return 0;若符合条件返回值为零 i++;进入下一列的判断 } return 1;

14 问题时间！！！