CMSC 201 Programming Project Two Sudoku Out: Wednesday 10/04/06 Due: Before Midnight, Wednesday 10/18/06 The design document for this project, design2.txt , is due: Before Midnight, Wednesday 10/11/06

The Objective

The objective of this assignment is to give you practice with project and function design. It will also give you an opportunity to work with two-dimensional arrays and passing arrays to functions for manipulation. It will give you more practice with separate compilation and reusing modules.

The Background

This project is based on the puzzles called Sudoku. Those of you who are not familiar with this kind of puzzle can read more about it at Wikipedia's Sudoku page

The puzzle forms a grid that is 9 rows high by 9 columns wide. It is composed of 9 sub-grids. Each of the numbers 1 through 9 will exist once and only once in each row, each column, and each sub-grid of the solution.

There is only one correct solution for each puzzle.

Here is the puzzle found in the data file, puzzle1.dat, as it is to be shown to the player:

The Task

The Specifications

• The puzzle must be implemented as a two-dimensional array of ints of size 9 X 9.
• You must use three of these arrays: the original puzzle, the puzzle that you've added values to (a work in progress), and the solution.
  • The values that fill the original array and the solution array will be read into them for you when you call the function, LoadPuzzle(), that has been written for you.
  • In order to use this function, you'll need to get a copy of loadPuzzle.o and loadPuzzle.h from my directory. Change into your directory for project 2 and issue the following command:

    cp /afs/umbc.edu/users/s/b/sbogar1/pub/loadPuzzle.* .

  • You'll also need a couple of data files, so copy them too.
    

    cp /afs/umbc.edu/users/s/b/sbogar1/pub/puzzle?.dat .

  • loadPuzzle.h contains the prototype for the function, LoadPuzzle(), and also has the following constants defined: #define ROWS 9 #define COLS 9 The prototype looks like: void LoadPuzzle(int original[ROWS][COLS], int solution[ROWS][COLS], int rows, int cols);
  • Just #include "loadPuzzle.h" immediately following your library header file inclusions and before your "sudoku.h", which will need to know them.
    Explanation: All of the files that use the two-dimensional arrays will need to know the values of ROW and COL. As a matter of fact, even the function prototype for the function LoadPuzzle() needs to know the values of ROW and COL. Since the functions you are defining in sudoku.c, have their prototypes in the file suduko.h and most of those functions use a 2-d array as one of their parameters, it is imperative that the values of ROW and COL be known before the compiler see the function prototypes in sudoku.h. So the #include of "loadPuzzle.h" needs to come before #include "sudoku.h"
  • Your program will need to call the LoadPuzzle() function and pass it the original and solution arrays and their size: rows and cols, as you see from its function prototype.
  • Your program will also need to make a copy of the original to have an array, probably called puzzle, that the player is allowed to write values into. You will need to keep original unmodified. This copying should be done in a function, so you MUST have a function called CopyPuzzle() that has the following function prototype:

    void CopyPuzzle(int source[ROWS][COLS], int target[ROWS][COLS], int rows, int cols);

• You are to use a menu to direct the activity of working the puzzle with the following options:
  1. Start / Start Over - The player is presented with the original puzzle, before any modifications were made.
  2. Play - The player is presented with the current state of the puzzle, with the modifications s/he has made. The user is then allowed to enter positions and values, can erase cells that s/he has modified, or can return to the menu.
  3. Check Answer - The current state of the puzzle is compared, cell by cell, to the given solution. The user is shown the solution and is informed of the outcome: Congratulations or You Lose. Checking your answer does NOT change the current state of the puzzle. This makes it easier to cheat ;) - Analogous to looking at the answers in the back of the puzzle book.
  4. New Puzzle - Allows the player to get a new puzzle from a file.
  5. Quit

More Details

• Grid numbering columns 0 1 2 3 4 5 6 7 8 |==============================================================| 0 | : : | : : | : : | |--------------------------------------------------------------| 1 | Sub-grid:# 1 | Sub-grid:# 2 | Sub-grid:#3 | |--------------------------------------------------------------| 2 | : : | : : | : : | |==============================================================| 3 | : : | : : | : : | r |--------------------------------------------------------------| o 4 | Sub-grid:# 4 | Sub-grid:# 5 | Sub-grid:# 6 | w |--------------------------------------------------------------| s 5 | : : | : : | : : | |==============================================================| 6 | : : | : : | : : | |--------------------------------------------------------------| 7 | Sub-grid:# 7 | Sub-grid:# 8 | Sub-grid:# 9 | |--------------------------------------------------------------| 8 | : : | : : | : : | |==============================================================| where puzzle[0][0], puzzle[0][1], puzzle[0][2], puzzle[1][0], puzzle[1][1], puzzle[1][2], puzzle[2][0], puzzle[2][1] and puzzle[2][2] are the cells of sub-grid # 1, etc.
• During play, the user is prompted to enter a row number OR -1 to return to the menu
• If the user entered a row number, s/he is prompted for a column, and then the value to write into that location. The user can erase a value that s/he previously entered by entering a 0 for the value.
• Your program should not allow the user to make an illegal move.
  • Values written into the cells of the puzzle can be only 0 - 9, if the value is a 0, then you should display 6 spaces.
  • Reject a value if that value already exists in that row, col, or sub-grid.
  • Don't allow the user to erase or change a value that was in the original puzzle.
  • Make sure all inputs are in the correct range of values.

Sample Run

This is the sample run.

Although your output need not be identical to that in the output file, all information (including a greeting and instructions that are not shown in the output) must be present.

Please be aware that this may NOT be a complete test of the program.

Extra Credit

As always, you may also earn extra credit points on any project by having outstanding documentation (exceeding 201 standards), an extremely clever or efficient algorithm, or a well-conceived, general, flexible design. These 1 - 10 points of extra credit are awarded at the discretion of the grader.

Submitting the Program

To submit your project, type the following at the Unix prompt. Note that the project name starts with uppercase 'P'.

submit cs201 Proj2 proj2.c sudoku.c sudoku.h util.c util.h

To verify that your project was submitted, you can execute the following command at the Unix prompt. It will show all files that you submitted in a format similar to the Unix 'ls' command.

submitls cs201 Proj2