Your task is to write a Java program that will solve incomplete Sudoku puzzles that will be read from files. This assignment requires you to use recursion in game environment to support backtracking. You must use recursion in your solution.

Location.java

This class represents a location on a Sudoku board. It should store a row and column value, and include methods for getting the "next" location from the current one.

public Location( int r, int c )

The constructor for Location. It should store the row and column values.

public int getRow()

Returns the Location's row value.

public int getColumn()

Returns the Location's column value.

public Location next()

Gets the next Location after this one. Should proceed through a row by incrementing the column value, until it needs to move to the next row. For example, the next location from 1,1 is 1,2 but the next location from 1,8 is 2,0. Should return null if the next location would be outside the space of a standard Sudoku board (9 rows by 9 columns.)

public String toString()

Returns a string representation of this Location. It should be in this format: row, col

Board.java

This class represents the 9x9 board of values for the Sudoku puzzle. It should store the values for the current state of the puzzle, and contains methods to read in a board as well as methods to help check whether a value is allowed in a give row, column, 3x3 box, or location.

public Board( Scanner sc )

Constructor for the Board class. Creates the instance variables to store the values for a 9x9 board. Should use readBoard to do most of its work.

public static int[][] readBoard( Scanner sc )

Uses the provided Scanner to read the board and return a 2D integer array with the appropriate values. Input should be 9 rows of values with 9 characters each. These characters will be 1-9 to indicate a fixed number in the starting board, or a - (dash) to indicate an empty location. A value of 0 indicates an empty space in the returned array. Should return null if the board was invalid (contains invalid characters or does not contain enough values.)

public int get( int row, int col )

Returns the value at row, col in the board.

public void set( int row, int col, int value )

Sets the value at row, col in the board. Does not need to confirm that the value is allowed, as these checks should be done before calling this method.

public boolean containsInRow( int row, int number )

Returns true if number was already contained in row, false otherwise.

public boolean containsInCol( int col, int number )

Returns true if number was already contained in col, false otherwise.

public boolean containsInBox( int row, int col, int number )

Returns true if number was already contained in the 3x3 box containing row, col, false otherwise. For instance, for 0,1 the method should check the box 0,0 through 2,2

public boolean isAllowed(int row, int col, int number)

Returns true if number would be valid to assign to row, col, false otherwise. For number to be allowed it should satisfy all of the rules for row, column, and 3x3 box.

public String toString()

Returns a string representation of the board. Uses dashes to indicate empty spaces, and indicates the 3x3 boxes within the board.

Sudoku.java

This class does the work of solving the Sudoku puzzle, as well as containing the main method to provide a text-based user interface. Stores a Board object which it uses in solving. It should also track statistics about the solving process: the number of recursive calls made, and the number of "backups" that had to be done.

public Sudoku( Scanner sc )

Constructor for the Sudoku class. Initializes the board and other instance variables.

public boolean solve( Location loc )

Recursively solves the board from the current configuration, using the backtracking algorithm described above. Returns true if a solution was found from the current configuration, false otherwise. Should only assign valid values to board locations, and should not overwrite locations that had values in the original board configuration.

public int getRecursionCount()

Returns the recursion count after the puzzle has been solved (or discovered to be unsolvable.)

public int getBackupCount()

Returns the backup count after the puzzle has been solved (or discovered to be unsolvable.)

public Board getBoard()

Returns the Sudoku board.

public static void main( String[] args )

The main method. Prompts the user for a file name, creates a Scanner using that file, creates a Sudoku object, prints the intial board, calls the solve method, and then prints the results, including the recursion count and backup count.