马踏棋盘——一个数据结构综合实验案例新解

总第１４卷１５７期　２０１２年９月　大众科技　Ｐｏｐｕｌａｒ　Ｓｃｉｅｎｃｅ＆Ｔｅｃｈｎｏｌｏｇｙ　ＶｏＬ．１４　Ｎ０．９　Ｓｅｐｔｅｍｂｅｒ　２０１　２　

马踏棋盘　一个数据结构综合实验案例新解　

宁黎华　陈光喜　

（１．桂林电子科技大学数学与计算科学学院，广西桂林５４１００４；　

２．桂林电子科技大学现代教育技术中心，广西桂林５４１００４）　

【摘要】首先把马踏棋盘问题作为一个综合设计案例引入到数据结构实验中，提出了用图论模型求解该问题的一个新思　

路。通过对该问题进行分析，循序渐进地给出了如何利用已学知识来求解该问题的过程。最后对该案例的设计进行了总结和思　考。　

【关键词】马踏棋盘；综合设计；图论　

【中图分类号】ＴＰ３１１　【文献标识码】Ａ　【文章编号】１００８一ｌ１５１（２０１２）０９—００１０—０４　

Ａ　ｎｅｗ　ｍｅｔｈｏｄ　ｆｏｒ　Ｈｏｒｓｅ　ｔｒａｖｅｌｌｉｎｇ　ｏｎ　ｃｈｅｓｓｂｏａｒｄｍａｎ　ｉｎｔｅｇｒａｔｅｄ—ｄｅｓｉｇｎ　ｃａｓｅ　

ｉｎ　ｄａｔａ　ｓｔｒｕｃｔｕｒｅ　ｅｘｐｅｒｉｍｅｎｔ　ｔｅａｃｈｉｎｇ　

Ａｂｓｔｒａｃｔ：Ｉｎ　ｔｈｉｓ　ｐａｐｅｒ，ｔｈｅ　ｐｒｏｂｌｅｍ　ｏｆ　ｈｏｒｓｅ　ｔｒａｖｅｌｉｎｇ　ｏｎ　ｃｈｅｓｓｂｏａｒｄ　ｗａｓ　ｉｎｔｒｏｄｕｃｅｄ　ｉｎｔｏ　ｄａｔａ　ｓｔｒｕｃｔｕｒｅ　ｅｘｐｅｒｉｍｅｎｔ　ｔｅａｃｈｉｎｇ　ａｓ　ａｎ　ｉｎｔｅｇｒａｔｅｄ—ｄｅｓｉｇｎ　ｃａｓｅ　ｆｉｒｓｔｌｙ　ａｎｄ　ａ　ｎｅｗ　ｉｄｅａ　ｏｆ　ｕｓｉｎｇ　ｇｒａｐｈ　ｔｈｅｏｒｙ　ｍｏｄｅｌ　ｆｏｒ　ｓｏｌｖｉｎｇ　ｔｈｅ　ｐｒｏｂｌｅｍ　ｗａｓ　ｐｒｏｐｏｓｅｄ．Ｔｈｅｎ　ｔｈｒｏｕｇｈ　ｔｈｅ　

ａｎａｌｙｓｉｓ　ｏｆ　ｔｈｅ　ｐｒｏｂｌｅｍ，ｔｈｅ　ｐｒｏｃｅｓｓ　ｈｏｗ　ｔｏ　ｕｓｅ　ａｌｒｅａｄｙ　ｌｅａｒｎｅｄ　ｋｎｏｗｌｅｄｇｅ　ｔｏ　ｓｏｌｖｅ　ｔｈｅ　ｐｒｏｂｌｅｍ　ｗａｓ　ｓｈｏｗｎ　ｓｔｅｐ　ｂｙ　ｓｔｅｐ．Ｆｉｎａｌｌｙ　ａ　

ｓｕｍｍａｒｙ　ｏｆ　ａｎｄ　ａ　ｆｕｒｔｈｅｒ　ｔｈｉｎｋｉｎｇ　ａｂｏｕｔ　ｔｈｅ　ｃａｓｅ　ｄｅｓｉｇｎ　ｗｅｒｅ　ｇｉｖｅｎ．　

Ｋｅｙ　ｗｏｒｄｓ：ｈｏｒｓｅ　ｔｒａｖｅｌｉｎｇ　ｃｈｅｓｓｂｏａｒｄ；ｉｎｔｅｇｒａｔｅｄ—ｄｅｓｉｇｎ；ｇｒａｐｈ　ｔｈｅｏｒｙ　

数据结构在计算机学科中有着重要的地位，起着承上启　

下的作用。通过对数据结构的学习可以锻炼学生的逻辑思维　

能力，提出问题、分析问题和解决问题的能力，为学好后继　

课程打下坚实的基础　。然而，数据结构也是一门理论性很强　的课程，理论知识抽象、概念多、算法多而杂，学生不好理　

解，设计程序无从下手。很多学生反映这门课“难懂、不好　

用”。学生不通过实践很难对其理论有深入理解和应用。因　此高质量地开设数据结构实验课十分必要，通过实验课，学　

生可以把课本上看不懂的算法一步步运行出来增强理解或者　

对算法的运行结果进行验证，也可以把抽象地理论应用到解　决实际问题上。　

数据结构实验课的重要性目益突出，目前笔者所在的学　

校已经将数据结构实验课作为一门单独的课程进行开设。而　

综合实验通常是实验课设置的一个压轴环节，根据综合实验　的定义，综合性实验要求学生能够综合利用所学到的知识点，　

解决一个给定的实际问题。其目的是培养学生解决问题的系　统思维能力和综合动手能力。设计适合学生、难易得当、繁　

简相宜的案例，应包含学生已经学到的知识，以此为驱动进　

行课程的教学和学习，提高学生的学习兴趣　。案例过大，学　生工作量大，在给定的时间完不成实验；案例太难，学生不　知从何下手，产生畏难心理，会打击学生解决问题的自信心；　

而案例过于简单，则达不到综合实验要求，起不到锻炼学生　的目的。一个合适的综合实验案例，应该具有以下几个特点：　

１）创新性。求解过程中包含了一种新型的求解思路；２）综　合性。内容具有代表性，涵盖多章的重要知识点　，能够把　

学生已学的各个知识点综合起来；３）可达性。难度不大，学　生容易下手，容易通过对已学理论举一反三，进行求解。　

传统的马踏棋盘问题采用的回溯法或者贪心法求解　，　学生学完了数据结构课程，用此类方法求解仍具有一定难度。　

就其原因，学生对数据结构的理论知识不能灵活运用以及相　

关算法不熟悉，感觉这些求解算法与自己所学相差甚远。学　生关心的问题是：“学习数据结构有什么用？能否用学到的　

最简单、最本质的知识点来求解给定问题？”。针对这个问　题，笔者把马踏棋盘问题作为一个综合设计案例引入到数据　

结构实验中，提出了用图论模型求解该问题的一个新思路。　

通过对该问题进行分析，循序渐进地引导学生如何利用已学　

知识来求解该问题。最后对该案例的设计进行了总结和思考。　

【收稿日期】２０１２—０７—１３　【基金项目】广西高等教育教改工程项目（２０１２ＪＧＡ１４４）　【作者简介】宁黎华，女，桂林电子科技大学数学与计算科学学院讲师，研究方向为进化计算、智能算法、ＯＢＤＤ等；陈光　

喜，男，桂林电子科技大学现代教育技术中心教授，研究方向为智能软件与算法、信息安全、符号计算。　

．

１０．　１马踏棋盘问题描述及求解　

国际象棋的棋盘为８＊８的方格棋盘。将　马　放在任意指定　

的方格中，按照　马　走棋的规则将　马　进行移动。要求每个　方格只能进入一次，最终使得　马　走遍棋盘的６４个方格。求　

出马从给定位置出发的一条或多条路径。　

图论是数据结构课程的一个重点内容，建立图的邻接表　

表示及对图进行深度优先这两个算法学生已经很熟悉，如果　能用这两个熟悉的算法稍加修改来得到新算法，那马踏棋盘　

问题就能迎刃而解了。　

图ｌ　国际象棋棋盘示意图　

１．１建立图论模型　首先我们先来给这个问题进行建模。图１所示的是一个　８＊８的国际象棋棋盘。忽略掉棋盘上的格子的颜色，该棋盘共　

由６４个相同的格子组成。马在棋盘上行走的规则是：先在水　

平或者垂直方向上移动一格，然后再斜走一格，合起来为一　步棋。假设马当前位置，如图所示，下一步马的位置最多有８　

个位置可选。马从当前格子跳到下一个格子，我们就认为当　

前格子到下一个格子是可达的、有路径的，如果把每个格子　看作图中的一个顶点的话，那么当前格子和周围的八个格子　

就存在着有向边关系。确定了有向图的顶点和边，有向图模　型就建好了。　

为了处理方便，我们把图１所示的棋盘放在一个直接坐标　

系中，取每个格子（顶点）左下角的坐标作为整个格子的坐　标。如图２所示。设马当前位置坐标为（ｉ，ｊ），则下一步马的　

可能位置与当前位置在ｘ、Ｙ轴方向上的偏移量是一个固定值，　

按逆时针方向分别为（２，１）、（１，２）、（一１，２）、（一２，　１）、（一２，一１）、（一１，一２）、（１，一２）、（２，一１）。有　

时候如果马的位置靠近棋盘边界，那么下一步的可能的位置　就有可能越界，为了保证下一步的位置是可行的，必须限定　

其ｘ、Ｙ坐标同时在［０，７］内。否则该位置越界了，不可取。　

举个例子，假设马当前的位置为（１，１），则下一步的８个位　

置的坐标分别计算得出（３，２）、（１，３）、（０，３）、（一ｌ，　２）、　（一１，０）、　（０，一１）、　（２，一１）、　（３，０）。其中　

（一１，２）、（一１，０）、（０，一１）、（２，一１）越界了，要　舍去。所以马的下一步可能位置数为４个。通过这个方法，我　

们可以求出图中每个顶点的邻接点。　５６．．　６３一　（７。７ｊ　｝｝２’　●　●　《＿＋　２　ｋ　●　●　ｌｉ￣２　｜＋１　ｌｉ，　１１　＠　｛　・ｌ｝　●　｝　●　＋：　ｌ　

ｌ６．　一　Ｉ｝２　●　●　ｌ－＋　矗２　＆　１５＋　（７。１Ｊ一　ｍ　２　３一　７　啭子　一　

图２直角坐标系下的棋盘位置示意图　

（１）有向图的邻接表形式说明　

有向图的表示有两种方式：邻接矩阵表示法和邻接表表　

示法。已知图中顶点和各个顶点的邻接点，采用邻接表表示　

很容易。因为计算邻接点的时候要用到顶点的坐标，所以我　们在定义表头结点的时候，不但定义了顶点的序号（ｖｅｒｔｅｘ）　

和边表头指针（１ｉｎｋ），还增加了一个表示顶点坐标的属性　

（Ｘ，Ｙ）。顶点序号和坐标的取值方式可见图２，不难发现，　顶点序号ｋ与其坐标（ｉ，ｊ）存在以下对应关系：ｋ－８ｊ＋ｉ。　

表头结点的结构体定义如下：　Ｔｙｐｅｄｅｆ　ｓｔｒｕｃｔ　｛ｉｎｔ　ｖｅｒｔｅｘ：　羔　：ｉ　羔　；　ｅｄｇｅｎｏｄｅ　１　ｉｎｋ：　）　边结点的定义如下：　

Ｔｙｐｅｄｅｆ　ｓｔｒｕｃｔ　ｎｏｄｅ　

｛ｉｎｔ　ａｄｊｖｅｘ：　ｓｔｒｕｅｔ　ｎｏｄｅ＊ｎｅｘｔ　

｝ｅｄｇｅｎｏｄｅ：　其中ｎｅｘｔ为链域指针，在邻接表中指向下一个边结点。　接下来要建立图的邻接表表示算法了。　

（２）邻接表建立算法　

算法２．１给出了从给定的图建立其邻接表的算法的步骤　及ｃ语言描述　：　

算法２．１　

１）读入顶点信息，初始化表头结点顶点域；表头结点初　始化为空；　

Ｆｏｒ（ｉ＝Ｏ：ｉ＜ｎ：ｉ＋＋）　｛ｇａ［ｉ］．ｖｅｒｔｅｘ＝ｇｅｔｃｈａｒ　０：　

ｇａ［ｉ］．１ｉｎｋ＝ＮＵＬＬ；）　

２）读入图中ｅ条边，每读入一条边＜ｉ，ｊ＞，将序号为ｊ的结　

点作为邻接点链在表头结点ｉ的边表中，并且是以头插法的方　

式链入。　Ｆｏｒ（ｋ＝０：ｋ＜ｅ：ｋ＋＋）　

｛ｓｃａｎｆ（“％ｄ％ｄ”，＆ｉ，＆ｊ）：　ｓ＝ｍａｌｌｏｃ（ｓｉｚｅｏｆ（ｅｄｇｅｎｏｄｅ））：　

ｓ一＞ａｄｊｖｅｘ＝ｊ：　ｓ一＞ｎｅｘｔ＝ｇａ［ｉ］．１ｉｎｋ：

　对上述算法２．１略加以下两处改动，我们可建立棋盘的图　

的邻接表表示算法２．２。　

改动ｉ：图中的项点序号及坐标不是从给定图读入的，而　是我们事先按照某个次序（如图２所示的次序）确定好的。为　

方便起见，我们取顶点序号为表头结点在邻接表中的下标。　

改动２：算法２．１中是通过读入给定图中的边来确定顶点　和顶点之间的邻接关系。而算法２．２中，给定任何一个顶点，　

我们是通过周围８个邻接点的相对位移算出它的邻接点。　算法２．２　

ｉ）读入顶点信息，初始化表头结点坐标域、顶点域：表　

头结点初始化为空。　ｆｏｒ（ｉ＝Ｏ：ｉ＜ｎ：ｉ＋＋）　

ｆｏｒ（ｊ＝ｏ：ｊ＜ｎ：ｊ＋＋）　

｛ｇ［ｎ＊ｉ＋ｊ］．ｘ＝ｊ：　ｇ［ｎ＊ｉ＋ｊ］．ｙ＝ｉ：　

ｇ［ｎ＊ｉ＋ｊ］．ｖｅｘ＝ｎ＊ｉ＋ｊ：　

ｇ［ｎ＊ｉ＋ｊ］．１ｉｎｋ＝ＮＵＬＬ：ｊ　２）从表头结点第一个节点开始，据其坐标算出其邻接点　的坐标，继而推导出邻接点序号，若邻接点满足条件，则将　

该结点作为邻接点链在相应表头结点边表中，并且是以头插　法的方式链入。　ｆｏｒ（ｋ＝Ｏ：ｋ＜ｎ＊ｎ：ｋ＋＋）　｛ｆｏｒ（ｉ＝Ｏ：ｉ＜８：ｉ十十）　ｉｆ（＜ｇ［ｋ］．ｘ＋ｐｘ［ｉ］，ｇ［ｋ］．ｙ＋ｐｙ［ｉ］＞满足要求没有越界）　（动态生成结点Ｓ　ｓ一＞ｖｅｘ＝ｎ＊（ｇ［ｋ］．ｙ＋ｐｙ［ｉ］）　ｇ［ｋ］．ｘ＋ｐｘ［ｉ］：　ｓ一＞ｎｅｘｔ＝ｇ［ｋ］．１ｉｎｋ：　ｇ［ｋ］．１ｉｎｋ＝ｓ：｝｝　至此，邻接表已经建立，接下来我们讨论图的遍历问题。　１．２图的遍历　图的模型建好以后，马踏棋盘问题就转化成求马遍历图　

中各个顶点一次且仅一次的一条或多条路径的问题。８　Ｘ　８的　

棋盘构成了一个具有６４个顶点的连通图，对这个连通图进行