Parkland College 2400 West Bradley Avenue, Champaign, Illinois 61821

Csc 123 - Computer Science I, Programming in Java

Project 3

Wednesday, November 15, 2006

A Sudoku Solver (well a Sudoku Helper, at least)

Background

Sudoku is a puzzle that has gained a lot of popularity in the last few years.  It is solved with pure logic, and has simple data, the digits from 1 to 9, and simple rules.  This makes it a good puzzle to computerize. You can find the rules and a good implementation to practice at the Washington Post's Sudoku site: http://www.uclick.com/client/wpc/wpdoc/  Be sure to check out the Options button and turn on the Hints.  You will be calculating the hints to help the user solve a Sudoku puzzle.

Assignment

Using the supplied SudokuSolver Java application, write the necessary code in the   calculateHints   function in class HintCalculator to implement correct hints for the user.  The function  calculateHints   will be called for a specific Cell.  You should program the function from the point of view of that Cell only.  The SudokuSolver will call your function for every cell, but don't set the hints in any other Cell but the single Cell for this specific call.   Your hints must check for the following conditions:

1. All other values set in the row of the Cell must not be included in the hints.
2. All other values set in the column of the Cell must not be included in the hints.
3. All other values set in the 3x3 box containing the Cell must not be included in the hints.

>>>> Note: this fourth requirement is not applicable to Fall 2006.  Scott: use this in the future!
4. If any other Cell in the same column, row, or box if this Cell has the same value as this Cell's then both Cell's setError(true) functions must be called.  This will display a red box around the Cells.  

If your hints are correct, most Sudoku puzzles can be solved by repeated hitting the Singles button, with only a few additional choices made by the user.  A correct Sudoku puzzle, such as those in the Washington Post website above, must be solvable by using your hints, without misleading the user in any way.

Advice

Set the hints for that Cell only.  Don't change the hints in any other cell because you will find that the cells will interfere with each other and give an incorrect result.  The current cells's row, column, and boolean hints array are passed as parameters.   Also, you will get a reference to the entire 9 x 9 two-dimensional Cells array, so you can request information for the other Cells, and set their Error variable if necessary.

Explanation of the parameters passed to calculateHints, and therefore are useable by your code in that function:

int row and int column -- These specify the location of the Cell you are processing in the 9 x 9 Cells array.  These are index numbers, so they go from 0 to 8, not from 1 to 9.

boolean[ ] hints -- This is an array of 9 boolean values, numbered with the index numbers 0 to 8.  They correspond to the values 1 to 9 when displayed on the screen, so you always must use an index number one less than the value you want to display.  hints[3] controls the number 4, for example.  Since a value of zero in a Cell means an empty square, you can never try to display 0 as a hint.  You will get a run-time ArrayOutOfBoundsException if you try to access hints[-1], mistakenly trying to control 0 as a hint.  You should set all 9 of the booleans in the array to true, at the beginning of your calculateHints code, and then turn off specific hint values when you find they are not valid.  For instance if you find that the value of 9 is already used by another Cell in your Cell's row, then you would write

hints[value - 1] = false;

to remove value, which in this example is 9, from the hints display for that cell.

Cell[][] cells -- This is the 9 x 9 array of Cells that is displayed on the screen.  The important public functions that you can use are listed below.  Be careful and only get information from the other Cells, except for the setError function.  You can change some other of their variables using setter functions, but you will probably only introduce errors into the program, resulting in an incorrect solution.

boolean fullHints -- This boolean is true if the user has set "Full Hints" in the pull down menu, and false if the user has chosen "Basic Hints".  Use this parameter only if you want to go beyond the required hints listed above.  Anything beyond the required hints should be put in an  if(fullHints) { }   statement, so that they can be turned off.  Your project will be graded using the Basic Hints only.

Here are the useful public functions of Cell that you can use to get the information you need to make decisions.  You can call these functions on any cell in the 9 x 9 array of cells passed as a parameter.

public int getValue()  // will always return 0 through 9. 0 means an empty cell.
public void setError(boolean b)  // turns the red error box in the cell on and off
public boolean[] getHints()  // use this function to read the hints in another cell.
                             // changing these hints will not change the other cell's hints
                             // you can only change the hints sent as a parameter, which
                             //   are the hints for the current cell only
public int getHintCount()  // how many hints are currently set true in the cell

Requirements

Your program must be an implementation of the supplied SudokuSolver Java Application, solely by implementing the

public static void calculateHints(int column, int row, boolean[] hints, Cell[][] cells, boolean fullHints)
.
in class HintCalculator.  You can not change any other code in the application.  (If you think there is a problem in the supplied code, please tell the instructor as soon as possible so he can post a bug-fixed version.)

Your program must correctly implement the 4 requirements for hints listed above.

Your program must be written in standard Java, in good Java style as discussed in class, and must compile and run using JCreator or the javac and java command line programs.   

Grading

Project 3 is worth ?? points toward the final grade.  It will be graded according to the criteria on the Project 3 Grade Report.  Your grade will be recorded on Angel. 

Date

Your project will be interactively graded on Monday, November 20th.  On Wednesday, November 15th each student will sign up for a specific 15 minute period for grading on the following Wednesday.   You may have your project graded before November 20th, if you wish, by making arrangements with the instructor.