这次程序设计训练小学期一共有三个大作业，分别是数独、在线国际跳棋和人物信息检索系统。这里是简单的一些介绍，代码放在 https://github.com/miskcoo/programming-training。

Week 1: Sudoku Game

简介

Sudoku 是一款利用 Qt 实现的数独游戏，提供了多达 10 个难度的关卡选择，同时还有丰富的功能来帮助玩家更加高效地求解数独问题，例如候选数、高亮相同数字、高亮选中的行列、撤销当前操作以及提示等功能。玩家还可以手动输入数独题目利用 Sudoku 帮助求解。

除了传统 9x9 的数独游戏以外，还提供了更高难度的 16x16 的数独游戏。

基本功能

Sudoku提供了多个方便的按钮：

  • 新游戏：玩家可以开始一局新的游戏。
  • 重玩：玩家可以重新开始本局游戏。
  • 暂停：玩家可以暂停该局游戏（即暂停计时）。
  • 提示：如果当前已经确定的数都是正确的，玩家将会得到一个未填空格的正确数字；如果当前已经确定的数和答案矛盾，导致整个数独无解，那么所有与答案矛盾的数字将会被粗体标出。
  • 清除：清除当前选中格子的所有数字。
  • 撤销：撤销前一步的操作，以及取消撤销（最多可支持 50 步撤销）。

同时可以通过菜单来实现多达 10 种难度的游戏选择，可以求解任意用户输入的数独问题。

玩家在空格中填入的数字分为确定数（采用正常大小的字体表示）以及候选数（采用小号字体表示）。确定数只能存在一个，候选数可以存在多个，并且确定数和候选数不能同时存在。

玩家可以通过多种方式进行格子的选择：

  • 鼠标直接点击格子进行选中。
  • 键盘方向键来进行当前选中格子的切换。
  • Tab键快速切换到下一个格子。

玩家可以用鼠标右键点击格子来对其进行标记。

玩家在选中一个格子之后，如果该格子的数字已经确定，那么所有与该数相同的数将会被加粗显示，以方便确认是否满足数独的条件。同时，所有与该格在相同行或列的格子都会被高亮显示。此外，无论该格子数字确定与否，右侧数字列表中该格子的所有数都会被加粗。

玩家可以通过多种方式在空格中填入数字：

  • 键盘直接输入数字将填入对应的确定数，如果 Ctrl 键被按下，那么填入的将会是候选数。
  • 鼠标点击右侧数字列表填入。使用鼠标左键点击将会填入确定数，右键点击则会填入候选数。

玩家也可以通过多种方式在空格中填入数字：

  • 键盘删除键删除格子中的一个数字。
  • 鼠标点击右侧数字列表已经选中的数进行删除。
  • “清除”功能键来清除该格子所有的数字。

游戏生成算法

我们认为一个数独游戏的难度可以根据行列空格数的最大值以及给定数字的数量来确定。行列空格数的最大值越小玩家拥有的信息量就越多，同样给定数字越多玩家也能获得更多的信息。

在我们的难度中，最简单的关卡给出的数字至少有 50 个，并且行列空格数不会超过 4 个。然而，在最困难的关卡中，最少只会给出 20 个数字，并且可能会有某些行或列全部是空格。在最简单和最困难中间这两个影响难度的因素平滑过渡。

为了生成一个满足条件的数独，可以按照以下步骤来实现：

  1. 在空白棋盘随机填入数十个数。
  2. 利用求解算法获得一个合法解，如果不存在合法解，转到 1。
  3. 生成一个随机的格子排列。
  4. 按照这个序列来尝试一个个删除所填入的数字，如果删除后能保证解唯一并且满足之前的条件，那么就删除，否则不删除。
  5. 如果删除了足够的数字，则返回。否则跳到 1。

为了实现快速的数独问题求解，我们利用 Dancing Link 来优化搜索。

参考资料

[1] XUE, Y.H., JIANG, B.B., Li, Y., YAN, G.F. and SUN, H.F., 2009. Sudoku puzzles generating: From easy to evil. Mathematics in practice and theory, 21(000).

[2] Knuth, D.E., 2000. Dancing links. arXiv preprint cs/0011047.

Week 2: Internet Draughts

简介

Draughts 是一款利用 Qt 实现的国际跳棋游戏，支持双人在线对战。国际跳棋是十分古老的智力游戏之一，其规则是在 10x10 的棋盘内，黑白双方各执 20 子，通过斜向移动、跳吃等手段吃掉对方更多的棋子。最终吃掉对方所有棋子或者使对方无法移动的一方获得胜利。

国际跳棋的基本规则是，黑方先行，并且所有棋子均只能斜向移动，因此整个棋盘只有深色位置可以有棋子。它有几条基本的吃子以及前进规则：

  • 能吃子就必须吃：如果有多个棋子以及多条路径都可以吃子，那么必须吃最多的棋子。如果多有条路径可以吃到相同个数的棋子，那么可以任意选择一条。
  • 土耳其打击：如果吃多子，那么被吃棋子在整个吃子过程结束后才被撤出棋盘。
  • 普通棋子前进：对于普通棋子，只能向前方对角线方向前进一格。
  • 普通棋子跳吃：对于普通棋子，只要对角线方向最近的黑格有敌方棋子，并且该棋子后最近的一格有空位，那么就可以跳到后方空位并且吃掉对应敌方棋子。
  • 升王：任何棋子在最后一步停在对方底线则称为王棋。
  • 王棋前进：对于王棋，只要对应方向有空位，可以向任意对角线方向前进后退任意步数。
  • 王棋跳吃：对于王棋，在跳吃的时候可以无时距离，并且停在被吃棋子后任意空格处。

基本功能

我们的游戏实现在当前是自己的回合时，所有可以移动的棋子会被以绿色标出。当选中某个可移动棋子时，其本身以及下一步能够移动到的位置会被以黄色标出。

由于有连跳以及能吃子就多吃的规则，在存在多条可选路径时，如果只标明最终可达位置，可能会造成困惑以及存在无法选择相同可达位置但不同走棋路线的困难。因此，我们允许玩家一步一步进行走棋，以便选择路径。

Week 3: 人物信息检索

简介

这是一个利用 Django 搭建的一个人物信息检索系统，大约从 Wikipedia 爬取了 10000 个人物信息，并且提取了其中 Infobox 的对应信息。

对于爬取的信息，我们重新组织了其显示的格式并且提供了一个搜索页面，允许根据关键词对其进行搜索，并且还可以根据原先信息的特定字段（如Born，Name，Nationality等）进行关键字查询。搜索结果按照匹配的关键字个数从高到底排序后进行显示，同时匹配的关键字将会被高亮标出。另外，如果结果过多将会分页进行显示。

本文遵守 CC BY-NC 4.0 许可协议。