University of Virginia, Department of Computer Science
CS201J: Engineering Software, Fall 2003

Problem Set 4:
Designing with Data Abstractions
Out: 26 September 2003
Design Document Due: Thursday, 2 October (beginning of class, two copies)
Final Due: Tuesday, 16 October (beginning of class)

Collaboration Policy - Read Carefully

For this problem set, you are required to work in an assigned team as shown below. Unlike other assignments, your group should strive to divide the work in such a way that you can work independently on different parts, and combine your work to solve the problem. In your design document, you will document each member's role.

Abul Kalan ak4f
Kian Keyvanfar kk9t
William Ingram wai9z
Anna Capetanakis ac6cd
Irina Golub ErinGolub
Tuan Vu tv7z
Nancy Fechnay nlf6b
Christopher Cutrona csc5r
Hyun Jong Hong hjh9d
Sam Baumgardner scb7b
Stephen Guy sjg5m
Dan Laufer dl9h
Debora Wesner dtw4e
Craig Pratsch cp9x
Guy-Robert Duval gd4b
Laura Paulsen lep4f
Patrick Rooney pjr2y
Ryan Eagan rme3d
Brian Annes baa2j
James Layman layman
Yohan Kim yk7e
Christine Pearce cep6z
Jacosta Silvers jas4xj
Steven Li ssl5b
Danielle Fallon df8m
Hope Tuck ht8a
Raquel Johnathan rdj2f
Donald Conner dec3s
James Kulina jk2af
Neil Guha png4v
Doug Stewart dds9e
Jasjeev Sawhney jss8b
Patrick Johnston pnj9t
Elizabeth Verell ekv4r
Jimmy Benani jcb7y
Nitin Chandra nitin
Eric Kobe ek4t
Joseph Burns jcb7j
Marija Cvijetic mc6sb
Melissa Thomason mbt3w
Frank Gilmore ross
Heather McGinness ham5c
Landon Shoop lhs8v
Marshall (Beau) Ordemann beau
Amin Mehr am3cf
Isabelle Estripeaut ie2g
Benjamin Hoover bnh3x
Deniz Kustu kustu
Kevin David kevin.davis
Chad Gallagher cjg5f
Thomas Kuklinski tk4m
Nicholas Kristoff nmk7f
Lauren Foster lef3v
Ryan Tiffany rt7m
Michael Packer Jr. mwp5c
Karen Yeung kly2b
Atul Khosla atulk
Julia Lancaster jal8x
Raul Maynigo rmm3g
Cemi Almazlinos ca9d
Reading: Chapter 13 (except Section 13.11, we won't cover Data Models).


In Problem Set 3, you implemented a data abstraction given a specification. In this assignment, you will design and implement several data abstractions to solve a complex problem. It is up to you to decide what those data abstractions are.


The Cracker Barrel peg game is a one-player game played on a board containing fifteen holes. The game begins with one hole empty and the other holes filled with pegs. The goal is to remove all but one of the pegs by jumping pegs over one another. A peg may jump over an adjacent peg only when there is a free hole on the other side of the peg. The jumped peg is removed.

As anyone who has ever attempted to solve the peg game can appreciate, it is difficult to win. For this assignment, you will develop a program that takes as input a position on a peg board, and produces as output a sequence of jumps that wins the game (leaves a single peg), if such a sequence is possible, or a message indicating that there is no winning sequence.

Your program should take one parameter that is the name of a file containing an initial board configuration. The first line in the file contains a number n that indicates the number of rows on the peg board. The remainder of the file contains n lines. Each character is one of:

For example, the standard Cracker Barrel peg board initial configuration with the top peg missing is represented by:

   * *
  * * *
 * * * *
* * * * *
Spaces in the input are ignored. We use spaces to make the board above appear as a triangle, but the input file below is equivalent:
Your program may reject input files that are not in the shape of a triangle. If the input file format is incorrect, your program should print a helpful error message and exit. Note that the format is incorrect if the number in the first line does not match the number of rows in the file.

Otherwise, your program should either output a winning sequence of jumps if one exists, or a message indicating that there are no winning sequences.

A solution to a peg board puzzle is a sequence of jumps that leaves a single peg on the board. We can describe a solution by numbering the squares on the board starting from the top. For the example above, the squares are:

       2   3 
     4   5   6 
   7   8   9  10 
11  12  13  14  15
Your program should print out one of the winning sequences by printing out each jump as the position of the peg that starts the jump, and the landing position.

For example, is the input is:

   * *
  * * *
Your program should output
No winning sequences
If the input is,
   * *
  * o o
your program should output
There may be several possible winning solutions for a given initial configuration. Your program may output any legal solution. If there is no possible solution, your program should output a message indicating that there is no winning solution.


One way of solving a peg board puzzle is to try all possible legal jumps, and then try all possible legal jumps on the resulting boards.

Starting with the example board, there are two possible legal jumps:

  1. The peg in position 4 jumps over the peg in position 2, landing in position 1.
  2. The peg in position 6 jumps over the peg in position 3, landing in position 1.
After choice 1, the board would look like this:
   o *
  o * *
 * * * *
* * * * *
Now, we have three possible jumps:
  1. 11 jump 7 into 4
  2. 6 jump 5 into 4
  3. 13 jump 8 into 4
If we recursively try solving each board that results, some choices will lead to winning positions. Searching all possible boards and moves until a winning position is found, or all possibilities have been exhausted without finding a winner.

Design Document

A design document is due on Thursday, 2 October. You should bring two copies of your document to class on 2 October.

It should contain:

Final Report

On Tuesday, 16 October turn in a final report containing:

Credits: This problem set was developed for UVA CS 2001J Fall 2003. We used a version of the Peg Board game for an excercise in CS200 Spring 2003. You can learn more about the Peg Board game from

CS201J University of Virginia
Department of Computer Science
CS 201J: Engineering Software
Sponsored by the
National Science Foundation