Description
Checkpoint 1
For the first checkpoint, we will explore the implementation of the ds set class, along with the use of recursive
functions to manipulate binary search trees. Download and examine the files:
http://www.cs.rpi.edu/academics/courses/spring17/ds/labs/10_sets/ds_set.h
http://www.cs.rpi.edu/academics/courses/spring17/ds/labs/10_sets/test_ds_set.cpp
The implementation of find provided in ds_set.h is recursive. Implement and test a non-recursive replacement for this function.
To complete this checkpoint: Show one of the TAs your new code. Be prepared to discuss the running
time for the two different versions of find for various inputs.
Checkpoint 2
The implementation of the copy constructor and the assignment operator is not yet complete because each
depends on a private member function called copy tree, the body of which has not yet been written. Write
copy tree and then test to see if it works by “uncommenting” the appropriate code from the main function.
To complete this checkpoint: Present your solution to one of the TAs.
Checkpoint 3
For the last checkpoint, we will write a simple Sudoku puzzle solver using the STL set container class.
Sudoku puzzles are typically played on a 9×9 grid in which some of the cells have been initialized and many
of the cells left blank. The instructions are simply to: “Fill in the grid so that every row, every column, and
every 3×3 box contains the digits 1 through 9”. If you are unfamiliar with Sudoku puzzles you may read
about them here: http://en.wikipedia.org/wiki/Sudoku
Please download the following files which contain a partial implementation of a Sudoku puzzle solver:
http://www.cs.rpi.edu/academics/courses/spring17/ds/labs/10_sets/sudoku.h
http://www.cs.rpi.edu/academics/courses/spring17/ds/labs/10_sets/sudoku.cpp
http://www.cs.rpi.edu/academics/courses/spring17/ds/labs/10_sets/puzzles.txt
First familiarize yourself with the code and how we will be representing partially solved Sudoku puzzles. The
2D grid is stored using nested vectors. The elements of the inner vector are sets of integers, which represent
the possible values for that cell.
We know we’re done when each cell has exactly one possible value. If in the
course of solving the puzzle we end up with no values in a particular cell, we know the puzzle is impossible
to solve. The program handles 4×4 puzzles with 2×2 blocks and 9×9 puzzles with 3×3 blocks (and even larger
puzzles too!)
Part 1:
Finish the implementation of the Sudoku class constructor and the Sudoku::IsSolved member
function. At this point you should be able to compile and test your program on the input file (using file
re-direction). The provided code for this assignment will print out the contents of each cell in the puzzle. At
this point, every number (1-4 on the small puzzles and 1-9 on the large puzzles) will be an possible value for
each unspecified cell in the puzzle.
Part 2:
In the next step you will propagate information from the values in the grid which are known. For
example if “7” is the only remaining choice for the cell (i, j) then we can remove “7” from all the other cells
on the ith row and the jth column and the corresponding block. Follow the structure in the code provided
and complete the Sudoku::Propagate member function.
Test your program on the provided input.
To complete this checkpoint and the entire lab: Show a TA your completed program. Be prepared to
discuss why it can only solve some of the puzzles. Think about how you would extend the program to solve
some of the more difficult puzzles.
