159.302 Artificial Intelligence

Assignment #1

The 8-Puzzle: Comparing Search Algorithms

Maximum number of members per group: 3 students

Deadline for submission: May 2, 2012

Instructions

Your task is to write a program that will solve the 8-puzzle problem using four different search algorithms, one after the other.

An AnimateSolution() function has been provided that you can use to animate the sequence of moves (i.e. path) calculated by the algorithms. A start-up program (compiles with ScITE) with a graphics library is available for downloading from our website:

It is up to you to write any functions , classes or data structures that you may require. You can use any printf()(or cout)to trace the algorithm execution.

For each implementation of the algorithms below, include codes that will capture the following information during the algorithm’s execution:

  1. Max. Queue length – e.g. 26
  2. Path length - e.g. 30
  3. Number of state expansions – e.g. 157
  4. Sequence of moves – e.g. DDRRULUL
  5. Actual running time in seconds (use the clock() function as shown in the sample codes in slides)

Part 1: Depth-First Searchusingthe Visited List:
Write code that uses the s (initialstate) and g (a goalstate) and returns the sequence of moves.

Part 2: Breadth-First Search using the Visited List:
Write code that uses thes (initialstate) and g (a goalstate) and returns the sequence of moves.

Part 3: Progressive Deepening Search

Write code that uses the s (initialstate) and g (a goalstate) and returns the sequence of moves.

Part 4: A* Searchusing the Strict Expanded List:

Write a function in the same form as Part 1 to implement the A* algorithm with Strict Expanded List and using the following heuristic:

A* with Strict Expanded List and using the Sum of Manhattan Distances as heuristic

Part 5:Algorithm Documentation

Write a pseudo code (or flow chart) for each of the algorithm (in Parts 1, 2, 3 4) implementation. Discuss also the data structures and variables you have used.

Part 6: Tests and Results

Test all the algorithms using the given 5 starting states and 1 goal state below.

Include in your documentation the following information for each test case and algorithm combination:

  1. Max. Queue length
  2. Path length
  3. Number of state expansions
  4. Sequence of moves (e.g. d, l, r, etc.)
  5. Actual running time in seconds

Accomplish the given table below to summarize your results.

Algorithm / Initial State / Max. Queue length / Path length / No. of state expansions / Sequence of moves / Actual Running Time (sec.)
1 / DFS using the Visited List / 042158367
2 / BFS with Visited List / 042158367
3 / Progressive Deepening Search / 042158367
4 / A* using the Strict Expanded List / 042158367
5 / DFS using the Visited List / 876543210
6 / BFS with Visited List / 876543210
7 / Progressive Deepening Search / 876543210
8 / A* using the Strict Expanded List / 876543210
9 / DFS using the Visited List / 481302675
10 / BFS with Visited List / 481302675
11 / Progressive Deepening Search / 481302675
12 / A* using the Strict Expanded List / 481302675
13 / DFS using the Visited List / 168342750
14 / BFS with Visited List / 168342750
15 / Progressive Deepening Search / 168342750
16 / A* using the Strict Expanded List / 168342750
17 / DFS using the Visited List / 123804765
18 / BFS with Visited List / 123804765
19 / Progressive Deepening Search / 123804765
20 / A* using the Strict Expanded List / 123804765

Note: # - blank space

GOALSTATE: ((# 1 2)

(3 4 5)

(6 7 8))

A set of starting states of differing complexity:

START1: ((# 4 2)

(1 5 8)

(3 6 7))

START2: ((8 7 6)

(5 4 3)

(2 1 #))

START3: ((4 8 1)

(3 # 2)

(6 7 5))

START4: ((1 6 8)

(3 4 2)

(7 5 #))

START5: ((1 2 3)

(8 # 4)

(7 6 5))

Marking:

Make sure your program compiles using gcc before handing it in.

Effective comments make it easier to award marks or partial points if the program is not 100% working properly.

You can work as agroup for this assignment. Copied work will be awarded zero marks.

Hints:

Some random combinations of pieces for your initial state are unsolvable.

Refer to the lecture slides for concepts.

You can step through the search by including a getch() function inside your main loop to pause the program until the user presses any key.

Example Sequence:

Sequence of states and operations.

You may choose to represent states in an array, size 9. You can represent operations with the 'u' 'd' 'l' 'r' characters.

In notation, the sequence s to get to the goal from the initial state could be represented:

s = {d,r,u,u,l,d} You may find it helpful to printf()(or cout) something similar to help debug your program.

Nothing follows.

N.H.Reyes