|
|
| Csc 125 Traditional - Computer Science II, Programming in C++ |
| Project 4 |
| Thursday, November 30, 2006 |
The starting code for Project 4 is in ~sbadman/csc125traditional/project4start on the Parkland Linux machines.
Solving a Sudoku puzzle.
Sudoku puzzles are perfect for
computerization, because the rules are simple and logical, and the state of the
puzzle at any time can be completely contained in a single array of integers or
a string. Also, the algorithm for solution of any given starting state can
be implemented straightforwardly using recursion, or using iteration and a
stack.
Assignment
Use the given code in
~sbadman/csc125traditional/project4start and complete the
SudokuSolver::solve() function to successfully solve any given starting string.
Your code must either find a solution if there is one, or declare the puzzle not
solvable if there is no possible solution.
Requirements
You must use the supplied code as is
and only add to it. You are not allowed to hack or circumvent the
protections on the private data in the SudokuSolverBase class. You are not
given the source code except for the one SudokuSolver::solve() function you must
write. That function is called automatically by the compiled code you are
given.
Your solution must find a solution if there is one. If there are multiple
solutions, your program need only find any one of the solutions. If there
is no solution, your program must say so.
You may either use recursion or use a stack and iteration to implement the solve
function.
Your program must call showCells() with the solution or with a final insolvable
state, and it must state that either the solution was found, or the puzzle is
insolvable.
Your program is not responsible for any bugs in the instructor's code, or with
handling incorrect input or user errors. Please notify the instructor
about any problems.
Your program
should be written on a Linux or Unix system. It will be graded in my
office on your Linux account.
Hints
You will need to use the following command
to compile your code in sudokusolver.cpp with the supplied object files.
Object files are the result of compiling each .cpp file and contain linkable
code that can be combined with additional compiled files. Object code is
designated by dot-oh extensions: .o
g++ sudokusolver.cpp *.o
or
g++ *.cpp *.o
If you want to write additional functions for your implementation, make them
private and add the prototype to the sudokusolver.h file and the function
definition to sudokusolver.cpp The new function will compile
and link with the other .o files.
Look in the sudokusolverbase.h file to see
the public functions you can call. Notice that there are no protected
members in the SudokuSolverBase class. Since you are writing in a derived
SudokuSolver class you will not have access to any of the private data or
functions. Please notify the instructor if there is a missing function
that you think is really necessary.
The algorithm to solve the Sudoku is essentially the same whether you use
recursion or a stack and iteration. Here is the fundamental logic:
save the original given state (by
pushing on the stack, or by calling a recursive function, which acts similar to
a stack)
while any states are left unprocessed (i.e. the stack is not empty or the
recursion has not returned back to the top)
find the first empty cell in the current state.
get the hints for that cell (these are the remaining
possible values that this cell can have without an immediate error)
for every hint for that cell
insert the value of
that hint into the state at this cell's position
if the puzzle is
solved
stop or return, preserving this state
else
save this state (push on the stack, or make a recursive call)
end for
end while
The algorithm above is only the general
logic. You can not just replace it with code and expect it to work as is.
You will need to understand the algorithm, fill in details, and carefully debug
your resulting code.
Start by testing the given public functions to see what they do. Isolate
them by just calling them once on a known given state and see what is returned
by the getter functions, or how that state is changed by the setter functions.
Don't assume you know their behavior and immediately put them into loops.
The given code in int main() tests a number of these functions as illustrations.
You are given three ways to implement your code. You can change the cell's
values directly and work only with the cells. Alternatively you can work
with the state string only. Or you can use the integer array of state
values. You will probably want to stick to one of the three, and not mix
your logic between the three methods. If you change one of them, the other
two should automatically record the change. If not, please let the
instructor know.
Grading
Project
4 is worth
?? points toward the final
grade. It will be graded according to the criteria on the
Project 4 Grading
Criteria.
Date
Your project will be interactively graded on Thursday, November 30th. On Tuesday, November 28th each student will sign up for a specific 15 minute period for grading on the following Tuesday. You may have your project graded before November 30th, if you wish, by making arrangements with the instructor.
| Back to Csc 125 - Computer Science II, Programming in C++ |
| Scott Badman Office: B132 Phone: 353-2250 sbadman@parkland.edu |
Parkland College, 2400 W. Bradley Avenue, Champaign, IL 61821 |