Prolog 人工智能语言中文论坛---打造优质Prolog学习交流园地

一个供Prolog爱好者学习与交流的地方


您没有登录。 请登录注册

急求数独程序解释,看不懂呀,希望逐句解释

浏览上一个主题 浏览下一个主题 向下  留言 [第1页/共1页]

shudu_rule(Scope, I, Total_cell) :-
numlist(1, 9, J), repeat_list(9, I, I2, []), repeat_list(9, Total_cell, T, []),
maplist(choose_number, Scope, T, I2, J).

choose_number(Deter, Total_cell, I, J) :- var(Deter) -> candidate(C, Total_cell, I, J), member(Deter, C) ; true.

candidate(Can, Total_cell, I, J) :-
nth1(1, Total_cell, Line_set), nth1(2, Total_cell, Column_set), nth1(3, Total_cell, BigCell_set),
nth1(I, Line_set, Line), nth1(J, Column_set, Column),
JJ is floor((J - 1) / 3) + 1, II is floor((I - 1) / 3) + 1, K is (II - 1) * 3 + JJ, nth1(K, BigCell_set, BigCell),
copy_term(Line, SmallLine), list_to_set(SmallLine, Out), numlist(1, 9, A), subtract(A, Out, C),
copy_term(Column, SmallColumn), list_to_set(SmallColumn, Out2), subtract(C, Out2, Ca),
copy_term(BigCell, SmallBigCell), list_to_set(SmallBigCell, Out3), subtract(Ca, Out3, Can).

repeat_list(N, Ele, F, A) :- N > 0 -> append(A, [Ele], A1), N1 is N - 1, repeat_list(N1, Ele, F, A1); F = A.


shudu :-

Line1 = [S11,S12,5,3,S15,S16,S17,S18,S19],
Line2 = [8,S22,S23,S24,S25,S26,S27,2,S29],
Line3 = [S31,7,S33,S34,1,S36,5,S38,S39],
Line4 = [4,S42,S43,S44,S45,5,3,S48,S49],
Line5 = [S51,1,S53,S54,7,S56,S57,S58,6],
Line6 = [S61,S62,3,2,S65,S66,S67,8,S69],
Line7 = [S71,6,S73,5,S75,S76,S77,S78,9],
Line8 = [S81,S82,4,S84,S85,S86,S87,3,S89],
Line9 = [S91,S92,S93,S94,S95,9,7,S98,S99],

Column1 = [S11,8,S31,4,S51,S61,S71,S81,S91],
Column2 = [S12,S22,7,S42,1,S62,6,S82,S92],
Column3 = [5,S23,S33,S43,S53,3,S73,4,S93],
Column4 = [3,S24,S34,S44,S54,2,5,S84,S94],
Column5 = [S15,S25,1,S45,7,S65,S75,S85,S95],
Column6 = [S16,S26,S36,5,S56,S66,S76,S86,9],
Column7 = [S17,S27,5,3,S57,S67,S77,S87,7],
Column8 = [S18,2,S38,S48,S58,8,S78,3,S98],
Column9 = [S19,S29,S39,S49,6,S69,9,S89,S99],

BigCell1 = [S11,S12,5,8,S22,S23,S31,7,S33],
BigCell2 = [3,S15,S16,S24,S25,S26,S34,1,S36],
BigCell3 = [S17,S18,S19,S27,2,S29,5,S38,S39],
BigCell4 = [4,S42,S43,S51,1,S53,S61,S62,3],
BigCell5 = [S44,S45,5,S54,7,S56,2,S65,S66],
BigCell6 = [3,S48,S49,S57,S58,6,S67,8,S69],
BigCell7 = [S71,6,S73,S81,S82,4,S91,S92,S93],
BigCell8 = [5,S75,S76,S84,S85,S86,S94,S95,9],
BigCell9 = [S77,S78,9,S87,3,S89,7,S98,S99],

Line_set = [Line1, Line2 ,Line3, Line4, Line5 ,Line6, Line7, Line8 ,Line9],
Column_set = [Column1, Column2 ,Column3, Column4, Column5 ,Column6, Column7, Column8 ,Column9],
BigCell_set = [BigCell1, BigCell2 , BigCell3, BigCell4, BigCell5 , BigCell6, BigCell7, BigCell8 , BigCell9],
Total_cell = [Line_set, Column_set, BigCell_set],

numlist(1, 9, I), repeat_list(9, Total_cell, T, []),
maplist(shudu_rule, Line_set, I, T),

write(Line1), nl, write(Line2), nl, write(Line3), nl,
write(Line4), nl, write(Line5), nl, write(Line6), nl,
write(Line7), nl, write(Line8), nl, write(Line9).

查阅用户资料
看起来挺复杂,其实思路挺简单的。
为了解释,将代码重新按照流程排列了一下:

shudu :-

Line1 = [S11,S12,5,3,S15,S16,S17,S18,S19],
Line2 = [8,S22,S23,S24,S25,S26,S27,2,S29],
Line3 = [S31,7,S33,S34,1,S36,5,S38,S39],
Line4 = [4,S42,S43,S44,S45,5,3,S48,S49],
Line5 = [S51,1,S53,S54,7,S56,S57,S58,6],
Line6 = [S61,S62,3,2,S65,S66,S67,8,S69],
Line7 = [S71,6,S73,5,S75,S76,S77,S78,9],
Line8 = [S81,S82,4,S84,S85,S86,S87,3,S89],
Line9 = [S91,S92,S93,S94,S95,9,7,S98,S99],

Column1 = [S11,8,S31,4,S51,S61,S71,S81,S91],
Column2 = [S12,S22,7,S42,1,S62,6,S82,S92],
Column3 = [5,S23,S33,S43,S53,3,S73,4,S93],
Column4 = [3,S24,S34,S44,S54,2,5,S84,S94],
Column5 = [S15,S25,1,S45,7,S65,S75,S85,S95],
Column6 = [S16,S26,S36,5,S56,S66,S76,S86,9],
Column7 = [S17,S27,5,3,S57,S67,S77,S87,7],
Column8 = [S18,2,S38,S48,S58,8,S78,3,S98],
Column9 = [S19,S29,S39,S49,6,S69,9,S89,S99],

BigCell1 = [S11,S12,5,8,S22,S23,S31,7,S33],
BigCell2 = [3,S15,S16,S24,S25,S26,S34,1,S36],
BigCell3 = [S17,S18,S19,S27,2,S29,5,S38,S39],
BigCell4 = [4,S42,S43,S51,1,S53,S61,S62,3],
BigCell5 = [S44,S45,5,S54,7,S56,2,S65,S66],
BigCell6 = [3,S48,S49,S57,S58,6,S67,8,S69],
BigCell7 = [S71,6,S73,S81,S82,4,S91,S92,S93],
BigCell8 = [5,S75,S76,S84,S85,S86,S94,S95,9],
BigCell9 = [S77,S78,9,S87,3,S89,7,S98,S99],

到此很简单,只是将数独题目输入进来以事实表示。
其中,BigCell指的是3*3组成的大格子,
因为数独的规则是除了同行(代码里的Line)不能重复、同列(代码里的Column)不能重复,
还有同大格子(代码里的BigCell)不能重复,
因此先定义好BigCell对后面的处理是有好处的。


Line_set = [Line1, Line2 ,Line3, Line4, Line5 ,Line6, Line7, Line8 ,Line9],
Column_set = [Column1, Column2 ,Column3, Column4, Column5 ,Column6, Column7, Column8 ,Column9],
BigCell_set = [BigCell1, BigCell2 , BigCell3, BigCell4, BigCell5 , BigCell6, BigCell7, BigCell8 , BigCell9],
Total_cell = [Line_set, Column_set, BigCell_set],

将9条行、列、大格再放进List中,组成行、列、大格集合,
将行、列、大格集合再组成一个List,也就是整个数独题目Total_cell集合。
这么做的目的是为了待会方便参数传递。

numlist(1, 9, I), repeat_list(9, Total_cell, T, []),
maplist(shudu_rule, Line_set, I, T),

numlist可以产生一个1-9的List,repeat_list可以产生9个Total_cell组成的List,
这么做的目的都是为了要使用maplist这个函数,这个函数的好处是可以当成循环来用,
比如查询maplist(func, [1,2,3], [a, b, c]),
prolog会执行func(1, a),如果true,
再执行func(2, b),如果true,再执行func(3, c),
也就是一下子就会做三遍func,很好用。

所以这里的目的其实就是要做很多遍shudu_rule,每次给的参数都由后面的Line_set、I、T给出。

write(Line1), nl, write(Line2), nl, write(Line3), nl,
write(Line4), nl, write(Line5), nl, write(Line6), nl,
write(Line7), nl, write(Line8), nl, write(Line9).

这三行代码很简单,只是输出最终结果而已。

shudu_rule(Scope, I, Total_cell) :-
numlist(1, 9, J), repeat_list(9, I, I2, []), repeat_list(9, Total_cell, T, []),
maplist(choose_number, Scope, T, I2, J).

这里是为了重复执行choose_number做准备,
choose_number的作用是对当前的小格子挑一个可行解(即当前同行、同列、同大格无与之重复的数字)。

choose_number(Deter, Total_cell, I, J) :- var(Deter) -> candidate(C, Total_cell, I, J), member(Deter, C) ; true.

具体的做法是:用candidate找出可行解的集合,然后用member函数从中挑选一个。

candidate(Can, Total_cell, I, J) :-
nth1(1, Total_cell, Line_set), nth1(2, Total_cell, Column_set), nth1(3, Total_cell, BigCell_set),
nth1(I, Line_set, Line), nth1(J, Column_set, Column),
JJ is floor((J - 1) / 3) + 1, II is floor((I - 1) / 3) + 1, K is (II - 1) * 3 + JJ, nth1(K, BigCell_set, BigCell),
copy_term(Line, SmallLine), list_to_set(SmallLine, Out), numlist(1, 9, A), subtract(A, Out, C),
copy_term(Column, SmallColumn), list_to_set(SmallColumn, Out2), subtract(C, Out2, Ca),
copy_term(BigCell, SmallBigCell), list_to_set(SmallBigCell, Out3), subtract(Ca, Out3, Can).

candidate的做法其实很简单,
一开始的一堆nth1函数,只是为了将传进来的Total_cell分解,
分解出各行、各列、各大格,然后根据循环参数I、J,得知当前是想要帮哪个小格子(简称e)选数字,
然后提取e所在位置对应的行、列、大格集合(3个集合),
对此3个集合分别用list_to_set把集合中的数字留下,变量删除,
subtract分别得到3个集合的补集,这个补集就是我们可以为e选择的合法数字。

至此程序已经解释完了,其实就是从第一个小格子开始,往右一直循环到第9个,
再换下一行……,一直到跑完全部9行的所有小格子。
每次在替一个小格子选数字的时候,都是将它所在位置所对应的行、列、大格的3个集合提取出来,
扣除掉已经出现在集合里的数字,剩下的就是可选数字(假设为C),
然后从C里按排列顺序先选一个数字,先当它是正确答案继续往下运行,
如果程序运行下去最后选不出来,也就是出现false的情况,
prolog会透过回溯的方式回到C,按顺序再选下一个数字,
直到所有小格子e都满足规则为止,解答就出来了。


repeat_list(N, Ele, F, A) :- N > 0 -> append(A, [Ele], A1), N1 is N - 1, repeat_list(N1, Ele, F, A1); F = A.

查阅用户资料 http://prolog.longluntan.net

3 O(∩_∩)O谢谢 于 周六 十月 26, 2013 6:31 am

谢谢,分析得很详细,但我还不是很明白,这可能跟我不是很了解prolog语言有关吧,,
我还想问下用prolog解数独的程序,和其他语言(例如C)相比,有什么优点吗?

查阅用户资料
溪中水life 写道::谢谢,分析得很详细,但我还不是很明白,这可能跟我不是很了解prolog语言有关吧,,
我还想问下用prolog解数独的程序,和其他语言(例如C)相比,有什么优点吗?
prolog只要定义好"已知什么"、"规则是什么"、"你想问什么"就好,
C之类的传统语言,你必须写清楚每一步要做什么。

以数独为例,如果用C之类的传统语言写,
光是要写"遍历所有可能",就很麻烦,
81个格子需要81层循环,81层循环的写法怎么写?
(虽然有些格子数字是已知的,不到81层)

也许传统语言有更方便的写法,但至少我是不会写,
这是我目前能想到的一个巨大差异。

多层循环,或是可以用树状结构展开的题目,
很适合用prolog来解决。
但是如果是流程很明确,一步一步按顺序下来没什么循环的,
用prolog会比较费事。
这是我自己的感觉,仅供参考。

查阅用户资料 http://prolog.longluntan.net

浏览上一个主题 浏览下一个主题 返回页首  留言 [第1页/共1页]

您在这个论坛的权限:
不能在这个论坛回复主题