Prolog学习：数独

2017-07-30 本文已影响0人小白frankie

数独

数独是一个很经典的游戏，玩家需要根据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学习：数独

数独

猜你喜欢

热点阅读