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!

最后编辑于：2017.12.09 14:10:54

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 206,482评论 6赞 481
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 88,377评论 2赞 382
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 152,762评论 0赞 342
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 55,273评论 1赞 279
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 64,289评论 5赞 373
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 49,046评论 1赞 285
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 38,351评论 3赞 400
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,988评论 0赞 259
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 43,476评论 1赞 300
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,948评论 2赞 324
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 38,064评论 1赞 333
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,712评论 4赞 323
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 39,261评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 30,264评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,486评论 1赞 262
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 45,511评论 2赞 354
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,802评论 2赞 345

Prolog学习：数独

数独

推荐阅读更多精彩内容