Tents and Trees puzzle

This assignment consists in solving the tents and trees puzzle (try here an online game) described as follows. We have a grid of n x n cells. Some cells contain trees that constitute a fixed input, and the rest have to filled with a tent or left empty. Besides, each row and each column are assigned a number (of tents to be placed). The rules for placing tents are as follows:

1. Each tree must have a uniquely associated tent that must be next to the tree, either horizontally or vertically (diagonal doesn't count).
2. Tents cannot touch each other, even diagonally.
3. The number of tents placed in each row (respectivelly, column) must coincide with the assigned input number for that row (resp. column).

The following images show an example of initial configuration of a puzzle (6 x 6) and the final solution where, additionally, we have also represented which tent is associated to each tree, using a small red line.

Initial configuration	Solved puzzle

Step 1. Each input instance is an ASCII file containing a squared grid (n x n) with the following format. The file contains n lines (the rows) and each line contains n characters (the columns) ended by a newline. Each cell contains a character that can be:

•  't' = a tree
• '.' = an empty cell that can be filled with a tent or can be left empty

The last two lines contain the numbers associated to columns (first line) and rows (second line) separated by blank spaces.

The following shows the input format for the initial configuration above:

..t... .t.... t....t ...... ....t. t...t. 1 2 0 1 1 2 2 1 0 2 0 2

The file examples.zip will contain several input files and their solutions. [Warning: examples dom06.txt has no solution]

Step 2. Write a python program encode.py to transform each input ASCII file into a logic program containing facts. For instance:

python3 encode.py dom01.txt domain.lp

will transform the example above into the set of facts for the predicates you decide to use for representing the problem. The file domain.lp can only contain facts and constant definitions, but no conditional rules or constraints.

Step 3. Encode the tents problem in clingo in a file called tents.lp. You can use

clingo 0 tents.lp domain.lp

to obtain all the answer sets. You should check that each puzzle should have a unique solution. You can use the following file decode.py that allows printing the solution as an output text file:

python3 decode.py tents.lp domain.lp

To use this program, you need output facts like tree(X,Y) to represent a tree and a predicate tent(X,Y) to represent a tent. You also need a predicate dim(N) to specify the size of the grid -- in the example above, dim(6). The result produced by this program will have the form

.xtx.. .t...x t....t x...x. ....t. tx..tx

Where 'x' represents a tent.

Finally, if you have installed the python library pygame, you can also draw a graphical representation using the files display.py, drawtents.lp and pics.zip as follows. First, unzip de pictures file:

unzip pics.zip python3 display.py tents.lp domain.lp drawtents.lp

Assessment & delivery