### CS4341 Introduction to Artificial Intelligence  HOMEWORK 1 - C 2000

#### PROF. CAROLINA RUIZ

DUE DATE: Tuesday, Jan 25 at 5 pm.

• Instructions for Homework 1:
• This is an INDIVIDUAL homework
• The homework is due Tuesday, January 25, 2000 at 5 pm.
Please turn in the homework using the turnin system.

• Homework Problems: This homework consists of two (plus an additional problem for students who are taking this course for graduate credit) problems:

### Problem 1 (40 points + extra-points): Problem Solving Strategies

Consider the following puzzle (taken from Russell and Norvig's textbook, 1995)

This puzzle consists in finding a substitution of the letters F, O, R, T, Y, E, N, S, I, X by digits such that when each of these letters is replaced by the corresponding digit, the following sum is still arithmetically correct.

FORTY
+ TEN
+ TEN
-----
SIXTY

This puzzle has solutions. One of them is

F = 2, O = 9, R = 7, T = 8, Y = 6, E = 5, N = 0, S = 3, I = 1, X = 4

since:

29786
+ 850
+ 850
-----
31486

is arithmetically correct. Solutions to the puzzle should not repeat digits.

Your mission is to:

1. Design a computer system that uses the generate-and-test strategy to solve this puzzle.
• Your system must satisfy the following conditions:
• It should find at least one solution to the puzzle.
• The generator must be
• complete, and
• non-redundant

2. Write a computer program using any high level programming language (Lisp, Prolog, C, C++, ...) that implements the system you designed to solve this puzzle. Your program must run in the CCC machines.

3. You will receive extra credit if:
• your program produces a solution to the puzzle different to the one given above (extra points for each additional correct solution found), OR if you prove (providing a formal argument) that no other solutions are possible.
• your generator is informed.

For this problem, you need to "turnin" the following material by the deadline:

• A description of your system (generator and tester) together with formal arguments showing that the generator is complete and non-redundant.
• Your program code. Your program code should be documented using the departmental documentation standard
• A transcript containing the solutions found by your program.
• A precise count of how many different candidate solutions your generator would produce before exhausting all possibilities.
• For the extra credit you need to include also:
• A formal argument showing that your generator is informed.

### Problem 2: Search (60 points)

Consider the graph on page 634 (figure E4.1) of your textbook. S denotes the starting state and G denotes the goal state. The number attached to each edge in the graph represents the COST of traversing the edge. Assume also that the ESTIMATED distances to the goal are given by the following table:
 FROM TO ESTIMATED DISTANCE S G 10 A G 8 B G 5 C G 1.4 D G 9 E G 6 F G 2 G G 0
For EACH of the following search methods show the search tree as it is explored/expanded by the method until it finds a path from S to G. Number the nodes in the order in which they are expanded by each method. Show your work.
1. Depth 1st
3. Depth-limited Search (depth-limit = 3)
4. Iterative Deepening Search
5. Branch-and-bound (= Uniform Cost Search)
6. Greedy Search (= Best 1st Search)
7. A*
8. Hill-climbing
9. Beam Search (m = 2)

### Problem G: Additional Graduate Credit Problem (20 points)

We have computed optimal paths under the assumption that COSTS are non-negative. Suppose that we remove that assumption. Discuss how allowing some of the costs (both g and h values) to be negative would affect the search methods below, and illustrate the effects of this change with examples.
1. Depth 1st