Project Description
SuDoKu

Overview

For this project you will complete a skeleton C program that presents a sudoku puzzle to a player and provides commands for the player to incrementally solve the puzzle. Here is a tutorial on the rules of sudoku for those who are unfamiliar with the game.

Setup

Download the file sudoku.zip from the software engineering web to a clean working directory for this project. Unzip the file - on linus you can use the command:

unzip sudoku.zip

which will place all the files in the zip archive in the current directory. At this point you can remove sudoku.zip; should you need it later (e.g., for disaster recovery) you can always download it from this page. At this point you should see the following files & directories:

bool.h

A header file declaring a pseudo-type for bool along with constants FALSE and TRUE.

main.c

The main driver function: It parses the command line arguments, initializes the puzzle, loads the puzzle configuration from a file provided as an argument, and, if the load succeeds, reads user commands (one command per input line) and calls the appropriate processing function in the puzzle module.

arguments.h & arguments.c

Interface to and implementation of a module processing the command line arguments to (a) determine whether or not the input commands should be echoed (optional -e flag), and (b) open the puzzle configuration file, which defines the initial state of the puzzle. Exits with appropriate messages if there are problems with the arguments provided.
Note: You need not concern yourself with this module, as it is only used by the main function. On the other hand, perusing it would give you  examples of using some standard C functions and idioms.

puzzle.h & puzzle.c

The puzzle module you will complete. The header, puzzle.h, defines the interface you must adhere to, as the only source file you will submit is the corresponding implementation, puzzle.c. In particular, puzzle.c is the one file you must edit and the only file you may edit.

solve_sudoku & skeleton_sudoku

Two executable files, compiled and linked for Linux. solve_sudoku represents a full, complete implementation of the requirements, including error handling; use it as a reference against which to compare your program as you go along. skeleton_sudoku was compiled directly from the files we provide; all the functions in the puzzle.c file have been stubbed out, and those functions with return values return whatever is required to make it appear that everything proceeds normally. This can be used as a baseline for comparison with your version.

Makefile

A file making it easy to compile the source code and link the object files. To create an executable file named sudoku use the command:

make sudoku

As you add functionality to the puzzle.c implementation, this executable will be used to test your changes. Makefile also has a series of targets to run your program using different valid and erroneous puzzle configurations, as well as command scripts that are error free or seeded with specific types of errors. More on these tests below.

p+s

A directory with (p)uzzle configurations and command (s)cripts for use in testing.

Description.html

This file (in case you are working remotely and can't access the SE web servers).

Track+Reflect.doc

An M/S Word file in which you record your estimate and actual time it took to do each level, along with reflections on why they diverge (if they do) and your perception of the project as a whole.

Note: If you have problems running either solve_sudoku or skeleton_sudoku, this is probably because the files are exectuable. To fix this, run the following command on Linus:

chmod +x solve_sudoku skeleton_sudoku

This will set the e(x)ecute permission on these files, at which point you should be able to run them.

Using the Example Programs

All the examples will be given using solve_sudoku. You can substitute skeleton_sudoku, but the program will look like it did nothing (which, in fact, is what happens in the skeleton). And, of course, as you implement the required functionality, you can use your compiled version, sudoku.

The program is invoked in one of two ways:

./solve_sudoku configfile
./solve_sudoku -e configfile

In both cases, configfile is a text file giving the initial placement of digits in the puzzle. The optional -e flag determines whether or not the user commands are echoed to standard output. If you're running on the console and typing in commands, you should probably not use the flag. On the other hand, if you are running commands from a script (a text file), then -e lets you see what commands are executed in sequence.

Example

./solve_sudoku -e p+s/good_puzzle.txt < p+s/script_good_solve_puzzle.txt

runs the program using a legitimate puzzle configuration in p+s/good_puzzle.txt with echoing turned on and the commands coming from the script file p+s/script_good_solve_puzzle.txt - this script has commands that add digits to the puzzle to solve it. Along the way, the partial puzzle solution is printed at several points.

You could run the puzzle interactively as follows:

./solve_sudoku p+s/good_puzzle.txt

In this case, the main program directs the initialization and loading of the puzzle configuration, prints the initial board, and enters the command loop. Each time through the loop the program prompts command: to which you respond with a single lower-case letter command and possibly digits used by the command. Spacing is important: the command letter must be the first character on the line, and the command and arguments are separated from each other by a single digit; each command is terminated by a newline. The commands are:

p	Print the puzzle
q	Quit (also on end-of-file)
a r c d	Add digit d to the puzzle at row r column c
e r c	Erase the digit at row r column c

Rows, columns, and digits are all in the range 1..9.

Design Notes

Puzzle Configuration File Format

The configuration file comprises a series of 0 or more rows, each row beginning with three digit characters giving the row, column, and value for one of the initial placements in the puzzle. All three digits must be in the range 1..9. For example, the line 135 means 5 is to be placed at row 1, column 3 in the initial configuration.

Puzzle Data Structures

The puzzle implementation is built on two 10x10 matrices: puzzle and fixed. The matrices are 10x10 to permit 1-based indexing into the 9x9 array defining the puzzle proper; the 0th row and column are unused.

The puzzle matrix holds the values placed so far, with 0 representing a blank (available) location or cell. After initialization to all zeros, this matrix is filled in first from the configuration file and then via commands read from standing input. In later stages of the implementation, the program will enforce the Sudoku consistency constraints - a row, column, or 3x3 region may not contain the same value in two cells.

The fixed matrix is a boolean matrix initialized to all FALSE values. When a puzzle is configured (via data in a configuration file), the row and column for each value so placed is set to TRUE in fixed. In later stages of the implementation, attempting to erase a fixed value is an error and the cell is not changed.

Puzzle Module Interface

The public interface has of an enumeration, op_result, which is used to report back the status of each add or erase command. OP_OK signals success; the other values in the enumeration reflect the different errors that may be detected. OP_BADARGS means the command gave a row, column, or digit that was not in the range 1..9, OP_OCCUPIED is for attempts to place something at a location with an existing value, OP_ILLEGAL is for placements that would violate the Sudoku rules (a duplicate value in a row, column, or region), OP_EMPTY is for attempts to erase an empty cell, and OP_FIXED is for attempts to erase a fixed cell (one set by the puzzle configuration). Only OP_OK results in a change to the puzzle layout; all erroneous commands have no effect.

The interface proper is defined by five visible functions:

init_puzzle( )	Initialize the puzzle and fixed matrices.
configure( pf )	Read configuration lines from the file whose handle is pf and use this to fill out the puzzle and fixed matrices. If any configuration errors are encountered, this function prints a message and exits - thus a return from this function represents successful configuration.
print_puzzle( )	Print the puzzle - The first line is 25 dashes (-). - A line of 25 dashes is also printed after the 3rd, 6th, and 9th row of the puzzle. - Each puzzle row begins with a vertical bar (|) - Each cell in the row is printed as a space and the cell's value (space for a 0 value). - After the 3rd, 6th, and 9th colum, a space and a vertical bar are printed.
add_digit( r, c, d )	Add digit d to the puzzle cell at row r, column c, returning success or error status.
erase_digit( r, c )	Erase the puzzle cell at row r, column c, returning success or error status.

Puzzle Module Internal (static) Functions

The puzzle module also declares and defines a set of utility functions to aid in implementing the interface. As these are internal to the module, you are not required to use them - you can arugment or replace them with other functions of your own design (replacement requires complete eradication of all traces of the replaced functions).

Note (if you use your own ideas):

• You are still responsible for providing all the specified interface behavior for each level of functionality, and
• Your code must still adhere to high qualities of structure, naming, documentaition, and partitioning. Long, convoluted, poorly indented or inadequately documented code will cost you dearly in terms of quality.

Tasks & Deliverables

The project is organized as a sequence of six functionality levels. Each level requires you to extend the work done at the previous level. For each level 1 through 6 you will fill out the associated estimating, tracking, and reflection activity outlined in the file Track+Reflect.doc. 15% of your project grade rides on your attention to the details of estimating the time it will take you to complete the activity, track that time and accurately record it when the level is done, and provide thoughtful reflection on the work you did. Some levels are relatively straightforward and require less in the way of reflection. Still, if you have little in the way of thoughtful reflection for any of the activities and the overall summary, expect to be docked heavily.

Similarly, 15% of your grade is based on the quality of your implementation. Aspects considered include:

• Naming: Are variable, function and other names meaningful? Do they have a clear relation to their role in the computation? Would a competent developer be able to pick up this code and understand why you chose the names you did?
• Documentation: Do you use comments to simply repeat the code or to provide insight into its context and intention? Are comments, clear, concise, and correct? Are comments readable - do they avoid distracting grammatical and spelling errors? Are the aligned with the code to make it obvious which comments refer to which sections of code?
• Structure: Are the bodies of functions organized into clear, coherent sets of statements that clearly contribute to the function's goals? As appropriate, are sections of code factored out into local functions of their own, either to simplify the original function, to enhance readability, or to adhere to DRY (Don't Repeat Yourself)?
• Style: Does the layout of the code enhance its readability? Do you use consistent indentation in line with examples done in class? Do you use blank lines to separate distinct blocks of code? Do you use spaces to enhance readability (or are expressions scrunched together, making it difficult to distinguish variables from operators from constants)?
• Source Code Control: Did you demonstrate appropriate us of source code management during the development of the project? Did you provide svn comments for each commit of an update file? Is your test code under source control?

Level 0 (Compiles & Links)

This is a pseudo level, in that all your puzzle.c must do is compile and link against the rest of the program, and your Track+Reflect.doc must contain a reflection on whatever you did. As these conditions can be met by simply submitting the puzzle.c skeleton in the zip file and almost anything for thetracking and reflection, this is really a test of whether you can submit to myCourses.

Level 1 (Puzzle Module Initialization and Printing of an Empty Puzzle)

Fill in the body of the init_puzzle() function and write the print_puzzle() function. Skeletons for two static methods related to printing are there for your completion and use: print_dashes() and print_row(row). When your modifications compile and link, test them using make:

make test_l1

Level 2 (Initialization, Configuration and Printing of a Real Puzzle)

Fill in the body of the configure(puzzle_file) function, ignoring any error conditions for now. This requires you to

• Read three digit characters and a newline from the file whose handle is the argument (see the Puzzle Configuration File Format section).
• Convert each digit character to the number it represents,
• Place the value in the puzzle cell designated by the row and column, and finally,
• Mark the selected cell as fixed.

When your modifications compile and link, test them using make:

make test_l2

Level 3 (Add and Erase Commands)

Fill in the bodies of add_digit(row, col, digit) and erase_digit(row, col), ignoring any error conditions for now.

When your modifications compile and link, test them using make:

make test_l3

This runs three tests: one a simple test of adding, one a simple test of erasing, and one which solves a real puzzle - the last printout shows a completed puzzle.

Level 4 (Syntax and Simple Add/Erase Errors)

Change the configure function:

1. Discard everything after the three digit characters up to and including the next newline or EOF.
2. Check to ensure they are all digit characters in the range '1' through '9'; if any are not in range, print the message:
   Illegal format in configuration file at line N, where N is the line number, and call exit(1).
   You may find it useful to complete the skeleton helper function in_range(value).
3. Ensure that the cell at the selected row and column is not already filled with a value; if it is, print the message:
   Illegal placement in configuration file at line N, where, once again, N is the line number, and call exit(1).

Change the add_digit function:

1. If any of the three arguments is not in the range 1 .. 9, return OP_BADARGS without changing the puzzle. You may find the helper function in_range(value) useful.
2. If the selected cell already has a value in it (i.e., it is non-zero), return OP_OCCUPIED without changing the puzzle.

Change the erase_digit function:

1. If either of the two arguments is not in the range 1 .. 9, return OP_BADARGS without changing the puzzle.You may find the helper function in_range(value) useful.
2. If the selected cell is already empty (i.e., its value is 0), return OP_EMPTY without changing the puzzle.
3. If the selected cell is fixed (non-eraseable), return OP_FIXED without changing the puzzle.

When your modifications compile and link, test them using make:

make test_l4

This runs a series of tests, the first few with different combinations of bad configuration files, and a last one with a valid puzzle but bad (a)dd and (e)rase commands.

Level 5 (Row and Column Rule Violations)

Change the configure function:

1. Check to ensure that the value being placed in the puzzle is not already in the row or column specified. If it would be a duplicate, print the message:
   Illegal placement in configuration file at line N, where N is the line number, and call exit(1) - you may want to add this check onto the previous one that produces this message. You may find it useful to complete the skeleton helper functions row_contains(row, digit) and col_contains(col, digit).

Change the add_digit function:

1. Check to ensure that the value being added in the puzzle is not already in the row or column specified. If it would be a duplicate, return OP_ILLEGAL without changing the puzzle.
   You may find the helper functions row_contains(row, digit) and col_contains(col, digit) useful.

When your modifications compile and link, test them using make:

make test_l5

This runs a series of tests, the first few with different combinations of bad configuration files, and a last one with a valid puzzle but bad (a)dd commands.

Level 6 (Region Rule Violations)

Change the configure function:

1. Check to ensure that the value being placed in the puzzle is not already in the region specified. If it would be a duplicate, print the message:
   Illegal placement in configuration file at line N, where N is the line number, and call exit(1) - you may want to add this check onto the previous one that produces this message. You may find it useful to complete the skeleton helper function region_contains(row, col, digit).

Change the add_digit function:

1. Check to ensure that the value being added in the puzzle is not already in the region specified. If it would be a duplicate, return OP_ILLEGAL without changing the puzzle.
   You may find the helper function region_contains(row, col, digit) useful.

When your modifications compile and link, test them using make:

make test_l6

This runs a series of tests, the first few with different combinations of bad configuration files, and a last one with a valid puzzle but bad (a)dd commands.

Assessment

Level 0 (puzzle.c compiles and links)	10
Level 1 (initialize and print empty puzzle)	10
Level 2 (initialize, configure and print a real puzzle)	15
Level 3 (add, erase and solve a real puzzle)	15
Level 4 (detect bad syntax and simple add / erase errors)	5
Level 5 (detect adding duplicate values in row or column)	5
Level 6 (detect adding duplicate values in a region)	10
Estimation, tracking, analysis and reflection	15
Implementation quality, source control	15

Submission

As you complete the tasks for each level and your program passes the associated tests, submit a zip file containing:

svn repository (zipped)
puzzle.c
Track+Reflect.doc

Submissions made by the deadline shown on the course schedule will be deposited in the Project 1 dropbox. Submissions may be deposited in the Project-1-late dropbox up to 24 hours late with a 15% penalty. No submissions are accepted after 24 hours from the due date.

You may submit as many times as you like - we suggest at least once per level, with Track+Reflect.doc incorporating the work up through that level. We will only evaluate the last submission you make, and myCourses records everything you submit, so there is no risk associated with making many submissions.

CAVEAT:  We assume that you, as a matter of course, check each submission to ensure it was properly uploaded and recorded. Thus we will not be swayed by statements like "I submitted it and don't know what happened."