从八皇后问题的解决方案看面向过程和面向对象

宋东兴，殷旭东

（常熟理工学院计算机科学与工程学院，江苏常熟 215500）

从八皇后问题的解决方案看面向过程和面向对象

宋东兴，殷旭东

（常熟理工学院计算机科学与工程学院，江苏常熟 215500）

通过八皇后问题的解的分析，讨论了面向过程的解决方案和面向对象解决方案的不同，比较了面向过程设计思想和面向对象设计思想的区别和联系，提出程序设计教学要从面向过程逐步过渡到面向对象，片面强调一面而忽视另一面都是不可取的.

八皇后；面向过程；面向对象；对象；解决方案

著名数学家高斯在1850年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法？此即八皇后问题.八皇后问题可以采用面向过程和面向对象两种不同的解决方案.

在众多针对“软件危机”[1]的解决方案中，面向对象编程是一种优秀的方法，国内大多数高校的计算机专业都开设了面向对象的程序设计课程，有的学校大一就直接进入面向对象教学.然而要完全抛弃传统的面向过程方法，只接受面向对象方法并不科学，宏观上的面向对象思想从微观上看仍然是面向过程在实现，离开面向过程的铺垫而直接进入面向对象，学生理解起来往往比较困难，实际教学效果也不理想.笔者通过八皇后问题的求解案例，分析比较面向过程和面向对象的不同，提出程序设计教学要从面向过程循序渐进到面向对象.

1 面向过程的分析方法

1.1 基本思想

以过程作为分析的主题，着重强调一个系统中发生的过程以及由一个过程的结果输出作为下一个过程输入的数据流动，通过信息流及其状态转换来认识系统，采用的是“自顶向下，逐步求精”的思维方法，核心思想是：以事件为中心，分析解决问题的步骤，然后用函数把这些步骤一步一步实现，使用时依次调用就可以了.

1.2 八皇后问题的面向过程的解决方案

需要使用各种数据结构来保持棋子的位置，算法通过系统地控制每一个数据结构的数值，检测每个新位置是否符合没有皇后攻击其他皇后的原则来解决问题.

1.2.1 穷举法

解决八皇后问题的关键在于：

（1）找到合理的数据结构存放棋子的摆放位置.

（2）要有合理的冲突检查算法[2].采用的方法是，先把8个棋子摆在棋盘上，每行摆一个，然后去检查这种摆放是否有冲突，如果没有冲突，即找到了一种解决方案.

首先是如何存放棋子的摆放位置.可以设想一下，当8个棋子摆放好之后，每个棋子的位置都有一个行值和列值，由于每行只有一个棋子，就可以从第0行开始依次记录每个棋子的列值，8个棋子的列值依次排列构成一个数字序列，例如24135046，它表示第0行棋子摆放在第2列，第1行棋子摆放在第4列，以此类推，这样一种摆放方式对应一个8位的8进制数，用一个一维数组来存放这样一个8进制数，00000000-77777777穷举了所有的摆放方式.

接下来对每种摆放情况做冲突检查，若不冲突就是一个解.

注：(i，queen[i])代表一个棋子的行，列坐标.

冲突检查：（1）每行只放一个棋子，行上不会有冲突.

（2）数组中如没有两个元素值相同，则列上没有冲突.

（3）任意两个棋子（i，queen[i]），(j，queen[j])，只要有queen[i]+i!=queen[j]+j，且queen[i]-i!=queen [j]-j，则对角线上没有冲突.

为方便运算：将八进制数范围00000000-77777777表达成十进制，则范围为[0，88-1]，再将范围内每个十进制数转化为八进制数字存入queen数组中.

穷举算法：

1.2.2 回溯法[3]

回溯算法也叫试探法，它是一种系统化的穷举搜索问题的解的方法，基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试.在前进和回撤的路上都设置一些标记，以便正确返回，直到达到目标或者所有可能方案都已尝试为止.

从第一行开始，逐行安排皇后（Q），Q1从第一行的第一个位置开始尝试，然后尝试Q2，…Qi-1，使得前i-1个皇后互不攻击，再尝试Qi，如果第i行上没有剩余可放位置，则返回i-1行，同时使Qi-1放弃刚才摆放位置，并尝试下一位置，…当Q8成功放置时，则找到一种解.当Q8尝试过最后一行的所有位置后，算法结束.

回溯算法：

2 面向对象的分析方法

2.1 基本思想

面向对象分析方法的基本思想是：万物都可看作对象[4]，面向对象的系统是由一组互相作用的对象所组成的一个团体，每一个对象都扮演一个角色，并为团体中的其他成员提供特定的服务或者执行特定的行为，目标的实现来自于每个对象的努力和他们之间的相互协作.

2.2 八皇后问题的面向对象的解决方案

方案要点：创建代表每一个皇后的对象，然后赋予它们寻找解决方案的能力，八个皇后彼此之间相互作用，各自负责寻找自己的解决方案[1].

2.2.1 为皇后对象建模

分析：在任一解决方案中，不会出现空列，一列也不可能有两个皇后，可以为每一皇后指定一个特定列（col），而寻找一个合适的行（row）.为了找到解决方案，皇后们需要相互联系，每个皇后只需要了解它的邻居（neighbor），即紧挨着其左边的那个皇后.

第n列的可接受的解决方案可表示为：从第1列到第n列，没有皇后可以攻击其他皇后.每个皇后只需询问相邻皇后是否能够互相攻击.如果能够互相攻击，那么这个皇后就前进一行（如不能前进将返回失败），当相邻皇后返回不能互相攻击的信息时，解决方案就找到了，通过询问最右端的皇后，找到一个可能的解决方案，即可找到整个问题的方案.

2.2.2 Queen类的部分方法实现思路

①构造方法

为皇后对象建立必需的初始条件，行（row）从第0列开始，处于第n列皇后通过给定列号（col）以及相邻的皇后进行初始化.

图1 皇后类的UML表示

②寻找解决方案findsolution()

通过询问相邻皇后是否能够互相攻击，来寻找解决方案.如果能够互相攻击，那么这个皇后就前进一行（如不能前进将返回失败），当相邻皇后返回不能互相攻击的信息时，解决方案就找到了.

③皇后前进下一位置advance()

如果当前不是最后行，则行号（row）加1，否则当试验过本列所有位置后仍然没有找到解决方案时，就要求邻居皇后寻找新的解决方案，并且自己的行（row）位置重新从第0行开始.

2.2.3 八皇后问题的面向对象解

图2 findSolution()方法实现思路

3 面向过程和面向对象的解决方案比较

从八皇后的问题的解法来看，传统的面向过程的求解就像一个人坐在棋盘前，移动一些毫无生命的棋子，这种方式强调的是从一个行为到另一个行为的控制流，每一步过程的结果，都是下一步的前提条件，程序设计者必须事必躬亲，考虑系统的每一细节，什么时候对什么数据进行操作.当分析的系统规模较小时，面向过程的方法能取得较好的效果，但当系统逐比较大复杂时，由于系统组成预先不可知，加上系统组成之间的结构关系也不易弄清楚的情况下，面向过程的分析方法就难以胜任了.

而在八皇后问题的面向对象的解法中，我们赋予每一个棋子自己解决问题的能力[1].把寻找解决方案的责任分配给那些相互作用的皇后对象，每一个棋子就像一个有生命的个体，它们彼此相互作用，各自负责寻找自己的解决方案，这代替了那种由单一实体来控制结果的集中模式，当系统需求增加或发生变化时，只需在局部进行改变或增删操作，而不会影响整个系统的架构.

面向过程方法要求你为数据结构做些什么，而面向对象的方法则问数据结构为你做了些什么；面向过程采用的是一个过程状态转换模型，它与实际计算机内部的工作流程大致相吻合，但对于我们理解如何使用计算机来解决问题却没有什么帮助，面向过程采用的是“责任驱动”设计模型，与现实世界人们解决问题的方式相近，但无论是哪种方式对程序员来说都应该熟悉和掌握.教师在面向对象的程序设计教学中，选取一些典型的问题，引导学生用两种不同方式来思考解决，更有利于学生加深对面向对象的思维方式的理解，笔者在实际的教学中采用这种方式也取得了较好的效果.

4 结束语

面向过程和面向对象是两种不同的思考问题的方法，面向过程方法以事务为中心，侧重于分析解决问题所需的步骤，强调怎么实施，而面向对象是以事物为中心，把系统分解成若干对象，侧重某个对象在整个解决问题的过程中的责任（行为），强调实施什么.通过用责任来讨论问题，提高了抽象的水平，使得对象之间更加独立，这正是解决复杂问题的关键.

对于大多数问题，面向对象方法比面向过程方法优越，但并不意味着它能完全取代面向过程，事实上，从宏观角度来分析系统时采用面向对象，而从微观考虑一个对象的行为的具体实现时，离不开面向过程[5].这就要求程序设计课程教学要从面向过程开始，并在教学中及时渗透面向对象的思想，使学生逐步过渡到用面向对象方法思考问题.

[1]（美）Timothy A Budd.面向对象程序设计（影印版）[M].北京：清华大学出版社，2004.

[2]焦玲，邢伟，于海波，等.Java程序设计案例汇编[M].北京：中国铁道出版社，2008.

[3]严蔚敏，吴伟民.数据结构（C语言版）[M].北京：清华大学出版社，1997.

[4]（美）Bruce Eckel.Java编程思想[M].北京：机械工业出版社，2005.

[5]游晓明，刘升.面向过程向面向对象程序设计的转变与实现[J].湖北师范学院学报，1999（2）.

Observing Procedure-oriented and Object-oriented from the Solution to the Eight-queen Puzzle

SONG Dong-xing,Ying Xu-dong,LIU Yong-jun
(School of Computer Science and Engineering,Changshu Institute of Technology,Changshu 215500,China)

By analyzing the question of the eight-queen puzzle,this paper discusses the different solutions between procedure-oriented and object-oriented,compares their relation and difference.The paper also proposes program⁃ming design teaching,which needs natural transition from procedure-oriented to object-oriented,and it is not desir⁃able to emphasize one side and ignore another one.

eight queens;procedure-oriented;object-oriented;object;solution

TP312

A

1008-2794（2012）04-0120-05

2012-02-23

宋东兴（1973—），男，江苏高邮人，讲师，研究方向：计算机网络技术，图像处理，软件工程.