下一个谓词混淆

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

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

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

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

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

所以我如何理解这一点，我通过在Rest中保留这个来每次移除头部来循环，这样我就可以在后面追加它。

我接近这个错误吗？

Answer 1

问题有两个部分：（1）1的位置，（2）找到1后的前0的位置，以便1可以放在其新的位置。 Prolog解决方案将反映这一点。你的初始尝试试图在一个谓词中处理所有事情，我相信这会使任务变得更加困难。

基本情况很简单。它代表了最小的有效举措。

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

然后递归的情况。由于基础案例已经处理了2个职位的微不足道的案例，因此这些职位在列表中至少执行了3个职位，并且规定了规则中的相互排斥以避免多余的解决方案。

% 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 

Answer 2

解决这个问题的一个合乎逻辑的方法是：找到1之前的内容，然后是1之前和0之前的内容，然后是休息。然后，您需要交换1和0，以便您在1之前，0之后，0之前，之后1，之后0.

从小开始。首先，刚刚分拆名单，只要你有一个1，让你有Before和After，你可以使用append/3这样，利用你的榜样名单：

?- append(Before, [1|After], [1,0,0,1,1,1,0]). 
Before = [], 
After = [0, 0, 1, 1, 1, 0] ; 
Before = [1, 0, 0], 
After = [1, 1, 0] ; 
Before = [1, 0, 0, 1], 
After = [1, 0] ; 
Before = [1, 0, 0, 1, 1], 
After = [0] ; 
false. 

你已经拿到4个解决方案，您期望。现在，你需要看看里面After，看看哪里放1 - 好，你需要把它的第0，所以之后我们在0分裂After，但只有一次：

?- append(Before, [1|After], [1,0,0,1,1,1,0]), 
    once(append(Before0, [0|After0], After)). 
Before = Before0, Before0 = [], 
After = [0, 0, 1, 1, 1, 0], 
After0 = [0, 1, 1, 1, 0] ; 
Before = [1, 0, 0], 
After = [1, 1, 0], 
Before0 = [1, 1], 
After0 = [] ; 
Before = [1, 0, 0, 1], 
After = [1, 0], 
Before0 = [1], 
After0 = [] ; 
Before = [1, 0, 0, 1, 1], 
After = [0], 
Before0 = After0, After0 = [] ; 
false. 

现在你有3件：1件之前称为Before，其中1件与第一件0之间调用Before0，最后一件之后称为After0。你只需要把它们放在一起：Before,0，Before0,1,After0。您可以使用2个参数的append/2这需要在第一个参数列表的列表：（我只留下Result绑定，以节省空间）

?- append(Before, [1|After], [1,0,0,1,1,1,0]), 
    once(append(Before0, [0|After0], After)), 
    append([Before, [0|Before0], [1|After0]], Result). 
Result = [0, 1, 0, 1, 1, 1, 0] ; 
Result = [1, 0, 0, 0, 1, 1, 1] ; 
Result = [1, 0, 0, 1, 0, 1, 1] ; 
Result = [1, 0, 0, 1, 1, 0, 1] ; 
false. 

我认为你是在这一点上做。

Answer 3

感谢您对所有问题的答案，这是我做的：

flip_first_zero([0|L],[1|L]):-!. 
flip_first_zero([X|L],[X|L1]):- 
    flip_first_zero(L,L1). 

next([1|L],[0|L1]):- 
    flip_first_zero(L,L1). 
next([X|L],[X|L1]):- 
    next(L,L1).