Prolog 中的锁定挑战 [英] Lock Challenge in Prolog

问题描述

我刚开始学习序言，我一直在努力解决这个难题:

我尝试添加一些规则，例如这个例子 http://swish.swi-prolog.org/example/houses_puzzle.pl 但我想不出解决方案.

到目前为止我尝试过的:

% 将房屋术语呈现为一个漂亮的表格.:- use_rendering(table,[标题(h('N1'，'N2'，'N3'))]).数字(Hs) :-长度(Hs, 1),成员(h(6,8,2), Hs),成员(h(6,1,4), Hs),成员(h(2,0,6), Hs),成员(h(7,3,8), Hs),成员(h(7,8,0), Hs),right_and_placed(6, 8, 2, Hs).正确和位置(A，B，C，R).

但我什至不知道如何编写可以检查数字是否正确且位置正确的规则.

解决方案

对于现有答案，我想添加一个使用 CLP(FD) constraints 的版本.

我将使用的两个构建块是 num_correct/3 和 num_well_placed/3.

首先，num_correct/3，将两个整数列表与公共元素的数量关联起来:

<预>num_correct(Vs, Ns, Num) :-foldl(num_correct_(Vs), Ns, 0, Num).num_correct_(Vs, Num, N0, N) :-foldl(eq_disjunction(Num), Vs, 0, Disjunction),析取#<==>,N#= N0 + T.eq_disjunction(N, V, D0, D0 #\/(N #= V)).

示例查询:

<预>?- num_correct([1,2,3], [3,5], Num).数量 = 1.

作为纯关系的特征，这也适用于更一般的查询，例如:

<预>?- num_correct([A], [B], Num).B#=A#<==>数字，数字在 0..1.

其次，我使用 num_well_placed/3，它将两个整数列表与对应元素相等的索引数量相关联:

<预>num_well_placed(Vs, Ns, Num) :-地图列表(num_well_placed_, Vs, Ns, Bs),总和(Bs，#=，数字).num_well_placed_(V, N, B) :- (V #= N) #<==>B.

再次，一个示例查询和答案:

<预>?- num_well_placed([8,3,4], [0,3,4], Num).数量 = 2.

以下谓词简单地结合了这两者:

<预>num_correct_placed(Vs, Hs, C, P) :-num_correct(Vs, Hs, C),num_well_placed(Vs, Hs, P).

因此，整个谜题可以表述如下:

<预>锁(Vs):-Vs = [_,_,_],VS 0..9，num_correct_placed(Vs, [6,8,2], 1, 1),num_correct_placed(Vs, [6,1,4], 1, 0),num_correct_placed(Vs, [2,0,6], 2, 0),num_correct_placed(Vs, [7,3,8], 0, 0),num_correct_placed(Vs, [7,8,0], 1, 0).

在这种情况下根本不需要搜索:

<预>?- 锁定(Vs).Vs = [0, 4, 2].

此外，如果我概括最后一个提示，即如果我写:

<预>锁(Vs):-Vs = [_,_,_],VS 0..9，num_correct_placed(Vs, [6,8,2], 1, 1),num_correct_placed(Vs, [6,1,4], 1, 0),num_correct_placed(Vs, [2,0,6], 2, 0),num_correct_placed(Vs, [7,3,8], 0, 0),* num_correct_placed(Vs, [7,8,0], 1, 0).

那么唯一的解决方案可以仍然在没有搜索的情况下确定:

<预>?- 锁定(Vs).Vs = [0, 4, 2].

事实上，我什至可以也去掉倒数第二个提示:

<预>锁(Vs):-Vs = [_,_,_],VS 0..9，num_correct_placed(Vs, [6,8,2], 1, 1),num_correct_placed(Vs, [6,1,4], 1, 0),num_correct_placed(Vs, [2,0,6], 2, 0),* num_correct_placed(Vs, [7,3,8], 0, 0),* num_correct_placed(Vs, [7,8,0], 1, 0).

并且仍然解决方案是独一无二的，尽管我现在必须使用 label/1 来找到它:

<预>?- 锁(Vs)，标签(Vs).VS = [0, 4, 2] ;错误的.

I just started learning prolog and I'm stuck trying to solve this puzzle :

I tried to add some rules like this example http://swish.swi-prolog.org/example/houses_puzzle.pl but I couldn't come up with a solution.

What I tried so far:

% Render the houses term as a nice table.
:- use_rendering(table,
         [header(h('N1', 'N2', 'N3'))]).
numbers(Hs) :-
    length(Hs, 1),
    member(h(6,8,2), Hs),
    member(h(6,1,4), Hs),
    member(h(2,0,6), Hs),
    member(h(7,3,8), Hs),
    member(h(7,8,0), Hs),
    correct_and_placed(6, 8, 2, Hs).

correct_and_place(A, B, C, R).

But I don't even know how to write a rule that can check if a number is correct and on the right place.

解决方案

To the existing answers, I would like to add a version using CLP(FD) constraints.

The two building blocks I shall use are num_correct/3 and num_well_placed/3.

First, num_correct/3, relating two lists of integers to the number of common elements:

num_correct(Vs, Ns, Num) :-
        foldl(num_correct_(Vs), Ns, 0, Num).

num_correct_(Vs, Num, N0, N) :-
        foldl(eq_disjunction(Num), Vs, 0, Disjunction),
        Disjunction #<==> T,
        N #= N0 + T.

eq_disjunction(N, V, D0, D0 #\/ (N #= V)).

Sample query:

?- num_correct([1,2,3], [3,5], Num).
Num = 1.

As is characteristic for pure relations, this also works for much more general queries, for example:

?- num_correct([A], [B], Num).
B#=A#<==>Num,
Num in 0..1.

Second, I use num_well_placed/3, which relates two lists of integers to the number of indices where corresponding elements are equal:

num_well_placed(Vs, Ns, Num) :-
        maplist(num_well_placed_, Vs, Ns, Bs),
        sum(Bs, #=, Num).

num_well_placed_(V, N, B) :- (V #= N) #<==> B.

Again, a sample query and answer:

?- num_well_placed([8,3,4], [0,3,4], Num).
Num = 2.

The following predicate simply combines these two:

num_correct_placed(Vs, Hs, C, P) :-
        num_correct(Vs, Hs, C),
        num_well_placed(Vs, Hs, P).

Thus, the whole puzzle can be formulated as follows:

lock(Vs) :-
        Vs = [_,_,_],
        Vs ins 0..9,
        num_correct_placed(Vs, [6,8,2], 1, 1),
        num_correct_placed(Vs, [6,1,4], 1, 0),
        num_correct_placed(Vs, [2,0,6], 2, 0),
        num_correct_placed(Vs, [7,3,8], 0, 0),
        num_correct_placed(Vs, [7,8,0], 1, 0).

No search at all is required in this case:

?- lock(Vs).
Vs = [0, 4, 2].

Moreover, if I generalize away the last hint, i.e., if I write:

lock(Vs) :-
        Vs = [_,_,_],
        Vs ins 0..9,
        num_correct_placed(Vs, [6,8,2], 1, 1),
        num_correct_placed(Vs, [6,1,4], 1, 0),
        num_correct_placed(Vs, [2,0,6], 2, 0),
        num_correct_placed(Vs, [7,3,8], 0, 0),
        * num_correct_placed(Vs, [7,8,0], 1, 0).

then the unique solution can still be determined without search:

?- lock(Vs).
Vs = [0, 4, 2].

In fact, I can even also take away the penultimate hint:

lock(Vs) :-
        Vs = [_,_,_],
        Vs ins 0..9,
        num_correct_placed(Vs, [6,8,2], 1, 1),
        num_correct_placed(Vs, [6,1,4], 1, 0),
        num_correct_placed(Vs, [2,0,6], 2, 0),
        * num_correct_placed(Vs, [7,3,8], 0, 0),
        * num_correct_placed(Vs, [7,8,0], 1, 0).

and still the solution is unique, although I now have to use label/1 to find it:

?- lock(Vs), label(Vs).
Vs = [0, 4, 2] ;
false.

这篇关于Prolog 中的锁定挑战的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！