T-93.540 Logic programming

T-93.540 Logic Programming, autumn 2005

Home Exercises

This is the second part of the home exercises. By returning the answers to these proglems students can earn two points for the exam. The deadline for the return, see the course top home page. Return is done by submit-system, see quide.
You may solve these exercises using any constraint logic programming system. The course supports a constraint logic programming system called Eclipse. You must solve the exercises using CLP properties of the system to get any points.

You should read the pages 1-40 in the Eclipse library manual links to which can be found at: Eclipse-quides.

The answer will have to include sufficient test runs.
These exercises are meant to introduce students to constraint logic programming.

Problem 5:
Ivan Helsin is building a new house near Murmansk. The construction company promises to finish the house in two weeks. Different stages can be taken concurrently and they take time according to the following:

Foundations: must be done first, 7 days.
Interior walls: requires foundations, 4 days.
Exterior walls: requires foundations, 3 days.
Chimney: requires foundations, 3 days.
Roof: requires exterior walls, 2 days.
Windows: requires exterior walls, 3 days.
Tiles: requires chimney and roof, 3 days.
Doors: requires interior walls, 2 days.
Make a constraint logic program that describes the construction progress. Can you trust in the construction company's promise?
Problem 6:
One of the house's rooms is a library. On one wall of the library, there will be presented a big map of the countries of Northern and Eastern europe. The countries on the map will be colored with different colors. Each country on the map has the following neighbors:
neighbors(finland, [sweden, norway, russia]).
neighbors(sweden, [finland, norway]).
neighbors(norway, [finland, sweden, russia]).
neighbors(russia, [estonia, finland, latvia, lithuania, belarus, ukraine]).
neighbors(estonia, [russia, latvia]).
neighbors(latvia, [russia, estonia, lithuania, belarus]).
neighbors(lithuania, [latvia, belarus, poland, kaliningrad]).
neighbors(kaliningrad, [lithuania, poland]).
neighbors(belarus, [poland, lithuania, latvia, russia, ukraine]).
neighbors(ukraine, [poland, belarus, russia]).
neighbors(poland, [kaliningrad, lithuania, belarus, ukraine]).
Make a constraint logic program which colors the map with four colors [red, violet, blue, white] so that no two neighbors share the same color. Your program should solve the following questions, for example:

a) The Kaliningrad district is politically part of Russia. Can you still use four different colors for the map if you use the same colors for these two countries?
b) If you color Estonia with blue, Latvia with red and Lithuania with violet, what colors are legal for Finland?

Problem 7:
When the house is finished, it's time to move in the furniture. Ivan Helsin has hired three men to help him (so there's four to do the job.)

Piano, requires 3 men for 30 minutes.
Chair, requires 1 man for 10 minutes.
Bed, requires 3 men for 15 minutes.
Table, requires 2 men for 15 minutes.
It the total operation takes more than an hour, the helpers will get angry and demand more pay.
a) Make a constraint logic program to create possible operations so, that the length of the total operation will not exceed an hour. Use the minute as the basic unit of time.
b) Use your program to solve how fast the operation can be done with 3, 4, 6 or 9 men.
Problem 8:

Maka a constraint logic program to solve 9X9 Sudoku. (Sudoku - See part 3. in series I of homeworks). Use Eclipse finite domain (fd) library. (Documentation link on demo/exercise 2 page). Construct a method which should check sizes of variable domains and direct labeling based on that.