5

我正在尝试编写一个填字游戏求解器我有这个代码，但我无法理解它的某些部分：

size(5).
black(1,3).
black(2,3).
black(3,2).
black(4,3).
black(5,1).
black(5,5).

words([do,ore,ma,lis,ur,as,po, so,pirus, oker,al,adam, ik]) .

:- use_module(library(lists),[nth1/3, select/3]).

crossword(Puzzle) :-
    words(WordList),
    word2chars(WordList,CharsList),
    make_empty_words(EmptyWords) ,
    fill_in(CharsList,EmptyWords),
    word2chars(Puzzle,EmptyWords).

word2chars([],[]).
word2chars([Word|RestWords] ,[Chars|RestChars] ) :-
    atom_chars(Word,Chars),
    word2chars(RestWords,RestChars).

fill_in([],[]).
    fill_in([Word|RestWords],Puzzle) :-
    select(Word,Puzzle,RestPuzzle),
    fill_in(RestWords,RestPuzzle).

make_empty_words(EmptyWords) :-
    size(Size),
    make_puzzle(Size,Puzzle),
    findall(black(I,J),black(I,J),Blacks) ,
    fillblacks(Blacks,Puzzle),
    empty_words(Puzzle,EmptyWords).

    make_puzzle(Size,Puzzle) :-
    length(Puzzle,Size),
    make_lines(Puzzle,Size).

make_lines([],_).
make_lines([L|Ls],Size) :-
    length(L,Size),
    make_lines(Ls,Size).
    fillblacks([],_).

fillblacks([black(I,J)|Blacks],Puzzle) :-
    nth1(I,Puzzle,LineI),
    nth1(J,LineI,black),
    fillblacks(Blacks,Puzzle).

empty_words(Puzzle,EmptyWords) :-
    empty_words(Puzzle,EmptyWords,TailEmptyWords),
    size(Size),
    transpose(Size,Puzzle,[],TransposedPuzzle),
    empty_words(TransposedPuzzle,TailEmptyWords,[] ).

empty_words([],Es,Es).
empty_words([L|Ls],Es,EsTail) :-
    empty_words_on_one_line(L,Es,Es1) ,
    empty_words(Ls,Es1,EsTail).

empty_words_on_one_line([], Tail, Tail).

empty_words_on_one_line([V1,V2|L],[[V1,V2|Vars]|R],Tail) :-
    var(V1), var(V2), !,
    more_empty(L,RestL,Vars),
    empty_words_on_one_line(RestL,R,Tail) .

empty_words_on_one_line([_| RestL],R, Tail) :-
    empty_words_on_one_line(RestL,R,Tail) .

more_empty([],[],[]).
more_empty([V|R],RestL,Vars) :-
    ( var(V) ->
    Vars = [V|RestVars],
    more_empty(R,RestL,RestVars)
    ;
    RestL = R,
    Vars = []
    ).

transpose(N,Puzzle,Acc,TransposedPuzzle) :-
    ( N == 0 ->
    TransposedPuzzle = Acc
    ;
    nth_elements(N,Puzzle,OneVert),
    M is N - 1,
    transpose(M,Puzzle,[OneVert|Acc], TransposedPuzzle)
    ).

nth_elements(_,[],[]).
nth_elements(N,[X|R],[NthX| S]) :-
    nth1(N,X,NthX),
    nth_elements(N,R,S).

此代码用于解决这样的填字游戏：

在此处输入图像描述

在此处输入图像描述

符号是做什么; -> 用的？

我的主要问题是理解规则、转置和more_empty。任何有助于我理解代码的解释将不胜感激。

4

3 回答 3

2

->并且;是 Prolog 的控制流，就像其他语言中的if - then - else语句一样。所以：

transpose(N,Puzzle,Acc,TransposedPuzzle) :-
    ( N == 0 ->
    TransposedPuzzle = Acc
    ;
    nth_elements(N,Puzzle,OneVert),
    M is N - 1,
    transpose(M,Puzzle,[OneVert|Acc], TransposedPuzzle)
    ).

转换为伪代码：

def transpose(N, Puzzle, Acc)
    if N == 0
        return Acc
    else
        OneVert = nth_elements(N, Puzzle)
        transpose(N-1, Puzzle, [OneVert, Acc])

或者：

def transpose(N, Puzzle, Acc)
    while N > 0
        OneVert = nth_elements(N, Puzzle)
        Acc = [OneVert, Acc]
        N = N - 1
    return Acc

这应该让您对它的作用有所了解。我建议你自己把这个more_empty函数翻译成伪代码（或者只是在你的脑海中一步一步），然后试着从那里解决它。

于 2015-01-07T17:41:12.507 回答
1

这些是 Prolog 的 if-then-else 控制结构。

语法如下：

条件 -> then 语句/减速；else 声明/声明

于 2015-01-07T09:42:48.853 回答
1

除了 Josh 和 Avi Tshuva 的正确答案说a -> b ; c“如果 a 然后 b else c”，我想解释一下，->并且;是可以单独使用的单个运算符。

;是逻辑析取，即。逻辑“或”。所以x; y意思是“x 或 y”。这使得条件语句有点混乱，因为a -> b ; c读起来像“a 暗示 b 或 c”，这显然不是它的意思！即使你用括号括起来像“(a 暗示 b) 或 c”，你也会得到与条件语句不同的含义，因为在这种不正确的解释中，c 总是会被尝试，即使 (a 暗示 b) 成功。

不同之处在于->具有一些“非逻辑”语义。来自SWI-Prolog 文档：

:条件 -> :动作

If-then 和 If-Then-Else。该->/2构造承诺在其左侧做出的选择，破坏在子句 (by ;/2) 内或由该子句调用的目标创建的选择点。与 不同!/0的是，整个谓词的选择点（由于多个子句）不会被破坏。组合;/2和->/2如同定义为：
If -> Then; _Else :- If, !, Then. If -> _Then; Else :- !, Else. If -> Then :- If, !, Then.
请注意，(If -> Then)作为(If -> Then ; fail)，如果条件失败，则使构造失败。这种不寻常的语义是 ISO 和所有事实上的 Prolog 标准的一部分。

（请注意，在上面的引用中If，Then等是变量！）

所以要小心任何带有隐式切割的东西！

于 2015-01-08T00:50:30.410 回答