As announced assignment # 1 consist of 3 parts: a self-explorartory on-line task, some paper and pencil work, and some programming. The total credit is 100 points for the whole assignment. Points are given in brackets.

Due date: Mo 15.11.2004

Please go to

UBC

(page protected with the usual username & password)

alternatively go to:

http://www.cs.ubc.ca/labs/lci/CIspace/Version4/search/index.html

and try out all the search algorithms. Ask yourself whether you can find all the differences between the algorithms addressed in class.

Attention: Constraints of part a) slightly changed due to discovered inconsistency!!!

Consider the following logic puzzle: In five houses, each with a different color, live 5 persons of different nationalities, each of whom prefer a different brand of cigarette, a different drink, and a different pet.

a) Given the following facts, the question to answer is "Where does the zebra live, and in which house do they drink water?" (5)

• The Englishman lives in the red house.
• The Portuguese owns the dog.
• The Norwegian lives in the first house on the left.
• Marlboro are smoked in the yellow house.
• The man who smokes Chesterfields lives in the house next to the man with the fox.
• The Norwegian lives next to the blue house.
• The Barclay smoker owns a rabbit.
• The Lucky Strike smoker drinks orange juice.
• The Russian drinks tea.
• The Chinese smokes Parisienne.
• Marlboro are smoked in the house next to the house where the horse is kept.
• Coffee is drunk in the green house.
• The Green house is immediately to the right (your right) of the white house.
• Milk is drunk immediately to the right (your right) of the yellow house.

b) Formulate the problem in terms of variables, domains, and constraints. (5)

c) Enter the problem into the applet that can be found and downloaded from here. Find the solution using the algorithm. (5)

Please note:

1. If you choose the applet, you might NOT want to use any string-set domains (but integers), as the number of constraint types is too limited with strings!
2. Another possiblity to solve this logic puzzle is to implement a very small program that tries to find a proper solution to the problem. Extra credits will be given!!!

What to hand in:

• b) A textual definition of the problem (domains, variables, etc.)
• c) A screen-dump/output of the applet

Terminology

Sliding Block Puzzle starting frames are depicted in figures 1a and 2a whereas finishing (goal) frames are shown in figures 2a and 2b. A field of the frame is called a checker. One shape (LADYBUG, SPIDER, FISH, WORM) is using at least on checker in size.

Assignment

• a) Formulate the above Sliding Block Puzzle problems in STRIPS planning language. (see Page 377 – 382, Artificial Intelligence – A Modern Approach, Second Edition) (25)
• b) Formally describe at least two searching strategies for solving Sliding Block Puzzles in pseudocode, at least one as brute-force searching and one as informed searching strategy. (15)
• c) Implement the Sliding Block Puzzle solving problem in Java with your designed strategies (see implementation notes below). (30)
• d) Analyze the advantages and disadvantages for the different searching strategies that you use in your program on dimension of completeness, time, space and optimality. (10)

Implementation Notes

A small application providing six classes has been written to provide an appropriate environment that allows a direct implementation of different search strategies. The Java source code of the application can be downloaded as jar file (version: 1.11.2004). First unpack the jar file into a directory. If you have not installed Java on your system go to Sun's Java web page and download the appropriate Java package for your machine. Follow the instruction on the page to install Java on your machine.

Change directory to where you have unpacked the jar file and enter java -cp . puzzle.Run. You see the initial frame layout (compare figure 1a). Numbers between 0 and 10 represent shapes, -1 an empty checker. You can now start to play around with the puzzle by simply choosing the shape you want to move and the corresponding move to perform (up, down, left, right). Enter q at any point in time to exit the program.

It is your task now to implement at least two searching strategies to solve the Sliding Block Puzzle problem and to obtain the goal (finishing) frames (compare figures 1b and 2b). Therefore make yourself familiar with the given code. You are free to completely change/modify/update the code to suit your needs.

Just a few remarks about the code:

• A shape is given by its top left corner and its shape dimensions.
• It is assumed that a shape can only move one checker per time step.
• All moves have equal weight (cost) of 1 at the moment, you may change this according to your strategy.

What to hand it:

• a) A textual description of the answer
• b) A textual description of the answer
• c) Each of your strategies should be an extension of class PuzzleSolver. Therefore hand in these classes named in the following way: <CLASSNAME>_<YOURNAME> where className means the name of the implemented strategy and yourName simply is your name, e.g. depthFirstSearch_ChristophKiefer.
• d) A textual description of the answer

Please note: Extra credits are given for designing and implementing more searching strategies as well as for other (nice, but optional) things like a GUI etc.

Please do not hesitate to contact us (Jiweng Li, Christoph Kiefer) if you have questions or remarks of any kind.