11:59PM Monday, April 14, 2008.

After completing this assignment you will:

Similar to Assignment 2, you are to implement a Prolog predicate to generate all possible free polyominoes of a given degree. See that assignment for background information on polyominoes.

As with Assignment 3, please define the predicate student_name/1 and include this with your submission. Example:

student_name("Sally Student").

A polyomino is represented by a list of coordinate pairs. Since this list models a mathematical set, the order of the points in the set is not significant. See the description of Assignment 3, set_eq/2.

We further define the notion of a "normalized" polyomino to be translated to the x-axis and y-axis. Meaning the polyomino has at least on coordinate on the x-axis and one coordinate on the y-axis, but no coordinates negative.

The following predicate tests whether a polyomino has been normalized, and only succeeds if it is normalized.

normalized(P) :- no_negatives(P), has_zero_x(P), has_zero_y(P).
no_negatives([]).
no_negatives([[X,Y]|Rest]) :- no_negatives(Rest), X >= 0, Y >= 0.
has_zero_x([[0,_]|_]) :- !.
has_zero_x([_|Rest]) :- has_zero_x(Rest).
has_zero_y([[_,0]|_]) :- !.
has_zero_y([_|Rest]) :- has_zero_y(Rest).

For example,

| ?- normalized([[0, 0]]).

yes
| ?- normalized([[0, 0], [0, 1]]).

yes
| ?- normalized([[1,0]]).

no
| ?- normalized([[1, 1], [1, 2]]).

no

Implement the predicate, polyomino/2 that generates a polyomino of a given degree and further generates all remaining normalized polyominoes under backtracking.

Here are some examples.

| ?- polyomino(1, [[0, 0]]).

yes

Degree 1 has only one solution because there is exactly one monomino.

| ?- polyomino(2, P).

P = [[0, 0], [0, 1]]

yes

Degree 2 has only one solution because there is exactly one domino.

Note that your implementation could have instead produced,

P = [[0, 0], [1, 0]]

| ?- polyomino(3, P).

P = [[0, 0], [0, 1], [0, 2]]  ?;

P = [[0, 0], [0, 1], [1, 0]]  ?;

no

Degree 3 has exactly two solutions because there are exactly 2 triominos.

Here is a predicate to generate all neighbor points from a given (x, y) coordinate pair. A coordinate pair is represented by a list with two elements. The first is the x-coordinate; the second is the y-coordinate. There are exactly eight neighbor points. Here is the program and some query examples to demonstrate its behavior.

neighbors([X, Y], [[Xup, Yup], [Xup, Y], [Xup, Ydn],
                   [X, Yup],             [X, Ydn], 
                   [Xdn, Yup], [Xdn, Y], [Xdn, Ydn]]) :-
   Xup is X + 1, Xdn is X - 1, Yup is Y + 1, Ydn is Y - 1.

Here are the example queries.

| ?- neighbors([0,0], Lst).

Lst = [[1,1],[1,0],[1,-1],[0,1],[0,-1],[-1,1],[-1,0],[-1,-1]]

yes
| ?- neighbors([2,2], Lst).

Lst = [[3,3],[3,2],[3,1],[2,3],[2,1],[1,3],[1,2],[1,1]]

(1 ms) yes

Notice that "is" acts like an assignment. The expression on the right-hand side is evaluated, so "is" performs the addition or subtraction. However unlike other Prolog predicates, "is" only binds in one direction. So for example,

| ?- Sum is 2 + 3.

Sum = 5

(1 ms) yes
| ?- 5 is X + 2.
uncaught exception: error(instantiation_error,(is)/2)
| ?- Y = 3, 5 is Y + 2.

Y = 3

yes

The right-hand side of the "is" must have values that are integers or variables already ground to integer values, otherwise an exception gets thrown.

Submit via e-mail using a mime-encoded, zipped attachment. (Note, most e-mail client programs do mime-encoding automatically for you, but to create the zip file attachment, you will need to use zip utility. The zipped attachment must be named, a4.zip, which contains one file, a4.pro in the current directory (i.e., root of the zip archive).

To: martin@cs.sjsu.edu
Subject: A4