Prolog学习：数独

作者: 小白frankie | 来源:发表于2017-07-30 17:10 被阅读0次

Prolog学习：数独
头脑风暴-逻辑编程语言Prolog(01)
数独数独
初识Prolog
开启学习数独模式
Prolog学习：用八卦的精神走进Prolog
笔记 | GENENTECH: The Beginnings o
Prolog初探
数独数独我爱你
数独

数独

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

数独

当然数独的阶有很多，9*9是最常见的，我们就以它为例。在用prolog解决之前，我们先想想如何使用C++或者java怎么实现？无非是数据结构+算法，我们先得用一个数据结构表示数独，然后要在这个数据结构上“施加”算法进行求解。

采用prolog的第一步也是相同的，我们得找一个数据结构来表示数独，在prolog中只能选择列表或元祖，这里列表是更好的选择，因为列表可以进行[Head | Tail]解析。

[ _, 6, _, 5, 9, 3, _, _, _,
  9, _, 1, _, _, _, 5, _, _,
  _, 3, _, 4, _, _, _, 9, _,
  1, _, 8, _, 2, _, _, _, 4,
  4, _, _, 3, _, 9, _, _, 1,
  2, _, _, _, 1, _, 6, _, 9,
  _, 8, _, _, _, 6, _, 2, _,
  _, _, 4, _, _, _, 8, _, 7,
  _, _, _, 7, 8, 5, _, 1, _ ]

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

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

给定玩家一个9×9的盘面，玩家填充完所有的空格后最终的解仍然是这个9×9的盘面；
填充完空格后，每一个空格内的数字均在1~9之内；
填充完空格后，每一行9个数字各不相同；
填充完空格后，每一列9个数字各不相同；
填充完空格后，每一个宫格内的数字各不相同。
OK，这就是整个游戏的规则。你可能觉得第一条规则没什么用，实际上第一条规则定义了“解”的形式，就像在C#中我们确定了方法的签名一样：

sudoku(Puzzle,Solution):- Solution = Puzzle.

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

| ?- sudoku([1,2,3,4,5,6,7,8,9,
             1,2,3,4,5,6,7,8,9, 
             1,2,3,4,5,6,7,8,9, 
             1,2,3,4,5,6,7,8,9,
             1,2,3,4,5,6,7,8,9,
             1,2,3,4,5,6,7,8,9,
             1,2,3,4,5,6,7,8,9,
             1,2,3,4,5,6,7,8,9,
             1,2,3,4,5,6,7,8,9],Solution). 

Solution = [1,2,3,4,5,6,7,8,9,1,2,3,4,5,6,7,8,9,1,2,3,4,5,6,7,8,9,1,2,3,4,5,6,7,8,9,1,2,3,4,5,6,7,8,9......

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

| ?- sudoku([1,2,3],Solution).

Solution = [1,2,3]

yes

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

sudoku(Puzzle,Solution):-
    Solution = Puzzle,
    Puzzle = [S11,S12,S13,S14,S15,S16,S17,S18,S19,
              S21,S22,S23,S24,S25,S26,S27,S28,S29,
              S31,S32,S33,S34,S35,S36,S37,S38,S39,
              S41,S42,S43,S44,S45,S46,S47,S48,S49,
              S51,S52,S53,S54,S55,S56,S57,S58,S59,
              S61,S62,S63,S64,S65,S66,S67,S68,S69,
              S71,S72,S73,S74,S75,S76,S77,S78,S79,
              S81,S82,S83,S84,S85,S86,S87,S88,S89,
              S91,S92,S93,S94,S95,S96,S97,S98,S99].

| ?- sudoku([1,2,3],Solution).

no

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

sudoku(Puzzle,Solution):-
    Solution = Puzzle,
    Puzzle = [S11,S12,S13,S14,S15,S16,S17,S18,S19,
              S21,S22,S23,S24,S25,S26,S27,S28,S29,
              S31,S32,S33,S34,S35,S36,S37,S38,S39,
              S41,S42,S43,S44,S45,S46,S47,S48,S49,
              S51,S52,S53,S54,S55,S56,S57,S58,S59,
              S61,S62,S63,S64,S65,S66,S67,S68,S69,
              S71,S72,S73,S74,S75,S76,S77,S78,S79,
              S81,S82,S83,S84,S85,S86,S87,S88,S89,
              S91,S92,S93,S94,S95,S96,S97,S98,S99],
    fd_domain(Puzzle,1,9).

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

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

Row1 = [S11,S12,S13,S14,S15,S16,S17,S18,S19],
Row2 = [S21,S22,S23,S24,S25,S26,S27,S28,S29],
Row3 = [S31,S32,S33,S34,S35,S36,S37,S38,S39],
Row4 = [S41,S42,S43,S44,S45,S46,S47,S48,S49],
Row5 = [S51,S52,S53,S54,S55,S56,S57,S58,S59],
Row6 = [S61,S62,S63,S64,S65,S66,S67,S68,S69],
Row7 = [S71,S72,S73,S74,S75,S76,S77,S78,S79],
Row8 = [S81,S82,S83,S84,S85,S86,S87,S88,S89],
Row9 = [S91,S92,S93,S94,S95,S96,S97,S98,S99],
    
Col1 = [S11,S21,S31,S41,S51,S61,S71,S81,S91],
Col2 = [S12,S22,S32,S42,S52,S62,S72,S82,S92],
Col3 = [S13,S23,S33,S43,S53,S63,S73,S83,S93],
Col4 = [S14,S24,S34,S44,S54,S64,S74,S84,S94],
Col5 = [S15,S25,S35,S45,S55,S65,S75,S85,S95],
Col6 = [S16,S26,S36,S46,S56,S66,S76,S86,S96],
Col7 = [S17,S27,S37,S47,S57,S67,S77,S87,S97],
Col8 = [S18,S28,S38,S48,S58,S68,S78,S88,S98],
Col9 = [S19,S29,S39,S49,S59,S69,S79,S89,S99],
    
Square1 = [S11,S12,S13,S21,S22,S23,S31,S32,S33],
Square2 = [S14,S15,S16,S24,S25,S26,S34,S35,S36],
Square3 = [S17,S18,S19,S27,S28,S29,S37,S38,S39],
Square4 = [S41,S42,S43,S51,S52,S53,S61,S62,S63],
Square5 = [S44,S45,S46,S54,S55,S56,S64,S65,S66],
Square6 = [S47,S48,S49,S57,S58,S59,S67,S68,S69],
Square7 = [S71,S72,S73,S81,S82,S83,S91,S92,S93],
Square8 = [S74,S75,S76,S84,S85,S86,S94,S95,S96],
Square9 = [S77,S78,S79,S87,S88,S89,S97,S98,S99],

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

fd_all_different(Row1),
fd_all_different(Row2),
……
fd_all_different(Col1),
fd_all_different(Col2),
……
fd_all_different(Square1),
fd_all_different(Square2),
……

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

valid([]).
valid([Head|Tail]):-
    fd_all_different(Head),
    valid(Tail).

valid([Row1,Row2,Row3,Row4,Row5,Row6,Row7,Row8,Row9,
          Col1,Col2,Col3,Col4,Col5,Col6,Col7,Col8,Col9,
          Square1,Square2,Square3,Square4,Square5,Square6,Square7,Square8,Square9]).

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

valid([]).
valid([Head|Tail]):-
    fd_all_different(Head),
    valid(Tail).
sudoku(Puzzle,Solution):-
    Solution = Puzzle,
    Puzzle = [S11,S12,S13,S14,S15,S16,S17,S18,S19,
          S21,S22,S23,S24,S25,S26,S27,S28,S29,
          S31,S32,S33,S34,S35,S36,S37,S38,S39,
          S41,S42,S43,S44,S45,S46,S47,S48,S49,
          S51,S52,S53,S54,S55,S56,S57,S58,S59,
          S61,S62,S63,S64,S65,S66,S67,S68,S69,
          S71,S72,S73,S74,S75,S76,S77,S78,S79,
          S81,S82,S83,S84,S85,S86,S87,S88,S89,
          S91,S92,S93,S94,S95,S96,S97,S98,S99],
    fd_domain(Puzzle,1,9),
    
    Row1 = [S11,S12,S13,S14,S15,S16,S17,S18,S19],
    Row2 = [S21,S22,S23,S24,S25,S26,S27,S28,S29],
    Row3 = [S31,S32,S33,S34,S35,S36,S37,S38,S39],
    Row4 = [S41,S42,S43,S44,S45,S46,S47,S48,S49],
    Row5 = [S51,S52,S53,S54,S55,S56,S57,S58,S59],
    Row6 = [S61,S62,S63,S64,S65,S66,S67,S68,S69],
    Row7 = [S71,S72,S73,S74,S75,S76,S77,S78,S79],
    Row8 = [S81,S82,S83,S84,S85,S86,S87,S88,S89],
    Row9 = [S91,S92,S93,S94,S95,S96,S97,S98,S99],
    
    Col1 = [S11,S21,S31,S41,S51,S61,S71,S81,S91],
    Col2 = [S12,S22,S32,S42,S52,S62,S72,S82,S92],
    Col3 = [S13,S23,S33,S43,S53,S63,S73,S83,S93],
    Col4 = [S14,S24,S34,S44,S54,S64,S74,S84,S94],
    Col5 = [S15,S25,S35,S45,S55,S65,S75,S85,S95],
    Col6 = [S16,S26,S36,S46,S56,S66,S76,S86,S96],
    Col7 = [S17,S27,S37,S47,S57,S67,S77,S87,S97],
    Col8 = [S18,S28,S38,S48,S58,S68,S78,S88,S98],
    Col9 = [S19,S29,S39,S49,S59,S69,S79,S89,S99],
    
    Square1 = [S11,S12,S13,S21,S22,S23,S31,S32,S33],
    Square2 = [S14,S15,S16,S24,S25,S26,S34,S35,S36],
    Square3 = [S17,S18,S19,S27,S28,S29,S37,S38,S39],
    Square4 = [S41,S42,S43,S51,S52,S53,S61,S62,S63],
    Square5 = [S44,S45,S46,S54,S55,S56,S64,S65,S66],
    Square6 = [S47,S48,S49,S57,S58,S59,S67,S68,S69],
    Square7 = [S71,S72,S73,S81,S82,S83,S91,S92,S93],
    Square8 = [S74,S75,S76,S84,S85,S86,S94,S95,S96],
    Square9 = [S77,S78,S79,S87,S88,S89,S97,S98,S99],
    
    valid(Row1,Row2,Row3,Row4,Row5,Row6,Row7,Row8,Row9,
          Col1,Col2,Col3,Col4,Col5,Col6,Col7,Col8,Col9,
          Square1,Square2,Square3,Square4,Square5,Square6,Square7,Square8,Square9).

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

| ?- sudoku([_, 6, _, 5, 9, 3, _, _, _,
 9, _, 1, _, _, _, 5, _, _,
 _, 3, _, 4, _, _, _, 9, _,
 1, _, 8, _, 2, _, _, _, 4,
 4, _, _, 3, _, 9, _, _, 1,
 2, _, _, _, 1, _, 6, _, 9,
 _, 8, _, _, _, 6, _, 2, _,
 _, _, 4, _, _, _, 8, _, 7,
 _, _, _, 7, 8, 5, _, 1, _],Solution).

Solution = [7,6,2,5,9,3,1,4,8,9,4,1,2,7,8,5,3,6,8,3,5,4,6,1,7,9,2,1,9,8,6,2,7,3,5,4,4,7,6,3,5,9,2,8,1,2,5,3,8,1,4,6,7,9,3,8,7,1,4,6,9,2,5,5,1,4,9,3,2,8,6,7,6,2,9,7,8,5,4,1,3]

美化后的结果是这样的：

[7,6,2,5,9,3,1,4,8,
 9,4,1,2,7,8,5,3,6,
 8,3,5,4,6,1,7,9,2,
 1,9,8,6,2,7,3,5,4,
 4,7,6,3,5,9,2,8,1,
 2,5,3,8,1,4,6,7,9,
 3,8,7,1,4,6,9,2,5,
 5,1,4,9,3,2,8,6,7,
 6,2,9,7,8,5,4,1,3]

Perfect!

Prolog学习：数独
数独数独是一个很经典的游戏，玩家需要根据n*n盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、...
头脑风暴-逻辑编程语言Prolog(01)
Prolog语言介绍 Prolog的英语意思就是Programming in logic（逻辑编程）。与几乎无所不...
数独数独
想找人一起玩数独，你在哪？
初识Prolog
什么是prolog prolog是Programming in LOGic的简写，也就是使用逻辑的语言编写程序。 ...
开启学习数独模式
“数独”，也被称为“一个人的围棋”。游戏者只需要一张纸和一支笔，就可以去挑战游戏了。在挑战的过程中，游戏者是越...
Prolog学习：用八卦的精神走进Prolog
https://www.cnblogs.com/zhanjindong/p/3329647.html 最近枕头书是...
笔记 | GENENTECH: The Beginnings o
GENENTECH: The Beginnings of Biotech by Smith 2011 Prolog...
Prolog初探
人工智能Prolog实验报告题目要求 prolog代码运行结果误服酸性毒物，清醒状态误服酸性毒物，神志不清...
数独数独我爱你
好久没玩数独了，昨天在图书馆借书时突发奇想查了有关数独的书，有好多！借了一本非常数独，回家就迫不及待地翻阅，哇塞，...
数独
一款拥有几十年历史的数字益智游戏，5种宫格，3种难度，适合各种水平，最接地气的数独游戏。游戏特性： -- 每种难...