CIT 591 Assignment 5: Sudoku Fall 2007, David Matuszek

# Purposes of this assignment:

• To give you experience with arrays.
• To give you more experience with classes and methods.

# General idea of the assignment:

In Sudoku, you are given a 9x9 grid, divided into nine 3x3 "boxes," as shown on the right. Each box has nine "cells," and some of these cells have digits in them (but most are blank).

The puzzle is to fill in the rest of the grid so that every row, every column, and every 3x3 box contains the digits 1 through 9. Your assignment is to write a program to solve easy Sudoku puzzles.

This image is from http://www.sudoku.com/, which is a very nice site with additional explanations and puzzles (and a Sudoku program for sale).

 Roll your mouse on and off the grid. You may have to wait for the page to load fully

# Details:

Your job is to write a program to solve "easy" Sudoku puzzles. A problem is "easy" if, at all times, there is at least one location in the grid that has all but one of the nine digits occurring in the same row, column, or box.

For example, in the above puzzle, look at the bottom right-hand corner of the middle box in the top row of boxes (that is, row 2, column 5--remember to start counting with zero). The digits 2 and 1 occur in the same row; the digits 1, 3, 4, and 5 occur in the same box; and the digits 4, 5, 7, 1, 6, and 8 occur in the same column. The only missing digit is 9, which must perforce go into this location.

Name your Eclipse project `Sudoku_LastName_FirstInitial`--it doesn't matter whether it's your name or your partner's name that you use for the project, because the other person's name should be in both the Blackboard comments and in an` @author` tag in the main class.

This program could be done in a single class, but in order to give you a little more experience with classes and objects, I'm going to ask for two classes, `SudokuSolver` and `Sudoku`.

## `class SudokuSolver`

The class `SudokuSolver` will have the `main` method. It creates a Sudoku problem to solve (by filling a 9x9 `int` array with numbers), prints the array, asks the `Sudoku` class to solve it, and prints out the solution. All output (and input, if any) should be done in this class.

You can create a suitable array with code such as the following.

 ```int[][] problem = { { 0, 0, 4, 0, 0, 0, 0, 6, 7 }, { 3, 0, 0, 4, 7, 0, 0, 0, 5 }, { 1, 5, 0, 8, 2, 0, 0, 0, 3 }, { 0, 0, 6, 0, 0, 0, 0, 3, 1 }, { 8, 0, 2, 1, 0, 5, 6, 0, 4 }, { 4, 1, 0, 0, 0, 0, 9, 0, 0 }, { 7, 0, 0, 0, 8, 0, 0, 4, 6 }, { 6, 0, 0, 0, 1, 2, 0, 0, 0 }, { 9, 3, 0, 0, 0, 0, 7, 1, 0 } };```

In Java we don't have "true" two-dimensional arrays; this is actually a one-dimensional array of nine locations, where each location contains a one-dimensional array of nine `int` values. Sso, for example,` problem[8] `is an `int` array containing the values 9,3,0,0,0,0,7,1,0, while` problem[8][0] `contains the integer 9.

Your `SudokuSolver` class should also have the following method.

 `void print()` Prints the Sudoku array in the following form, using dots to represent zeros.  ```+-------+-------+-------+ | . . 4 | . . . | . 6 7 | | 3 . . | 4 7 . | . . 5 | | 1 5 . | 8 2 . | . . 3 | +-------+-------+-------+ | . . 6 | . . . | . 3 1 | | 8 . 2 | 1 . 5 | 6 . 4 | | 4 1 . | . . . | 9 . . | +-------+-------+-------+ | 7 . . | . 8 . | . 4 6 | | 6 . . | . 1 2 | . . . | | 9 3 . | . . . | 7 1 . | +-------+-------+-------+```

## `class Sudoku`

The class `Sudoku` will do all the work of solving the problem. It will not print anything.The class `Sudoku` should have at least the following methods. It may have additional private methods if you wish.

 `public Sudoku(int[][] problem)` This constructor takes as its parameter a 9x9 array of numbers representing a Sudoku problem, and saves it in an instance variable. Since this is an `int` array, and an `int` can't be "empty", empty locations in the array will be represented by the number zero. ``` ````public int[][] solve()` Solves this Sudoku problem, and returns the solution. (Notice that, since `solve` is an instance method in the `Sudoku` class, it works with the instance variable that was given a value by the constructor. ``` ````int[][] getBox(int boxRow, int boxColumn)` Returns a 3x3 array representing a "box" of the 9x9 array. The parameters `boxRow` and `boxColumn` are in the range 0 to 2, since there are three rows and three columns of "boxes." ``` boolean occursInRow(int digit, int row)``` Returns true if the given `digit` (which must be 1..9) occurs in the given `row` (rows are 0..8), and false otherwise. ``` boolean occursInColumn(int digit, int column)``` Returns `true` if the given `digit` (which must be 1..9) occurs in the given `column` (columns are 0..8), and `false` otherwise. ``` boolean occursInBox(int digit, int row, int column)``` Returns `true` if the given `digit` (which must be 1..9) occurs in the box containing the location at the given `row` and `column` of the 9x9 array, and `false` otherwise. Note that this method is given a row and column in the complete 9x9 array, but must search for the given digit in the box containing that (`row`, `column`) location. ` boolean occursInBox(int digit, int[][] box)` Returns `true` if the given `digit` (which must be 1..9) occurs in the given 3x3 box, and `false` otherwise. ```boolean isPossibleDigit(int digit, int row, int column)``` Returns `true` if the given `digit` (which must be 1..9) does not occur in the given `row`, or in the given `column`, or in the box containing this `row` and `column`, and `false` otherwise. That is, this digit is a possible candidate for putting in this location; there may be other candidates. ```boolean isOnlyPossibleDigit(int digit, int row, int column)``` Returns `true` if the given `digit` can be put in the given `row` and `column`, and no other digit can be put there; returns `false` otherwise.. ```int getOnlyPossibleDigit(int row, int column)``` If the rules of Sudoku allow only one particular digit to be placed in the given (`row`, `column`) location, return that digit, else return zero.

There is some redundancy in the methods, and you might not use them all in writing the `solve` method. That's OK; write (and test) them all, but use what you need.Use exactly the class names, method names, and method parameters as given--if you don't, our tests will fail, and the methods will be considered incorrect. You can create additional methods, but you must also have the given ones as specified. Any additional methods should also have Javadoc comments.

The DRY principle in programming is: Don't Repeat Yourself. If one method can make use of another method in order to avoid duplicating code, it should do so. Feel free to add any `private` methods you like.

# Programming hint:

When you are debugging a program, it's often useful to put in some additional print statements. However, these print statements will need to be taken out again, in order to "clean up" the program for submission. Here's a better way:

 ```static boolean debugging = true; static void debug(String message) { if (debugging) { System.out.println(message); } }```

Now, instead of saying `System.out.println(message)` for your debugging messages, you can say `debug(message)`. This is a bit shorter, but the important point is that you can "turn off" debugging messages by simply changing the value of the `debugging` variable.

# Due date:

Thursday, October 4, before midnight. Zip up all files and turn in one copy for your team via Blackboard. (See my Instructions for Using Zip Files and Blackboard). Only assignments submitted via Blackboard will be accepted--do not send your program by email. A late penalty of 5 points per day (out of 100 points) will apply.