Data Structures-Project 3 Sudoku Solved

   You will implement four methods to solve the problem: isFullSolution , reject , extend , and next .

To     complement     those     four,     there     are     four     testing             methods:

  testIsFullSolution , testReject , testExtend , and testNext . Each of these should make several tests of the corresponding solving methods.

The puzzle-solving algorithm
By implementing the four solving methods, you will be constructing a backtracking solver program. Important points:

 You must not change any of the original numbers already on the board. You must implement all the Sudoku rules: each row, column, and 3x3 square may only contain each number once.

  You only need to find one solution, not all solutions. Once you find a solution, you can stop.

  If a board is not solvable, your program must say so.

The puzzle-solving methods
 These methods make up the four parts of the backtracking template. These methods are not recursive! Only the solve method is, and we already wrote that for you ;)

 boolean isFullSolution(int[][] board)
 This takes a board as a 2D array, and returns true if it is complete (no empty cells) and satisfies all the rules.

 If there are any empty cells, or if there are any rule violations, it returns false.

boolean reject(int[][] board)
 This takes a partial solution, and returns true if it is impossible to continue with this board.

 For example, if there are two 3’s on one row, there is no reason to keep solving this board. int[][] extend(int[][] board)

 This takes a partial solution, and constructs a new partial solution. When I say “new” I mean use new to allocate a new 2D array!

  What I mean by “constructs a new partial solution” is it places a number into a previously-empty cell.

 If there are no more possible cells to place a number in, it should return null.

int[][] next(int[][] board)
The partner to extend . This takes a partial solution, and constructs another new partial solution.

  It will change the most-recently-placed number to the next possible option.

  So if the most-recently-placed number was a 1, this would change it to a 2…

  …or a 2 to a 3, or a 3 to a 4, and so on.

  If there are no options for the most-recently-placed number, it should return null.

 Do not write all the methods at once. Start with isFullSolution and reject . Test them extensively with your testing methods (by running your program with java Sudoku -t ).

The testing methods
Re-read starting at Chapter 2.16 to review the concepts behind writing test methods. Write your testing methods at the same time you write the solving methods. Have a look at this 8-Queens example to see some example testing methods.

For each of the testing methods, try to follow these guidelines:

  Come up with a variety of partial solutions that will test all possible paths through your solving method.

 Call the method with those partial solutions.

Check that the method actually returns what you expect it to return. Print out the test cases and results, so that you can easily see if things are looking right.

  Include enough test cases that you are convinced that your solving method is working properly.

 You can make new board files following the guidelines below, and then use readBoard to load them for testing.

 For example, if I were testing the reject method, I would give it…

 a board with two of the same number in the same row. a board with two of the same number in the same column.

a board with two of the same number in a 3x3 square.

    (probably a few versions of that, to be thorough.)   the boards we gave you ( 1-trivial.su etc.) to make sure it doesn’t reject those. a solved board (look online for one) to make sure it doesn’t reject that.

Example boards
 We’ve included 5 example boards (the .su files). If you open them in your text editor, you will see they look something like this:

 

There are 9 rows, and each has 9 columns. Any non-number character is treated as an empty (unsolved) cell.