时间戳

首页 > 解决方案 > Prolog：根据原始列表生成解决方案

prolog - Prolog：根据原始列表生成解决方案

问题描述

我是Prolog的初学者，我搜索了很多但无法解决问题。问题是给我一个给定列表头部的列表，例如[20,_,_,_].

  1. 列表的长度未知。例如，它可能是[30,_,_,_,_,_].
  2. the_是不同的因子，它只包含从 1 到 9 的数字。例如，[20,_,_,_]可以生成[1,4,5]及其组合。
  3. 该列表可以先填写一个数字。例如，[20,_,4,_]。输出仍然是[1,4,5]and [5,4,1]。

我尝试的是撕掉列表的头部，并尝试将其余元素生成回原始列表，但我失败了，并且无法理解调试器及其跟踪信息。

removeHead([Head|Tail],Tail).

get_head_element([],_).
get_head_element([Head|Rest],Head).

divide(1,[],_).
divide(Number,[Head|List],Result):-
    0 is mod(Number,Head),
    Quotient is Number/Head,
    divide(Quotient,List,Result).

solve_multiply(Row,RestRow):-
    get_head_element(Row, Goal),
    removeHead(Row,RestRow),
    all_distinct(RestRow),
    RestRow ins 1..9,
    divide(Goal,RestRow,RestRow).

我可以继续解决这个问题的任何资源提示？谢谢。

编辑： 我认为列表中相乘的元素在头部是相同的另一种方式，所以我写了一个乘法谓词。

%% multiply(+List,-Result)
%
% for calling the multiply(+List,+PrevResult,+Result) with accumulator set to 1
multiply(List,Result):-
    multiply(List,1,Result).

%% multiply(+List,+PrevResult,+Result)
%
% multiply each element in the list
multiply([Element|RestList],PrevResult,Result):-
    NextResult is PrevResult * Element,
    multiply(RestList,NextResult, Result).

%% multiply([], -Result, -Result).
%
% multiply predicate stops when all the elements have been multiplied
multiply([], Result, Result).

%% solve_multiply(+Row,-RestRow)
solve_multiply(Row,RestRow):-
    get_head_element(Row, Goal),
    removeHead(Row,RestRow),
    RestRow ins 1..9,
    multiply(RestRow,Goal), % get the Arguments not sufficiently instantiated message
    all_distinct(RestRow).

标签： prologclpfd

解决方案

找到解决方案的最简单方法是：

  1. 将相乘的元素与头部元素进行比较。
  2. 使用 clpfd 提供的约束。

因此，代码应该是：

multiply(List,Result):-
    multiply(List,1,Result).

multiply([Element|RestList],PrevResult,Result):-
    NextResult #= PrevResult * Element, % constraint that works for both side ?X #= ?Y
    multiply(RestList,NextResult, Result). % tail recursion

multiply([], Result, Result).

solve_multiply(Row,RestRow):-
    get_head_element(Row, Goal),
    removeHead(Row,RestRow),
    RestRow ins 1..9,
    multiply(RestRow,Goal),
    all_distinct(RestRow).

调用时solve_multiply([20,_,_,_],X), labeling([],X).的结果是：

X = [1, 4, 5] ;
X = [1, 5, 4] ;
X = [4, 1, 5] ;
X = [4, 5, 1] ;
X = [5, 1, 4] ;
X = [5, 4, 1] ;
false.

调用时solve_multiply([20,_,1,_],X), labeling([],X).的结果是：

X = [4, 1, 5] ;
X = [5, 1, 4].

推荐阅读