简单介绍了下Prolog的一些基本概念，今天我们来利用这些基本概念解决两个问题：数独和八皇后问题。

 数独是一个很经典的游戏：

玩家需要根据n×n盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫内的数字均含1-n，不重复。

当然数独的阶有很多，9×9是最常见的，我们就以它做例子。在用Prolog解决之前先想想如果我们用C#或Java来做或怎么做？无非就是数据结构加算法，我们先得用一个数据结构表示数独，然后我们要在这个数据结构上“施加”算法进行求解。采用Prolog的第一步是相同的，我们得找一个数据结构表示数独，毫无疑问在Prolog中我们只能选择列表或元组，这里列表是更好的选择，因为列表可以进行[Head|Tail]解析，后面你就知道为什么了。我们像下面这样表示一个数独：

“_”代表未知的数字，需要玩家填空的地方。

接下来的步骤跟命令式语言就截然不同了，我们不是描述算法，而是要描述数独这个游戏的规则：

1. 给定玩家一个9×9的盘面，玩家填充完所有的空格后最终的解仍然是这个9×9的盘面；
2. 填充完空格后，每一个空格内的数字均在1~9之内；
3. 填充完空格后，每一行9个数字各不相同；
4. 填充完空格后，每一列9个数字各不相同；
5. 填充完空格后，每一个宫格内的数字各不相同。

Ok，这就是整个游戏的规则。你可能觉得第一条规则没什么用，实际上第一条规则定义了“解”的形式，就像在C#中我们确定了方法的签名一样：

事实上这个规则已经可以工作了：

当然这只是第一步，这个规则对于输入的数独形式没有任何限制，事实上可以是任意的列表,Prolog都返回yes：

我们需要规定下数独的形式：

我们接着看第二条规则：“填充完空格后，每一个空格内的数字均在1~9之内” 。上一篇文章中我们介绍了Prolog中有一个内置谓词叫，这时候就可以派上用场了：

好了现在我们只能输入9×9并且每个每个位置上只能是1~9之间的数的列表了。

好了，现在到整个游戏的关键规则，事实上2,3,4这三个规则才决定了数独的难度，1,2只不过是基础，我们来统一考虑这三个问题。这里其实比想象的简单多了。我们首先要做的就是需要定义出来行、列、宫格：

上一篇文章中我还提到一个谓词叫fd_all_different:检查列表中是否有重复元素，接下来我们只要证明每一列，每一行，每一个宫格列表内没有重复元素就可以了：

其实到此这个解数独的程序已经结束了，不过最后这几行代码太土了，我们可以采用用递归“优化”下，像下面这样：

不管你信不信，我们已经搞定了，最终完整的代码如下：

反正我信了，我们来试试吧，就以上面我从百度上找到的那个图为例：

美化后的结果是这样的：

Ok，有了数独问题作为铺垫，下面看八皇后问题应该就应该没那么难了，请保持用Prolog思考问题的方式，解决后你会发现Prolog真是这方面的“专家”，Let's Go!

八皇后问题也是一个非常经典的问题：

八皇后问题是一个以国际象棋为背景的问题：如何能够在 8×8 的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。

老套路我们先描述游戏规则。

1. 每个皇后有一个行号和列号，行号和列号的取值范围在1~8之间；
2. 一个棋盘上有八个皇后；
3. 任意两个皇后不可以共享一行；
4. 任意两个皇后不可以共享一列；
5. 任意两个皇后不可以在同一个对角线上（左下角->右上角）；
6. 任意两个皇后不可以在同一个对角线上（右下角->左上角）。

在了解规则之后我们梳理一下这个问题，对照上面这个图：

我们给棋盘上每一个位置设定一个坐标(x,y)，八个皇后的坐标分别为(x1,y1)，(x2,y2)……我们以回溯的角度看问题，假设如图已经得到了最后解，那么这8个坐标满足：x1，x2……各不相同，y1，y2……个不相同，找出(x1,y1)，(x2,y2)……中属于对角线1上的和对角线2上的位置，它们坐标应该个不相同。

所以整个问题的难点在于给定类似下面这样一个列表，我们需要找出其中的所有的行号，列号，和在对角线上的坐标：

找出行号和列号稍微简单点，这里直接给出答案，大家也可以自己思考下：

把上面的列表代进去简单验证下：

关键是如何验证对角线上的元素，而且两条对角线是不一样的，提醒下因为我们最后会还是会利用fd_all_different这个谓词。

好吧，我们回过头观察下上面那个棋盘的坐标图（注意我标红的地方），有没有发现什么规则呢？

• 左上角到右下角的对角线上的元素：所有坐标的横坐标-纵坐标都相同，等于0；
• 左下角到右上角的对角线上的元素：所有坐标的横坐标+纵坐标都相同，等于9；

OK，我们可以定义下面这样两个谓词diags1和diags2：

如果坐标在对角线上，那么抓取到的列表元素都是相等的。

好了，到目前为止我们已经完成了最难的部分，剩下的都是一些验证性工作。我们最终的“程序入口”应该是这样的：

我们还需要一些验证性工作：

1.给定列表里的皇后是不是合法的，即横纵坐标都在1~8之内，这用到了我上一篇中提到的member谓词：

2.验证给定的列表是不是八个皇后，这里用到一个length谓词，顾名思义：

3.需要递归的验证给定的列表中的每个元素是不是“皇后”：

Ok，下面就是八皇后问题的答案的完整代码：

没错，答案已经出来，但事实上上面这个程序运行的非常慢，我在我i7的笔记本上的GNU Prolog中执行下面这个问题，半天没有响应：

其实我们可以对这个问题进行一个简化。我们可以肯定棋盘上八行每行肯定有一个皇后，又因为互不能在一行，因此我们假设八皇后的坐标分别为：(1,A),(2,B),(3,C),(4,D),(5,E),(6,F),(7,G),(8,H)。那么我们可以对上面的代码进行优化，去掉所有对行的操作，优化后代码如下：

?后跟a可以一次性询问所有答案，可以看到还是相当的慢，这也算是声明式语言的一个劣势吧。

好了，今天介绍的两个问题就到此结束了。问题本身并不是重点，重点是我们思考问题的方式。 

最后提供：，希望大家可以喜欢Prolog这门小巧简单，功能强大的语言。

来源：互联网05-27编辑：MR阅读()