CIT 591 Assignment 5: Sudoku Fall 2005, David Matuszek

# Purposes of this assignment:

• To give you more experience with JUnit.
• To get you started with two-dimensional arrays.

# General idea of the assignment:

Recently, a new form of puzzle, Sudoku, has appeared on the scene. You are given a 9x9 grid, divided into nine 3x3 "boxes," as shown on the right. Some of these boxes have digits in them.

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 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.

Write a class `SudokuSolver` with at least the following methods, and a JUnit test method (at least one) for each one except the last:

 `public void solve(int[][] problem)` Given a 9x9 array of numbers representing a Sudoku problem, solve the problem. 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. ``` ``` `void setArray(int[][] someArray)` Your `SudokuSolver` class should have a `private` instance variable to hold the array. This method just sets that instance variable to the given array. (You don't need to copy the array, just assign it.) You will need this method in your JUnit test class, to give `SudokuSolver` a particular array. ``` ``` `int[][] getArray()` Returns a reference to the (`private`) 9x9 array that holds the puzzle to be solved. ``` ``` `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. `void displayArray()` Prints the Sudoku array in the following form, using dots to represent zeros: ```------------------------- . 6 . 1 . 4 . 5 . . 8 3 . 5 6 . . 2 . . . . . . . 1 8 . . 4 . 7 . . 6 . . 6 . . . 3 . . 7 . . 9 . 1 . . 4 5 . . . . . . . 2 . . 7 2 . 6 9 . . . 4 . 5 . 8 . 7 . -------------------------```

As before, I recommend that you start by writing the JUnit test methods. All of the above methods have "package" visibility except solve, which I've made public. That's fine--it's only the private methods that you can't test with JUnit. Don't write a JUnit test for `displayArray`.

Clearly, `solve` is the "top-level" method here. You will also need a `main` method (not to be tested) that simply gets a problem to be solved, prints it, solves it, and prints the solution. Here is an``` int[][] getProblem()``` method you can use; I will post a better one on the class web site (as soon as I get it working!):

 `public int[][] getProblem() { 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 } }; return problem;}`

There is some redundancy in the methods, and you might not use them all in writing the `solve` method. That's OK; test them all, but use what you need.

Remember the DRY principle, and 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.

# Due date:

Thursday, October 13, before midnight. Zip up all files and turn in one copy for your team via Blackboard.