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

By Kannan Gangadharan, Weiyang Lin, Jason Reposa, and Prof. Carolina Ruiz

• 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.

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).
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.

We need to generate and test every possible combination of digits from 0 to 9 to the alphabets F, O, R, T, Y, E, N, S, I and X. However it is possible to optimize the solution by loking carefully at the problem.

N and E both can take each one of two values 0 or 5. But since in the tens digit addition we need T + 2E + (carry over from units digit) = T or (10+T) hence N = 0. It follows that E = 5. Further in the thousands digit addition we have O + (carryover from hundreds place) = 10 + I. Since N = 0 hence I = 1. It follows that 0 = 9. Using this knowledge helps us to develop an informed generator. The generator is complete if we test and exhaust all possible permutations of values for the alphabets that satisfy the contraints mentioned above.

The code presented below implements a complete, informed generator. Each combination generated is tested on the fly instead of storing the combinations. The generator is non-redundant as it produces all the possible combinations in a proper sequence thus making sure that no combination is generated twice.

The code is as follows.

```
#include"stdio.h"
#include"math.h"

// By nature of the problem some variables can have only selected values.
// N = 0; E = 5; O = 9; I = 1;
// Using this in the generator makes it informed.

int N = 0;
int E = 5;
int O = 9;
int I = 1;
int F, R, T, Y, S, X;

main()
{
generate();
}

generate()
{
for(F=2;F<=8;F++) {
if (F==E) F++;
for(R=2;R<=8;R++) {
if ((R==F)||(R==E)) R++;
if ((R==F)||(R==E)) R++;
if (R>8) continue;
for(T=2;T<=8;T++) {
if ((T==F)||(T==R)||(T==E)) T++;
if ((T==F)||(T==R)||(T==E)) T++;
if ((T==F)||(T==R)||(T==E)) T++;
if (T>8) continue;
for(Y=2;Y<=8;Y++) {
if ((Y==F)||(Y==R)||(Y==T)||(Y==E)) Y++;
if ((Y==F)||(Y==R)||(Y==T)||(Y==E)) Y++;
if (Y>8) continue;
for(S=2;S<=8;S++) {
if ((S==F)||(S==R)||(S==T)||(S==Y)||(S==E)) S++;
if ((S==F)||(S==R)||(S==T)||(S==Y)||(S==E)) S++;
if ((S==F)||(S==R)||(S==T)||(S==Y)||(S==E)) S++;
if ((S==F)||(S==R)||(S==T)||(S==Y)||(S==E)) S++;
if ((S==F)||(S==R)||(S==T)||(S==Y)||(S==E)) S++;
if (S>8) continue;
for(X=2;X<=8;X++) {
if ((X==F)||(X==R)||(X==T)||(X==Y)||(X==E)||(X==S)) X++;
if ((X==F)||(X==R)||(X==T)||(X==Y)||(X==E)||(X==S)) X++;
if ((X==F)||(X==R)||(X==T)||(X==Y)||(X==E)||(X==S)) X++;
if ((X==F)||(X==R)||(X==T)||(X==Y)||(X==E)||(X==S)) X++;
if ((X==F)||(X==R)||(X==T)||(X==Y)||(X==E)||(X==S)) X++;
if ((X==F)||(X==R)||(X==T)||(X==Y)||(X==E)||(X==S)) X++;
if (X>8) continue;
test();
}
}
}
}
}
}
}

test()
{
int FORTY, TEN, SIXTY,RHS;
FORTY = (F*10000+O*1000+R*100+T*10+Y);
TEN = (T*100+E*10+N);
SIXTY = (S*10000+I*1000+X*100+T*10+Y);

RHS = FORTY + TEN + TEN;
if (SIXTY == RHS)
printf("FORTY - %d\nTEN - %d\nSIXTY - %d\n\n", FORTY,TEN,SIXTY);
}

```

The only solution generated is -
FORTY - 29786
TEN - 850
SIXTY - 31486

1. S should be F + 1;
2. Your tester only need to test R + T + T = 20 + X.

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)

Solutions - By Jason Reposa (a student in the course) Thanks Jason!!

Depth 1st

Depth-limited Search (depth-limit = 3)

Iterative Deepening Search

Branch-and-bound (= Uniform Cost Search)

Greedy Search (Best 1st Search)

A*

Hill-climbing

Beam Search

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 to be negative would affect the search methods below, and illustrate the effects of this change with examples.
1. Depth 1st
3. Depth-limited Search
4. Iterative Deepening Search
5. Branch-and-bound (= Uniform Cost Search)
6. Greedy Search
7. A*
8. Hill-climbing
9. Beam Search
10. Best 1st Search (= Greedy Search)

Solutions - By Weiyang Lin

• Depth 1st Search, Breadth 1st Search, Depth-limited Search, Iterative Deepening Search: Because these four search methods do not consider cost, it will not make any difference to these methods if we allow negative costs.

• Branch-and-bound (= Uniform Cost Search): For only positive costs, Branch-and-bound is guaranteed to find the optimal solution if there is one. For negative costs, this is not true anymore. Consider the following case,

TREE 1

S
10 / \ 20
G   B
| -100
G

Clearly the optimal path from S to G is S->B->G with total cost -80. However, branch-and-bound would go over the whole process below:
1. Add S to the queue:    Queue = [S]
2. Expand S:                    Queue = [G: g(G)=10, B: g(B)=20]
3. Expand G:                   Goal!
So the path we found s->G is not the optimal path.

• A*: For only positive costs, A* search is guaranteed to find the optimal solution if there is one. For negative costs, this is not true. Consider the following case,

TREE 2

S
10 / \ -10
h=0  G   B0  h=10
| -10
B1  h=10
| -10
B2  h=10
| -10
B3  h=10
... (the branch continues like this infinitely without reaching G)

Notice that h should be an underestimate and Bn is an infinite path not leading to G.
From start state S, we would go over the process below:
1. Add S to the queue:    Queue = [S]
2. Expand S:                    Queue = [B0: f(B0)=0, G: f(G)=10]
3. Expand B0:                  Queue = [B1: f(B1)=0, G: f(G)=10]
2. Expand B1:                  Queue = [B2: f(B2)=0, G: f(G)=10]
3. Expand B2:                  Queue = [B3: f(B3)=0, G: f(G)=10]
...
So we will go forever and never find a solution.

• Greedy Search(Best 1st Search): For only positive costs, greedy search guarantees to find a solution (not necessarily an optimal solution) if there is one. But for negative costs, from the example for A* search, we could see it might go forever and not find any solutions even if there is one available.

• Hill-climbing: Hill climbing is not guaranteed to find a solution, even if one exists. And if it finds a solution, it is not necessarily an optimal one. However, allowing negative cost may make things even worse, since hill-climbing can follow a infinite path of nodes with negative values of h which doesn't converge to a goal state. This would happen for instance when applying hill-climbing to the TREE 2 above.

• Beam Search: Beam search is not guaranteed to find a solution, even if one exists. And if it finds a solution, it is not necessarily an optimal one. However, allowing negative cost may make things even worse, since beam search can select for expansion an infinite collection of nodes (m per level) with negative values of h without reaching a goal state. This would happen for instance when applying beam search with m=1 to the TREE 2 above.