挑战“八皇后问题”★★★★★★

挑战“八皇后问题”★★★★★★

     学习计算机编程的人一般都知道“八皇后问题”。解“八皇后问题”是学习PASCAL、QB、VB、C++等语言的基础问题之一，而用LOGO语言求解的却难以见到。所以我们说是“挑战‘八皇后问题’”。

 

    八皇后问题是一个古老的数学问题，该问题由十九世纪著名的数学家高斯在1850年提出：在国际象棋中棋子“皇后”具有最为灵活的“攻击手段”：它不仅可以横着、竖着走，还能沿着从左上——右下、右上——左下斜向走棋子。如果在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，那么将会有多少种摆法呢？

    显然，这涉及到极其庞大的计算量：因为每行棋盘都有8种放置棋子的可能，所以全部的排列组合达到8的8次方，即16777216种可能。即使在剔除了横行和纵列重复摆放棋子的情形，排列组合数也有8!=40320种。如果再加上判断棋子在所有斜线方向上是否有冲突，这确实涉及到“天量”的计算工作量。

    我们定义了数组A[8]，假如第一行的棋盘皇后应该放置在第3格，那么A[1]就赋值3……如果把程序设计成从A[1]～A[8]都只有1～8其中的1个数值、而没有重复的数字的话，就已经达到避免棋子的横向、纵向相冲突的目的了。

    在此基础上，还要排除各个棋子在同一个对角线的情形：把棋盘的横行数定为I，纵列数定为J,I和J的取值范围都是从１到８。当某个皇后占了位置(I,J)时，对于处在同一个“从左上到右下对角线上的棋子”，它们的I-J值是相等的；对于处在同一个“从右上到左下对角线上的棋子”，他们的I+J值是相等的。用数组循环的方式就能逐一排除掉对角线上冲突的棋子。

    编程求解八皇后问题有多种方法，程序风格比较优美的当然是用递归回溯算法，但是递归程序需要耗费大量的计算机资源为LOGO系统所不能承载。在这里我们使用了8重循环来解决这个问题。需要特别说明的是：在不是十分必要的情况下，编写程序时应当避免使用过多层次的循环嵌套。

    这个问题共有92种解。程序编写成能自动记录开始运行和结束的时间。庞大的计算量，即使在硬件中上等配置的“双核”CPU计算机上，这个问题也要30多分钟的时间才能给出全部答案。

 

TO QUEEN   ;著名的8皇后问题

  DRAW HT MAKE "A ARRAY 9 ;定义数组

  PR TIME ;输出开始的时间

  MAKE "N 0  ;开始时设定解的总数为0

  MAKE "BZ 0 ;设定标志=1时获得正确的解

  FOR "A1 1 8[FOR "A2 1 8[FOR "A3 1 8[FOR "A4 1 8[FOR "A5 1 8[FOR "A6 1 8[FOR "A7 1 8[FOR "A8 1 8[JC]]]]]]]]

  PR TIME ;输出结束的时间

END

TO JC ;检测程序段

  ASET :A 1 :A1 ASET :A 2 :A2 ASET :A 3 :A3 ASET :A 4 :A4

  ASET :A 5 :A5 ASET :A 6 :A6 ASET :A 7 :A7 ASET :A 8 :A8 ;读出组合出的棋子排列

  FOR "L 1 7[FOR "M :L+1 8[IF (AGET :A :L)=(AGET :A :M) THEN[GO "NEXT_]]] ;排除重复数字(排除纵横冲突)

  MAKE "BZ 0

  FOR "I 1 7[FOR "J :I+1 8[PDD :I :J IF :BZ=1 GO "NEXT_]] ;循环检验对角线是否冲突

  IF :BZ=0 THEN PRI ;调用输出答案的过程

  LABEL "NEXT_

END

TO PDD :I :J ;判对角线上是否有冲突断程序段

  IF (:I+AGET :A :I)=(:J+AGET :A :J) THEN[MAKE "BZ 1] ;发现从右上到左下对角线冲突

  IF (:I-AGET :A :I)=(:J-AGET :A :J) THEN[MAKE "BZ 1] ;发现从左上到右下对角线冲突

END

TO PRI ;以文本方式输出棋盘排列

  MAKE "N :N+1  ;解的总数增加1

  TYPE :N TYPE[=] ;TYPE TIME TYPE[=]

  FOR "K 1 8[TYPE AGET :A :K TYPE CHAR 32]PR[] ;画出皇后棋子

END

 

    程序的输出形式可以有两种选择：上面的程序是第一种方式，即在文本区输出答案。例如，输出答案之一是：6 =2 5 7 1 3 8 6 4 。这告诉我们，这是第6组答案，八个皇后棋子的排列是：第1行在第2列、第2行在第5列……

QUEEN_A

8 29 36……………………输出计算机开始计算的时分秒

1 =1 5 8 6 3 7 2 4

2 =1 6 8 3 7 4 2 5

……

36=4 2 8 6 1 3 5 7

37=4 6 1 5 2 8 3 7

……

91=8 3 1 6 2 5 7 4

92=8 4 1 3 6 2 7 5

9 6 14……………………输出计算机计算结束的时分秒

    LOGO语言具备画图的优势，程序的答案还能以图形的形式直观地在作图区进行显示，只要把PRI输出过程换用下面的程序就可以了。本文开始的两张图，是LOGO程序输出的第4种答案和第8种答案的棋子排列图形和每行棋子的位置值。

 

TO PRI ;以图形方式输出棋盘排列

  DRAW HT MAKE "N :N+1  ;解的总数增加1

  PU SETXY SE -110 140 PD TT "NO. ;显示解的组数

  PU SETX XCOR+30 PD TT :N

  SETPC 9 SETW 1  ;画棋盘格

  FOR "X 1 9[PU SETXY SE 30*:X-120 120 PD SETY -120]

  FOR "Y 1 9[PU SETXY SE -90 150-30*:Y PD SETX 150]

  FOR "K 1 8[PU SETXY SE -110 140-30*:K PD TT AGET :A :K]  ; 在图形左边输出棋子位置值

  SETW 20 SETPC 12 ;棋子宽20、红色

  FOR "K 1 8[DOT SE 30*(AGET :A :K)-105 135-30*:K]  ;用笔宽20的点画出皇后棋子

END

 

    在使用LOGO语言编程求解“八皇后问题”成功之后，我们从心里由衷地发出这样的赞叹：LOGO语言的功能是如此地丰富、强大，我们真的是应该重新评价和认识LOGO语言！

 

来自:http://blog.sina.com.cn/s/blog_5fd454d00100fibl.html