Question

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!

No correct solution

OTHER TIPS

This error will go away if you simply use CLP(FD) constraints for arithmetic. Simply replace (is)/2 by the constraint (#=)/2:

:- use_module(library(clpfd)).

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

Importantly, (#=)/2 can be used in all directions, also if variables still occur in its arguments.

Other comments:

  1. consider using (-)/2 to represent pairs, i.e., X-Y etc.
  2. The maplist/3 will help you to shorten your code.

Try obtaining a stack trace with the error. Some Prolog systems show a stack trace when an error occurs: SWI Prolog, SICStus Prolog, Jekejeke Prolog.

You have to experiment a little bit with your Prolog system. For various reasons the stack tarce might not be shown. For example try normal consult instead of compile. Or try debug mode on instead of normal execution.

Also you might not see the stack trace if the Prolog system enters automatically the debugger when an error occurs. But often the debugger offers you a command to show the stack trace. The typical command is: g for goals (backtrace).

When you see the stack trace you can more closely pin down where the problem occurs.

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top