下一个谓词混乱

Question

我正在学习prolog,我正在为一个非常简单的游戏编写下一个谓词.

你有一个列表[1,0,1,0,0,1]一个合法的移动是1移动到一个零位置,1只能向右移动到包含0的第一个位置,但它允许跳过其他必要时的价值观

首先我写了一个谓词来将值0更改为1:

flip_first_zero([0|Tail], [1|Tail]). 

很简单,现在我想找到合法的举动,我会尝试解释我的思考过程:

next([],[],[]).
next([Head|Tail], Rest, Out):-
    flip_first_zero([Head|Tail],List1),
    append(Rest,List1,Out).

next([Head|Tail], [Head|Rest], List):-
    next(Tail,Rest, List).

[1,0,0,1,1,1,0]输出应该是一个例子[0,1,0,1,1,1,0] ; [1,0,0,0,1,1,1]; [1,0,0,1,0,1,1] ; [1,0,0,1,1,0,1].

[ 1,0,0,1,1,1,0] - > [0,1,0,1,1,1,0]

[1,0,0,1,1,1,0] - > [1,0,0,0,1,1,1 ]

[1,0,0,1,1,1,0] - > [1,0,0,1,0,1,1 ]

[1,0,0,1,1,1,0] - > [1,0,0,1,1,0,1 ]

所以我是如何理解这一点的,我每次都通过在Rest中保存它来循环移除头部,所以我可以在之后重新附加它.

我接近这个错吗？

Answer 1

问题有两部分：(1) 1 的位置，(2) 找到 1 后第一个 0 的位置，以便将 1 放置到新位置。Prolog 解决方案将反映这一点。您最初的尝试尝试在单个谓词中处理所有内容，我认为这使任务变得更加困难。

基本情况很简单。它代表最小的有效移动。

move([1,0], [0,1]).

然后是递归情况。这些强制执行列表中的至少 3 个位置，因为 2 个位置的琐碎情况已经由基本情况处理，并且它在规则中建立互斥以避免冗余解决方案。

% If we're at a 0 (space), keep going
move([0,X1,X2|T], [0|R]) :-
    move([X1,X2|T], R).

% If we see a 1, we can move it, or we can leave it alone and move on
move([1,X1,X2|T], [0|R]) :-
    place([X1,X2|T], R).
move([1,X1,X2|T], [1|R]) :-
    move([X1,X2|T], R).

% Place the 1 at the first located 0 (space)
place([0|T], [1|T]).
place([1|T], [1|R]) :-
    place(T, R).

因此，要从起始位置确定有效的下一个位置：

| ?-  move([1,0,0,1,1,1,0],R).

R = [0,1,0,1,1,1,0] ? a

R = [1,0,0,0,1,1,1]

R = [1,0,0,1,0,1,1]

R = [1,0,0,1,1,0,1]

(1 ms) no
| ?-

您还可以确定哪些起始位置将导致特定的下一个位置：

| ?- move(S, [1,0,0,1,0,1,1]).

S = [1,0,0,1,1,0,1] ? a

S = [1,0,0,1,1,1,0]

S = [1,0,1,0,0,1,1]

no

这也可以使用 DCG 来完成：

move([0, 1]) --> [1, 0].
move([0|R]) --> see(0), move(R).
move([0|R]) --> see(1), place(R).
move([1|R]) --> see(1), move(R).

see(N), [X1, X2] --> [N, X1, X2].

place([1|T]) --> [0], seq(T).
place([1|R]) --> [1], place(R).

seq([]) --> [].
seq([X|Xs]) --> [X], seq(Xs).

| ?- phrase(move(R), [1,0,0,1,1,1,0]).

R = [0,1,0,1,1,1,0] ? a

R = [1,0,0,0,1,1,1]

R = [1,0,0,1,0,1,1]

R = [1,0,0,1,1,0,1]

no
| ?- phrase(move([1,0,0,1,0,1,1]), S).

S = [1,0,0,1,1,0,1] ? a

S = [1,0,0,1,1,1,0]

S = [1,0,1,0,0,1,1]

no