Sudoku Verifier

Project P6

Sudoku Verifier

Overview

Sudoku is a popular puzzle played on a 9 x 9 grid. Initially, a few of the cells of that grid contain a numbers, all integers between 1 and 9. The goal for the player is to fill in the remaining cells of the grid, also with integers between 1 and 9, given the following constraints:

Each value (1 through 9) must appear exactly once in each row.
Each value (1 through 9) must appear exactly once in each column.
Each value (1 through 9) must appear exactly once in each 3 x 3 sub-grid (or "square"), where the 9 x 9 board is divided into 9 such sub-grids.

A valid Sudoku game begins with initial numbers that, when combined with the constraints above, admit exactly one complete solution. That is, the initial numbers cannot make it impossible to fill in the board legally, nor can they allow multiple solutions. If you aren't familiar with Sudoku, you can learn more here or here.

The goal of this project is to write a Sudoku verifier. A verifier accepts an allegedly solved Sudoku grid (or partially solved grid) and then verifies whether the solution is valid, according to the rules above. (It does not have to ascertain whether a solution is possible; only whether the current grid configuration is legal.)

Problem Requirements

Write a program to perform verification for a Sudoku board.

You must follow this Java class definition:

public class Sudoku
{
    /**
     * Determine if a Sudoku board is in a legal configuration.
     * The board may be partially complete, in which case empty cells are represented
     * by a dot (.).
     * @param board a string containing the symbols in a 9x9 or 16x16 Sudoku board
     * in row-major order.
     * @pre board.length() is 81 or 256
     * @pre board 9x9 board uses symbols 1-9, 16x16 board uses A-P (uppercase).
     * @return true if the board configuration is legal, false otherwise.
     * That is, no row,
     * column or square contains a duplicate symbol.
     */
    public boolean verify(String board)
}

You may use additional private methods or helper classes in your solution.

Example Board

The following input string would represent the legal grid below:

.5...12.9.6.29....4...6....8.....4.1.73........4............6.4..5......7...8...2

board image

The grid represented by the following string would be illegal because the first column contains duplicate 7's.
75...12.9.6.29....4...6....8.....4.1.73........4............6.4..5......7...8...2

Note: Please design your own solution. While this algorithm is easy to find on the Web or in textbooks, please write your own algorithm from scratch. Do not use the internet or other resources for any purpose related to games.

Unit Testing

You must submit execution output that demonstrates that your program can produce the correct results for example in the overview above. This output can be created in one of two ways:

Write a JUnit test class and print the test source code and the successful test runner output.
Write a driver and a file of test input data. Print the driver source code, the input data file, and the execution output.

Perform any additional tests you want to convince yourself that your solution is correct.

Acceptance Testing

In addition, your program must pass the instructor's acceptance test. Once you are satisfied that your program is correct and is passing your unit tests, create a new time log entry. Enter "Test" for the phase and in the comment field enter "Acceptance Testing". (You may use "Accept Test" for the phase if you prefer. Do not count this phase as development time in your summary).

Submit your source code using the Web-CAT grader. On this project the grader will not run your own unit tests. Web-CAT will report checkstyle errors in red and they WILL count in your total score. Each coding standard violation is a defect. The defect type is 10 for code syntax, and 80 for Javadoc errors. (Tip: To avoid getting style errors in Web-CAT, run the Checkstyle extension in BlueJ before submitting to Web-CAT.)

If Web-CAT reports any errors, tally them in a new section of the defect tally without an inject phase, with a removal phase of "ACCEPTANCE TEST". Don't add them to Injected Phase or total on the Summary form. You are allowed five Web-CAT submissions without penalty. If you take more than five submissions, your project earns only half-credit.

When Web-CAT assigns a 100% score to your work, you should finalize your work according to the assignment directions.