CSC 411: Artificial Intelligence
(Fall 2006)
Programming Project 2: Search Control Algorithms
Due by November 9, Thursday, 2006
Write Prolog programs for the following search control algorithms:
a. Depth-first search,
b. Breadth-first search, and
c. Best-first search.
Your search control algorithms should be applied to the following three problems:
1. The missionary and cannibal problem:
Three missionaries and three cannibals come to the bank of a river they wish to cross. Three is a boat that will hold only two, and any of the group is able to row. If there are ever more missionaries than cannibals on any side of the river the cannibals will get converted. Devise a series of moves to get all the people across the river with no conversions.
2. The 8-puzzle problem:
The 8-puzzle is a 3 ´ 3 board in which 8 differently numbered tiles and a blank space are fitted into 9 spaces on a grid. Tiles can be moved around in 9 spaces. The goal is to find a series of moves of tiles into the blank space that places the board in a goal configuration. Although in the physical puzzle moves are made by moving tiles, it is much simpler to think in terms of moving the blank space instead. In order to apply a move, we must make sure that it does not move the blank off the board. The legal moves are:
1) Move the blank up
2) Move the blank right
3) Move the blank down
4) Move the blank left
Devise a series of legal moves that change an arbitrarily specified beginning state to the following goal state.
|
1 |
2 |
3 |
|
8 |
|
4 |
|
7 |
6 |
5 |
You can use one of the three heuristics that are discussed in the textbook and course notes.
The sliding-tile puzzle consists of three black tiles, three white tiles, and an empty space in the configuration shown in the figure below.
|
W |
W |
W |
|
B |
B |
B |
The puzzle has two legal moves with associated costs:
1) A tile may move into an adjacent empty location. This has a cost of 1.
2) A tile can hop over one or two other tiles into the empty position. This has a cost equal to the number of tiles jumped over.
The goal is to have all the white tiles to the left of all the black tiles. The position of the blank is not important. Devise a sequence of legal moves to transform an initial state arbitrarily given to the above goal state. Use the heuristics that you proposed in your Assignment 2.