4

For my "Declarative Languages" class we have to write a prolog program that solves Tangram puzzles. A puzzle is identified by a list of coordinates of the points of the puzzle. For example, puzzle(7,[(0,0),(8,0),(4,4)]) is a puzzle with identifier 7 and represents a triangle.

Here is my (naive) way of solving this. The execution starts with calling tangram(Puzzle, Puts). The program starts with all the possible pieces of the puzzle. I then pick a piece, try a position and a rotation and if this gives a valid position for the puzzle, I place the puzzle. (= place the block in the Puts list, which will be returned at the end of the program.) I backtrack over all these possibilities. Here's the code:

    %Harm De Weirdt
%3e Bachelor Informatica
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%        MAIN PROGRAM         %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%    
%All possible rotations of a piece.
angle(0).
angle(90).
angle(180).
angle(270).

%Puzzle is a list of the coordinates of the corners of the puzzle to be solved.
%Puts is a list of 7 elements indicating how each piece should be placed in order to solve the puzzle.
tangram(Puzzle, Puts):-
    findall(block(BlockId, PointList), block(BlockId, PointList), PossiblePieces),
    placePieces(PossiblePieces, Puts, Puzzle).

%placePieces(Pieces, Puts)
%Place all the puzzle pieces from Pieces on the puzzle.
%Puts is a list containing the position of all the pieces.
placePieces([], _,_).
placePieces([block(BlockId, PointList)|OtherPieces], Puts, Puzzle):-    
    between(0,8,X),
    between(0,6,Y),
    angle(Angle),
    allowedPosition(PointList, (X,Y), Angle, Puzzle, Puts),
    append(Puts, [put(BlockId, ((X,Y), Angle))], NewPuts),
    placePieces(OtherPieces, NewPuts, Puzzle),
    write(Puts).

allowedPosition(Block, (X,Y), Angle, Puzzle, Puts):-    
    rotatePolygon(Block, Angle, RotatedPolygon),
    translatePolygon(RotatedPolygon, (X,Y), TranslatedPolygon),
    insideFigure(TranslatedPolygon, Puzzle),
    noOverlap(TranslatedPolygon, Puts).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%       EXTRA PREDICATES      %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
%translate(Point, TranslationVector, TranslatedPoint)
%TranslatedPoint is the result of Translating Point with TranslationVector
translate((X, Y), (TX, TY), (RX, RY)):-
    RX is X + TX,
    RY is Y + TY.

%translatePolygon(Polygon, TranslationVector, TranslatedPolygon)
%Translates a Polygon, defined by a list of its Points, by  a given TranslationVector,
%resulting in the TranslatedPolygon
translatePolygon([], _Vector, []).
translatePolygon([(X,Y)|Rest], (TX, TY), TranslatedPolygon):-
    translatePolygon(Rest, (TX, TY), PartiallyTranslatedPolygon),
    translate((X, Y), (TX, TY), (NewX, NewY)),
    TranslatedPolygon = [(NewX, NewY)| PartiallyTranslatedPolygon].

Some possible puzzles: 

[(0,0),(4,0),(4,4),(0,4)]
[(3,0),(5,2),(5,4),(4,5),(2,5),(0,3)]
[(0,0),(6,0),(7,1),(7,3),(3,3)]

The problem when I run this is that I get the following error: 

 ERROR: is/2: Arguments are not sufficiently instantiated

When tracing it seems that somehow the TX and TY values in Translate aren't instantiated. Tracing back I think that somehow X and Y don't get instantiated in the placePieces predicate. If there were no values left, the predicate would just fail, right?

I have been looking at my code for over 5 hours and can't seem to find my mistake. Hopefully one of you has the time to look this over and set me back in the right direction.

Thanks in advance!

4

2 回答 2

3

如果您只使用 CLP(FD) 约束进行算术，这个错误就会消失。只需用(is)/2约束替换(#=)/2：

:- use_module(library(clpfd)).

translate((X, Y), (TX, TY), (RX, RY)):-
    RX #= X + TX,
    RY #= Y + TY.

重要的是，(#=)/2可以在所有方向上使用，即使变量仍然出现在其参数中。

其他的建议：

  1. 考虑使用(-)/2来表示pairs，ieX-Y等。
  2. 将maplist/3帮助您缩短代码。
于 2016-03-28T11:47:57.020 回答
1

尝试获取错误的堆栈跟踪。一些 Prolog 系统在发生错误时显示堆栈跟踪：SWI Prolog、SICStus Prolog、Jekejeke Prolog。

您必须对您的 Prolog 系统进行一些试验。由于各种原因，可能不会显示堆栈tarce。例如尝试正常咨询而不是编译。或者尝试打开调试模式而不是正常执行。

此外，如果 Prolog 系统在发生错误时自动进入调试器，您可能看不到堆栈跟踪。但通常调试器会为您提供显示堆栈跟踪的命令。典型的命令是：g 代表目标（回溯）。

当您看到堆栈跟踪时，您可以更准确地确定问题发生的位置。

于 2011-12-08T17:17:12.500 回答