TITLE

IDENTIFYING A SUDOKU SOLUTION

INTRODUCTION

A Sudoku puzzle is a 9x9 grid in which some---usually around 28 or 30---of the cells are filled with integers in the range of 1 to 9; the other cells are empty. A region of the puzzle is one of the nine 3x3 non-overlapping squares of cells within the grid. No integer is duplicated within any row, column, or region, and the puzzle's goal is to fill the remaining cells with integers from 1 to 9 so that this non-duplication property is maintained. Here is a typical Sudoku puzzle and its solution:

		4		2	1
	8				7			1
2			3		5
	1	9				8		3
	7		8		9		4
3		8				7	9
			5		2			4
9			1				8
			9	6		5

7	9	4	6	2	1	3	5	8
5	8	3	4	9	7	2	6	1
2	6	1	3	8	5	4	7	9
4	1	9	7	5	6	8	2	3
6	7	2	8	3	9	1	4	5
3	5	8	2	1	4	7	9	6
8	3	6	5	7	2	9	1	4
9	2	5	1	4	3	6	8	7
1	4	7	9	6	8	5	3	2

DESCRIPTION

In this project, you are to design, implement, document, and test a C++ program that reads a 9x9 matrix of integers from a data file and reports whether or not the matrix satisfies the requirements of Sudoku; that is, whether or not any value is duplicated in any row, column, or region in the matrix. Note that the program will NOT solve a Sudoku puzzle, only test whether a matrix satisfies the puzzle's requirements.

INPUT

The program will read the name of a data file from the terminal and the elements of a 9x9 matrix from the named file. A data file might look like this:

 7 9 4 6 2 1 3 5 8 5 8 3 4 9 7 2 6 1 2 6 1 3 8 5 4 7 9 4 1 9 7 5 6 8 2 3 6 7 2 8 3 9 1 4 5 3 5 8 2 1 4 7 9 6 8 3 6 5 7 2 9 1 4 9 2 5 1 4 3 6 8 7 1 4 7 9 6 8 5 3 2 

OUTPUT

The program will prompt for the name of the input file and write to the terminal the matrix being tested and whether or not it is a Sudoku solution; that is, whether or not there are any dpulicated values in any of the matrix's rows, columns, or regions. The program will write all output to the terminal.

ERRORS

The program may assume the input is as described; it need not detect any errors.

EXAMPLE

Two runs of the program might look like this:

 csh> sudoku Enter input file name: m1.dat The matrix 7 9 4 6 2 1 3 5 8 5 8 3 4 9 7 2 6 1 2 6 1 3 8 5 4 7 9 4 1 9 7 5 6 8 2 3 6 7 2 8 3 9 1 4 5 3 5 8 2 1 4 7 9 6 8 3 6 5 7 2 9 1 4 9 2 5 1 4 3 6 8 7 1 4 7 9 6 8 5 3 2 is a Sudoku solution. csh> sudoku Enter input file name: m2.dat The matrix 1 9 4 6 2 1 3 5 8 5 8 3 4 9 7 2 6 1 2 6 1 3 8 5 4 7 9 4 1 9 7 5 6 8 2 3 6 7 2 8 3 9 1 4 5 3 5 8 2 1 4 7 9 6 8 3 6 5 7 2 9 1 4 9 2 5 1 4 3 6 8 7 1 4 7 9 6 8 5 3 2 is NOT a Sudoku solution. 

OTHER REQUIREMENTS

Represent the candidate matrix in a two-dimensional array. Use functions to (1) open the input file; (2) read the matrix in; (3) test if the rows, columns, and regions of the matrix contain duplicate values; and (4) write out a matrix.

HINTS

The functions that test the rows, columns, and regions will all return boolean values. In each, a one-dimensional frequency matrix will likely be useful.

Pass the coordinates of each region's upper left corner to the function that tests if a region contains duplicates.

AN EXTENSION

Consider extending your program to report how an array that is not a solution fails.

HAND IN

See About Programming Assignments for a description of what to hand in: design document, user document, code, tests, and summary.

What to Hand In

For each programming project, turn in the following five parts. The links here connect to the parts of a small example project. Its program carries out a simple text-formatting task. The program also illustrates opening files for input and output and reading from and writing to them. The five parts of a project are:

1. A design document that describes the design of the program: what it does and how it does it. This document should be typed or word-processed. It must begin with a description of the problem and should provide enough detail about the program you have written to solve the problem that a reader, seeing nothing more than the design document, could substantially reproduce your program. Be sure not to plagiarize the project handouts.

2. Listings of the code for all the program's files. The code should be formatted for good readability and should include the usual comments, including an introductory comment that summarizes the program's purpose and design and includes the author's name, the course and section numbers, and the date the project is due. Each function's comments must include pre- and post-conditions: what must be true of the values going in, and what the calling code can expect to be true of the values coming back, assuming that the precondition is satisfied.

3. A user document that describes how to use the program. This document should be typed or word-processed. Include an example of how to run the program, and be sure to describe any requirements that input data must satisfy. Should the grader run your program, he or she will consult this document for directions; if they are not correct, neither is the document. Note that a user should not be told anything about how the program is implemented.

4. At least three tests showing that the program does what it is supposed to do. You will design your own test data. On the printout, annotate each data file and test to describe what feature(s) of the program the run is testing. Be sure to exercise each line and feature of the program.

5. A summary of what you learned from the assignment, how your solution to the problem might be extended or improved, and answers to any questions posed on the project page. This, too, should be typed or word-processed.

Three of these five parts are about the program, but are not the program itself or tests of it. This is intentional, and the grading of programming projects will reflect it. Designing and documenting programs are essential skills in computing, and we will pay attention to developing those skills.

More generally, it is essential to be able to communicate effectively in writing. Here, that communication is about problems and the programs that implement solutions to them. There are many resources that you can use to improve your writing. Among them, the Write Place on campus here offers both on-line and in-person help.

Grading

Programming projects will be evaluated using a 50-point scale, with the points allocated to the five parts of a project in this way:

Design document	15
Code	15
User document	5
Tests	10
Summary	5