Objectives

• Work through the details of stack, queue, and heap implementations.
• Understand DFS, BFS, and BestFS.
• Solve some fun puzzles!

Overview

Stacks and queues are powerful tools for storing and accessing data. In particular, these data structures are at the heart of two of the most important algorithms in computer science: depth first search (DFS) and breadth first search (BFS). Priority Queues are slightly more complicated and slightly less common, but are also widely used. In our project, they are used to implement the heuristic-based best-first search (BestFS) algorithm.

Searching is an extremely general approach to solving problems. We systematically explore possible solutions until we find one that works. Thanks to the speed of the computer (and efficient algorithms like what you learn in 221!), search is able to solve a wide range of important, practical problems. In this project, we'll develop some reusable code that lets us solve a wide range of puzzles, with only a small amount of coding needed to add a new puzzle type.

Of course, these are all just fun puzzles, but similar approaches have solved problems like route-finding in mapping systems or providing responsive control for space probes too far from Earth for direct control (among many others).

For starters, we are providing you with code to solve the classic Wolf-Goat-Cabbage problem, Sudoku, and the general Slider Puzzle of which the 15-puzzle is the most famous variant. We've also given you a simple maze explorer, to help you visualize the different search algorithms. We may add a few more puzzles if we have time.

(If you are unfamiliar with these puzzles, there are many on-line implementations. Here's one for the sliding puzzles, and one for Sudoku.)

DFS involves following a sequence of moves as far as we can go, until we get stuck. When this occurs, the search backtracks to its most recent choice and tries a different path instead.

BFS proceeds differently: it tries moves in order of their discovery, beginning at the starting point of the search. First it tries all moves available from the starting point, then it tries all moves available starting from where those first moves end, i.e., "two steps away". It continues in the same fashion from there until a solution is found. Because of this, BFS has the nice property that it will discover the shortest path to a solution, in terms of the number of moves taken to reach the solution. (It has the nasty property that it will visit every closer state of the puzzle along the way.)

Best First Search uses a heuristic function, which provides an approximate judgment on the quality of a state. Given this function, it explores from the most promising states that it has found so far. This hopefully helps guide the search to explore possibilities that are more likely to lead to a solution.

The algorithms for DFS, BFS, and BestFS all work very similarly. Each one is based on a different one of the three data structures we discussed above: a stack, a queue, and a priority queue. If we "line up" the operations of these three data structures—push, enqueue, and insert together and pop, dequeue, and deleteMin (or Max) together—and call them abstract "add" and "remove" operations on a set of active states, we can describe all three algorithms at once.

All three algorithms begin by adding the initial puzzle configuration into the active states. Then, until the active state set is empty or a solution is found, they remove a state from the active states. If that configuration has not already been explored (i.e., previously removed from the active states), they find the configuration's children and add each child into the active states.

Note that except in special cases (like Sudoku), we need a second data structure in addition to the todo list. This is a dictionary ADT that keeps track of whether we have previously visited a configuration during our search. If we have, we don't want the algorithm to try to explore it again (this wastes effort and might lead to infinite loops). In addition, for many puzzles, we don't want to see just the solution; we also want to see the sequence of moves that led from the initial configuration to the solution. If we use the dictionary to store for each state the predecessor state from which we arrived at the state, then once we find a solution, we can follow these predecessors backwards and find the sequence of states that led to the solution. Note that this dictionary will be used a LOT during the search, so it should be efficient.

Assignment

For this assignment, you will be implementing the active states ADT as a stack, a queue, and a priority queue. We have provided two implementations of the stack ADT, using an array or a linked list. You must implement the queue ADT using a circular array (and supporting dynamic resizing) as well as using linked lists. You must also implement a priority queue using a binary heap.

You will use your implementations, and some that we have supplied, to experiment with solving a variety of puzzles. In particular, you will test your code by using the supplied solve.cpp program, along with its associated files.

You also must answer some questions in the MILESTONE1.txt and HANDIN.txt files.

Important implementation constraints: In your circular array queue implementation, you must use regular C++ arrays. You may not use std::vector or other classes that directly support resizing. (We want you to learn how to do it yourself!) We have provided a simple, bare-bones linked-list node type and an example of using it in the LinkedListStack implementation. You are free to use this for LinkedListQueue, or you may implement your own linked list structure. You may not use std::list (which is implemented as a linked list) or any other linked list libraries. For the priority queue, you may not use std::priority_queue or any other heap implementations; you must implement your own. However, you are allowed (and strongly encouraged) to use std::vector in your heap implementation to make resizing the heap easy.

Important marking constraints: We will mark your code semi-automatically. Therefore, you must ensure that your code will compile and link correctly by simply running make on the ugrad Linux servers, with our supplied Makefile. Also, your code must respect the supplied interface types, with no modifications.

You are responsible for deallocating any memory that you allocate. (The rule of thumb is: if you create something with new, you should destroy it with delete when you've finished with it. If you used new with brackets to make an array, use delete [] rather than just delete.)

Teams

You may work on a team of at most two on this assignment, subject to the course's Academic Conduct policy, and we strongly encourage that you do so. We recommend that you work (literally) together as much as possible, but you may choose how to divide the work under three conditions: (1) document each team member's effort in the HANDIN.txt file; (2) work together on and both understand your HANDIN.txt; (3) understand how your team member's code is structured and why it works. Remember to test your team's code as an integrated whole! Except in extreme cases, all team members will receive the same grade for the project. Check out All I Need to Know about Pair Programming I Learned in Kindergarten for advice on working in a pair.

What we've provided

As a starting point we've provided some files:

Makefile

The command make will use this to build your program. You should not need to modify the makefile, even if you add new .cpp and .hpp files. DO NOT MISS the following commands: make handin-milestone1 hands in your Milestone #1. Run it early and often so you're not late. make handin-proj1 hands in your final project 1 submission (run early and often). These commands must be executed on our undergrad linux servers, in a directory that contains the relevant MILESTONE1.txt, HANDIN.txt, and various .cpp and .hpp files you wish to hand in.

MILESTONE1.txt, HANDIN.txt

Key documentation files for your milestone and final submissions. Read these and fill in the TODO items! Also, answer the questions there.

solve.cpp

This is the main code that solves the puzzles. You will edit this code to choose what kind of puzzle to solve, set up the initial configuration, and select which search strategy and dictionary implementation to use. Initially, you'll just make a few changes to it to explore the different search algorithms. Later, you'll alter it so it uses your data structures rather than ours.

BagOfPuzzleStates.hpp

This defines the abstract type which your stack, queue, and priority queues must implement. You can look at the provided implementations of the ArrayStack, LinkedListStack, and VectorPriorityQueue to see how to do this. Your queue, and priority queue classes must be subclasses of BagOfPuzzleStates.

Warning: Don't go about inserting logic for depth-first vs. breadth-first search into your code. It's entirely unnecessary. The two searches use the *same* algorithm; the only difference is a different underlying data structure for the active states.

ArrayStack.hpp, ArrayStack.cpp

An implementation of a stack using a (resizable) array. Study it carefully and use it as a guide to implement the rest of your data structures! It will especially be useful for your array-based queue.

Warning: your ensure_capacity for the queue will necessarily look somewhat different from the one in this file!

LinkedListStack.hpp, LinkedListStack.cpp

An implementation of a stack using a linked list. Study it carefully and use it as a guide to implement the rest of your data structures! It will especially be useful for your linked-list queue.A

VectorPriorityQueue.hpp, VectorPriorityQueue.cpp

A naive implementation of a priority queue that scans the list looking for the min on every remove operation. This will be helpful as a guide for implementing your HeapPriorityQueue, and you can also use this to test if your HeapPriorityQueue is working.

PredDict.hpp

This defines the abstract type which the dictionary must implement.

LinkedListDict.hpp, LinkedListDict.cpp

A naive implementation of a dictionary that scans the list for each find operation.

LinkedListQueue.hpp, LinkedListQueue.cpp

Skeleton code for the linked list queue files. Implement it!

ArrayQueue.hpp, ArrayQueue.cpp

Skeleton code for an array-based queue class. Implement it!

HeapPriorityQueue.hpp, HeapPriorityQueue.cpp

Skeleton code for a heap-based priority queue class. Implement it!

PuzzleState.hpp

An abstract class to represent a puzzle configuration.

WolfGoatCabbage.*, Sudoku.*, SliderPuzzle.*, etc.

Code that implements the PuzzleState interface, and lets us solve different puzzles using the same code for the rest of the program.

~cs221/assignments/project1

Copy them all by by changing directory (using the cd command) into your project1 directory and running:

cp -R ~cs221/assignments/project1/* .

Type make in that directory, and then run the solve program. Start playing with solve.cpp.

Outputting a solution

You should use the existing print routines to produce your output or risk losing credit in the automated portion of the marking.

Milestone

This project includes a milestone, due before the final deadline. For this milestone, submit your completed MILESTONE1.txt file, as directed in that file.

Why this milestone? Because in previous terms, foolhardy individuals (like more than one-third of the class) left compiling the code so late that they never got past it. Get past it!

Turn your file in electronically using handin, by running make handin-milestone1 in a directory that contains the relevant files (MILESTONE1.txt).

Final Submission

You are required to hand in your project1 directory with your implementation of the ADTs. Included in this directory should be at least these files:

• LinkedListQueue.{hpp,cpp}, ArrayQueue.{hpp,cpp}, HeapPriorityQueue.{hpp,cpp},
• Your completed HANDIN.txt file

You should not need to hand in changes to any other files in the project.

Turn your files in electronically using handin, by running make handin-proj1.