MP3

Part A - Puzzling the 8

Introduction

In this problem you are going to modify some C++ code that implements the A* search algorithm. The code is available as a zip file. This implementation was inspired by some online implementations (here and here). In addition a tutorial on the A* algorithm is available here.

The Code

The code consists of the following files:
main.cpp Board.h Node.h Utility.h    
constants.h Board.cpp Node.cpp Utility.cpp    
It implements ther A* algoriothm using STL.

The Task

The code currently implements a uniform-cost (breadth-first) search with no heuristic information (h = 0). You are to implement the following heuristic schemes (see the Heuristic function in Node.cpp):

  1. Heuristic search using the heuristic function h = number of tiles that are not in the correct place (not counting the blank).
  2. Heuristic search using the Manhattan heuristic function.
  3. Heuristic search using the heuristic function h = (sum of Manhattan distances) * 2.

A nice discussion on A* heuristics is available here.

Exercise the heuristics on the sample problems available here, and fill out the summary form here.

What You'll Turn In
The completed summary form and a disk with a directory named mp03a containing the code for the heuristic functions you used in your evaluation.

Part B - Scheme Problems

1. Power of Two
Using recursion over natural numbers, define and test a recursive Scheme procedure, (power-of-two power) that takes a natural number (an integer greater than or equal to 0) as its argument and returns the result of raising 2 to the power of that number. For example:

               > (power-of-two 3)
               8
               > (power-of-two 10)
               1024
               > (power-of-two 1)
               2

2. How Many Digits?
Create a Scheme procedure, (number-of-decimal-digits number), that computes the number of digits in the decimal representation of number: For example: 

> (number-of-decimal-digits 10)
2
> (number-of-decimal-digits 12345)
5
> (number-of-decimal-digits 64372967326724896427)
20
>

3. Last?

Define a recursive procedure, last-of-list, a recursive procedure that returns the last element of a list. For example:

> (last-of-list '(1 2 3 4 5))
5
> (last-of-list '((1 2 3 4) 5))
5
> (last-of-list '(1 2 3 4 (5)))
(5)
>

4. Intersection

Define and test a procedure (intersection left right) that takes two lists of symbols as arguments and returns a list of which the elements are precisely those symbols that are elements of both left and right.


	





What You'll Turn In

Add to the disk from Part A a directory named mp03b containing the file:








* based on assignments from here and here.