C++
Puzzle Configurations
NOTE: Project description taken from RIT's CS4 website. So all copyright stuff is theirs, etc etc.
Goal
1. Design
You will improve your design skills while learning many new design techniques and styles.
2. C++ Programming
You will learn what it takes to develop a larger program in the C++ language.
3. C++ Survival
Some of the techniques you learned in more standard object-oriented languages may not apply here. In addition, C++ has some unique features that you may be able to exploit. This project should help expose you to these issues and show you how to make choices you can live with.
Overview
Abstraction as a Means of Extensible Design
Below you will read about some specific problems you are to solve. However, we will also show you how these problems fit into a more general analysis pattern. If you know this, you can design your solution to this more abstract model, thereby allowing you to plug in new concrete problems with less effort.
Here are the three problems you are to solve. We describe in the background section the common characteristics of these problems.
Problem 1: Fixing the Time on Your Clock
Your clock has gone dead because you forgot to wind it or replace the battery, or you had a power outage. This clock has hands, so you must turn them to adjust the time. Which way, and how far, should you turn the hands to fix the time the most quickly? You've probably guessed that this will be the easy one of the bunch. In fact, we'll trivialize it even further. The clock only has an hour hand, so the question becomes how many whole hours backwards or forwards the hour hand must be moved. Then we will "complicate" it a bit by turning it into a general modulo-n counting problem, by saying that the clock displays n hours on its face.
Problem 2: A River Crossing
Several Professors and Students come to a river that they wish to cross using a small boat that can only carry two people at a time. However, because of the fun-loving nature of the students, the professors can never allow themselves to be outnumbered or they will be thrown into the river. How can everyone get across the river without getting wet?
Problem 3: A Sliding Block Puzzle
A shallow box has several different sized wooden rectangular blocks in it. Not all of the space in the box is taken up with the wooden rectangles so it is possible to slide the wooden blocks around if there is enough empty space around a block. The problem is to move a given block to a specified position by sliding all of the blocks around.
Background
A Single Abstraction for these Problems
The problems described in the overview section belong to a class of problems that can be characterized as follows:
- There is some kind of world that can be in one of many configurations. Actions cause the configuration of the world to change in some small and incremental way.
- The set of all possible configurations is not known ahead of time; they must be computed by applying actions and seeing where they take us.
- We are presented with an initial configuration, and asked to bring the system to an acceptable goal configuration.
- The acceptability of a configuration as a goal configuration is testable (often there is more than just one such configuration).
- The solution is then a sequence of actions that propel the world from the initial configuration to one of the goal configurations. It is enough to list a sequence of configurations that lead to a solution configuration.
Mapping the Abstraction
Let's see how the sliding block puzzle maps to this abstraction.
- The world is a box of rectangular blocks. The current configuration of the world is the size, position, and orientation of each block in the box. An action consists of moving one block one unit horizontally or vertically to a new spot in a legal way (no collisions).
- The initial configuration is just the initial setup of all the blocks. The test for an acceptable final configuration would see whether the specified block is at the specified final position.
- We will leave it as an exercise to the student to determine the mappings to the other two problems.
The Algorithm
The interesting thing about these problems is that we do not have to think about the concrete problem instance in order to describe an algorithm to solve it! Read and make sure you understand the algorithm below:
Create an initially empty queue of configurations.
Insert the initial configuration into the queue.
While
the queue is not empty and
the first configuration in the queue does not meet the goal,
loop:
Remove the first configuration from the queue and call it C.
For each action A applicable to C, loop:
Apply A to C, and enqueue the resulting
configuration if it has not already been seen.
end-loop.
end-loop.
The acceptable configuration is now at the head of the queue;
but if the queue is empty, there is no solution to the problem.
THE PROJECT
UML Diagrams (Class Diagram, Sequence Diagram, Use Case)
Download Archive of Code