SUDOKU

Sudoku is just a puzzle, but the backtracking technique for solving it is used in many important application domains. To solve a Sudoku without backtracking, you could generate every possible solution, then evaluate all of them and collect the legal ones. But there are 9^81 ways to fill in a Sudoku grid. 9^81 is ~= 2*10^77. If you could evaluate a billion grids per second, it would take 2*10^68 seconds. The universe is less than 10^18 seconds old. For this homework, you will learn the power of backtracking by writing a Sudoku solver that finds answers in just a few seconds.

SUDOKU Rules: A puzzle looks like the one on the previous page: a 9x9 grid with some numbers filled in. The challenge is to fill in each empty space with a digit 1 through 9, so that no digit is repeated in any row, column or block. Block is the name for the nine 3x3 blocks outlined in thicker black lines in the picture.

Your Assignment: In the Eclipse workspace of your choice, create a new Java project containing package sudoku. Import the 4 starter files that you downloaded with this assignment: Evaluation.java, Grid.java, Solver.java, and TestGridSupplier.java. You won't need to change Evaluation.java or TestGridSupplier.java. Your assignment is to finish Grid.java and Solver.java. Grid: This class models a Sudoku puzzle that is unsolved, partially solved, or completely solved. The class has a 9x9 array of ints, called values. If a Sudoku square is empty, the corresponding cell in values is zero; otherwise the cell in values contains the number in the Sudoku square. The starter class has a ctor and a toString() method that you should not change. It also has 4 empty methods that you need to write: next9Grids(), isLegal(), isFull(), and equals(). Do not change their names, arg lists, or return types. The comments on the unfinished methods tell you all you need to know about what they should do. Its ok to add more methods to this class. You dont need to provide this class with hashCode() or compareTo() methods. The equals() method is just so that you can compare your puzzle solutions to solutions in TestGridSupplier. (That is, you wont be collecting Grid instances into a hash set or a tree set.) Solver: Most of this class has already been written. Complete the solveRecurse() method using the backtracking. Also complete the evaluate() method. The main() method is for you to use while testing your code with the puzzles and solutions in TestGridSupplier. Evaluation: You saw this enum in lecture and lab. It contains 3 values that represent the 3 possible outcomes of the evaluate() method of the Grid class. Look at the source code. Sometimes enums can be complicated, but this one is not.

TestGridSupplier: This class contains static methods that return Grid instances. Some of them are puzzles, some are solutions, and some are for testing your code. STRATEGY: Plan your work before you start. The Solver class needs the Grid class to be working properly, so start with Grid. First write the simple methods isFull(), and equals(). Add a main method that tests these methods with instances from TestGridSupplier. If you get unexpected results, use the debugger or println statements to step through your code and see exactly where the problem is. Then write isLegal(), which is complicated. Youll have to check 9 rows, 9 columns, and 9 blocks. You might write a method called containsNonZeroRepeat(), whose input is an array of 9 ints. For each row, column, and block, build and array of 9 ints, containing the values in that row/col/block; then let containsNonZeroRepeat() figure out if your grid is legal or illegal. One place where you may have is the next9Grids() method. Figure out which empty location in this grid will be filled in next. Then, without altering this grid, construct 9 new instances, put the new instances in an array list, and return the array list. With such a large method, there is a high probability that youll have some bugs. Test next9Grids() but writing a main() method that creates a simple grid (maybe using TestGridSupplier), generates the next grids, and prints them out. Think about what you should see. If you dont see exactly that, single-step through your code using the debugger (or use println statements) until the output is perfect. Only then, move on. Use a similar strategy for Solver. Solver is much simpler than Grid, but it contains the recursive backtracking method. Be sure you undertand this method completely. If you dont get correct answers, or if your program crashes or runs forever, use the debugger or println statements.

--------------------

package sudoku; import java.util.*; public class Grid { private int[][] values; // // DON'T CHANGE THIS. // // Constructs a Grid instance from a string[] as provided by TestGridSupplier. // See TestGridSupplier for examples of input. // Dots in input strings represent 0s in values[][]. // public Grid(String[] rows) { values = new int[9][9]; for (int j=0; j<9; j++) { String row = rows[j]; char[] charray = row.toCharArray(); for (int i=0; i<9; i++) { char ch = charray[i]; if (ch != '.') values[j][i] = ch - '0'; } } } // // DON'T CHANGE THIS. // public String toString() { String s = ""; for (int j=0; j<9; j++) { for (int i=0; i<9; i++) { int n = values[j][i]; if (n == 0) s += '.'; else s += (char)('0' + n); } s += " "; } return s; } // // DON'T CHANGE THIS. // Copy ctor. Duplicates its source. Youll call this 9 times in next9Grids. // Grid(Grid src) { values = new int[9][9]; for (int j=0; j<9; j++) for (int i=0; i<9; i++) values[j][i] = src.values[j][i]; } // // COMPLETE THIS // // // Finds an empty member of values[][]. Returns an array list of 9 grids that look like the current grid, // except the empty member contains 1, 2, 3 .... 9. Returns null if the current grid is full. Dont change // this grid. Build 9 new grids. // // // Example: if this grid = 1........ // ......... // ......... // ......... // ......... // ......... // ......... // ......... // ......... // // Then the returned array list would contain: // // 11....... 12....... 13....... 14....... and so on 19....... // ......... ......... ......... ......... ......... // ......... ......... ......... ......... ......... // ......... ......... ......... ......... ......... // ......... ......... ......... ......... ......... // ......... ......... ......... ......... ......... // ......... ......... ......... ......... ......... // ......... ......... ......... ......... ......... // ......... ......... ......... ......... ......... // public ArrayList next9Grids() { int xOfNextEmptyCell; int yOfNextEmptyCell; // Find x,y of an empty cell. // Construct array list to contain 9 new grids. ArrayList grids = new ArrayList(); // Create 9 new grids as described in the comments above. Add them to grids. return grids; } // // COMPLETE THIS // // Returns true if this grid is legal. A grid is legal if no row, column, or // 3x3 block contains a repeated 1, 2, 3, 4, 5, 6, 7, 8, or 9. // public boolean isLegal() { // Check every row. If you find an illegal row, return false. // Check every column. If you find an illegal column, return false. // Check every block. If you find an illegal block, return false. // All rows/cols/blocks are legal. return true; } // // COMPLETE THIS // // Returns true if every cell member of values[][] is a digit from 1-9. // public boolean isFull() { } // // COMPLETE THIS // // Returns true if x is a Grid and, for every (i,j), // x.values[i][j] == this.values[i][j]. // public boolean equals(Object x) { } }

----------------------------------------------

package sudoku; import java.util.*; public class Solver { private Grid problem; private ArrayList solutions; public Solver(Grid problem) { this.problem = problem; } public void solve() { solutions = new ArrayList<>(); solveRecurse(problem); } // // FINISH THIS. // // Standard backtracking recursive solver. // private void solveRecurse(Grid grid) { Evaluation eval = evaluate(grid); if (eval == Evaluation.ABANDON) { // Abandon evaluation of this illegal board. } else if (eval == Evaluation.ACCEPT) { // A complete and legal solution. Add it to solutions. } else { // Here if eval == Evaluation.CONTINUE. Generate all 9 possible next grids. Recursively // call solveRecurse() on those grids. } } // // COMPLETE THIS // // Returns Evaluation.ABANDON if the grid is illegal. // Returns ACCEPT if the grid is legal and complete. // Returns CONTINUE if the grid is legal and incomplete. // public Evaluation evaluate(Grid grid) { } public ArrayList getSolutions() { return solutions; } public static void main(String[] args) { Grid g = TestGridSupplier.getPuzzle1(); // or any other puzzle Solver solver = new Solver(g); System.out.println(Will solve  + g); solver.solve(); // Print out your solution, or test if it equals() the solution in TestGridSupplier. } }