程序设计训练 - 数独、国际跳棋、人物信息检索系统

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

Week 1: Sudoku Game

简介

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

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

基本功能

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

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

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

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

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

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

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

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

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

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

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

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

(more…)

Read More

较短步数复原魔方的算法

这其实是我们上学期徐 BOSS 程设课的一个大作业,我本来很早就想把它记录下来了,可是实在太懒了加上拖延症严重于是就拖到了这个学期。本来作业是要求复原魔方就好了,但是后来发现没有图形界面的话似乎调试很困难,就顺便写了一个 UI,刚好还学了一下 OpenGL。最开始我是写了能够找到最优解的 Krof 算法,但是估计是我写得比较丑再加上状态空间实在太大了(大约在搜索到第 15 步还是 16 步的时候状态数就到百亿级别了,而我 8 个线程一秒只能搜几千万个状态好像),根本没有办法在可以接受的时间内得到解。于是退而求其次,改为去搜索一个比较优的解,最后基本上一秒以内就可以得到解了。

整个工程的代码我放在了我的 Github 上:https://github.com/miskcoo/rubik-cube

魔方的表示

如何表示一个魔方呢?一个很直接的方法就是用六个面一共 54 个色块来表示它,我在最开始写的时候就是用这种方法来表示一个魔方的,但是这样存在着很多的冗余。事实上,我们可以按照魔方的各个棱块和角块的位置和方向来存储。对于魔方的一个角块来说,我们只需要存储这个块在 8 个角的哪一个地方以及它的方向如何(关于方向接下来会进行规定)。对于棱块来说也是相同的,只需要位置和方向就可以决定了。

角块方向的表示

首先对于一个角块来说它可能会有 3 个不同的方向(如下图,暂不考虑这个魔方是否合法,仅关注角块)

corner-0corner-2

想象一下,从左到右相当于单独把面对我们的这个角块(按照从魔方中心指向该角块顶点的向量)旋转了两次。我们可以按照这样来规定角块的方向:首先将对应角块像上图中一样面对我们,并且以绿色或蓝色作为顶面。现在以绿色或蓝色作为参照色(因为一个角块有且仅有这两种颜色之一)。现在来规定角块的方向:

  • 如果参照色位置在如同第一张图一样的位置,就规定方向为 0
  • 如果参照色位置在如同第二张图一样的位置,就规定方向为 1
  • 否则就规定方向为 2

棱块方向的表示

对于棱块方向的规定就稍微有些复杂了,因为没有办法像角块这样找到对立的两个面使得每个棱都包含这两种颜色之一。那么对于棱块的参照色我们规定:如果一个棱存在蓝色或绿色,则该颜色为参照色,否则白色或者黄色为参照色。规定了参照色之后就可以规定棱块的方向了:

  • 如果棱块位于顶层或者底层(也就是绿色或者蓝色面所在的层),那么当参照色在这两个面中的一个时方向为 0,否则为 1
  • 如果棱块位于中间层,那么当参照色在白色或者黄色面时方向为 0,否则为 1

edge-0edge-1

在第一张图中,两个棱块的方向都是 0。这是因为对于红白色棱块,白色为参照色并且其位于顶层绿色面;对于绿白色棱块,绿色为参照色并且位于中层白色面。

在第二张图中,两个棱块的方向都是 1。原因与之前的刚好相反。

Kociemba 算法

首先我们规定一种魔方的中间状态:仅仅通过 U、D、L2、R2、F2、B2 这几种旋转就可以将魔方复原的状态。也就是不允许 90^\circ 地旋转魔方的前后左右这四个面。这种状态有什么特点呢?

首先很明显可以观察到按照我们刚刚规定的方向,旋转顶面和底面都是不会改变棱块和角块的方向的,并且仅按照 180^\circ 来旋转周围四个面也是不会改变棱块和角块的方向。那也就是说,在这种中间状态下,魔方的棱块和角块的方向应该都是 0,这是因为目标状态的魔方如此。除此之外,魔方中间层的四个棱块必然也在中间层。

可以简单地计算出这种中间状态一共只有 8! \times 8! \times 4! = 3.9 \times 10^{10} 种可能,事实证明,在不超过 18 步以内就可以从这种状态复原魔方。我们用 IDA* 来进行搜索,当我们设计启发函数的时候分别针对角块(一共 8! 种可能)、顶层和底层的棱块(一共 8! 种可能)、中间层的棱块(一共 4! 种可能)计算复原它们所需要的最少步数(这可以直接进行搜索),之后的启发函数就是这三者的最大值。

剩下的问题就是如何将魔方旋转到中间状态,我们同样采用 IDA* 来进行搜索。对于启发函数,分别针对角块的方向(一共 3^8 种可能)、棱块的方向(一共 2^8 种可能)、中间层棱块的位置及方向(一共 A^4_{12}\times 2^4 种可能)计算复原它们所需要的最少步数。经过计算,不超过 12 步就可以将一个魔方旋转到中间状态。这样总共在不超过 30 步的情况下就可以复原一个魔方了!

刚刚的状态表示方式在这个算法里显示出了很大的优势,在进行 Hash 的时候可以直接使用这个状态表示,而不必从其它表示方法(例如存储 54 个面的方法)计算出棱和角的方向。事实证明,在通常情况下,这个算法很快就能够复原一个魔方。

Krof 算法

这个算法就是我前面说的搜索最优解的算法,思路和 Kociemba 算法几乎一样,不过 Krof 算法没有划分阶段,启发函数是分别对于角块的方向和位置(一共 8!\times3^7 种可能)、两组每组 6 个梭块的位置和方向(每组都是 A^6_{12}\times2^6 种可能)计算复原它们所需要的最少步数。由于这个启发函数的计算也是十分耗时的,所以可以先计算一次之后记录下来之后直接读取就可以了,而前面 Kociemba 算法的启发函数可以现场计算。

Read More

上帝的指纹——Mandelbrot集合的绘制

322px-mandel_zoom_00_mandelbrot_set

曼德博集合(Mandelbrot Set)是一个在复平面上的点集。有人认为 Mandelbrot 集合是“人类有史以来做出的最奇异、最瑰丽的几何图形”,曾被称为“上帝的指纹”。

Mandelbrot 集合是一个分形(fractal),将它无限放大都能够有精妙的细节在内,而这瑰丽的图案仅仅由一个简单的公式生成。

Mandelbrot 集合的定义是由法国数学家 Adrien Douady 做出的,而它的命名则是为了纪念被称为“分形学之父”的 Benoit Mandelbrot。

在计算机出现后,对于分形的绘制成为了可能。在这篇文章中,我会介绍如何用 C++ 以及高精度库 MPFR 绘制 Mandelbrot 集合,以及对图像色彩渲染的一些方法。

具体代码可以参考 https://github.com/miskcoo/mandelbrot-render

(more…)

Read More