跟风向，用swi-prolog解世界最难数独，无解

%求解这个问题用到的四个谓词
has(Head,[Head|Tail]).
has(Head,[OtherHead|Tail]):-has(Head,Tail).
delete(H,[H|T],T).
delete(H,[OH|T],[OH|T2]):-delete(H,T,T2).
pailie([],[]).
pailie([A|B],Y):-delete(A,Y,Y1),pailie(B,Y1).
different2([_|[]]).
different2(List):-has(Ele,List)->delete(Ele,List,Tail)
->not((has(Ele,Tail))),different2(Tail).
%swi-prolog赋值各种蛋疼
the_answer:-
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],

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

different2(Column1),
different2(Column2),
different2(Column3),
different2(Column4),
different2(Column5),
different2(Column6),
different2(Column7),
different2(Column8),
different2(Column9),


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


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),nl,fail.

fuyunv 写道:%求解这个问题用到的四个谓词
has(Head,[Head|Tail]).
has(Head,[OtherHead|Tail]):-has(Head,Tail).
delete(H,[H|T],T).
delete(H,[OH|T],[OH|T2]):-delete(H,T,T2).
pailie([],[]).
pailie([A|B],Y):-delete(A,Y,Y1),pailie(B,Y1).
different2([_|[]]).
different2(List):-has(Ele,List)->delete(Ele,List,Tail)
->not((has(Ele,Tail))),different2(Tail).
%swi-prolog赋值各种蛋疼
the_answer:-
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],

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

different2(Column1),
different2(Column2),
different2(Column3),
different2(Column4),
different2(Column5),
different2(Column6),
different2(Column7),
different2(Column8),
different2(Column9),


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


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),nl,fail.

原图好像要开代理才能看得到，
我把它另存出来直接上传到这个论坛提供的图片空间。



感觉挺有意思的，
我在想，先定义一个谓词，比如possible_num(List_A, List_B)，
然后你询问possible_num(Line1, Possible_List)时能传回Possible_List = [1,2,4,6,7,8,9]，
然后再配合member这个内定谓词，给出条件：可能的数字是Possible_List的1个元素，
意即member(N, Possible_List)要是true，然后让prolog自己去try所有的可能，
这样子应该能解出来吧？除非try的次数太多要解很久。

现在忙着准备周六的期货从业资格考试，
考完这个我再来研究研究。

期待，祝Liao Sir考好

fuyunv 写道:期待，祝Liao Sir考好

还好fuyunv已将题目输进来，让我省了不少力气，
不然光打字就够我受的了，哈哈。
我就直接copy你输入的题目了，代码如下：

代码:

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).

运行结果：

4 ?- shudu.
[1,4,5,3,2,7,6,9,8]
[8,3,9,6,5,4,1,2,7]
[6,7,2,9,1,8,5,4,3]
[4,9,6,1,8,5,3,7,2]
[2,1,8,4,7,3,9,5,6]
[7,5,3,2,9,6,4,8,1]
[3,6,7,5,4,2,8,1,9]
[9,8,4,7,6,1,2,3,5]
[5,2,1,8,3,9,7,6,4]
true ;
;
false.


按;传回false，表示只有一组解。

多谢Liao Sir,有好多没见过的谓词和语法，我得慢慢看了

确实能解出，但用trace步进的时候会出错

fuyunv 写道:确实能解出，但用trace步进的时候会出错

是喔？你说的是逐步逐步执行，
按一下空白键程序做一步的那种？

对啊，按空格，按回车都可以

各路大神有谁明白prolog中的module？有没有实际的案例，分享一下？