Topic: "Recursive Sudoku Solver"

In this assignment, you implement a recursive method to find a solution to a given Sudoku problem.

A Sudoku is a 9x9 grid of integers, each with values 1..9.

A Sudoku is valid when each of the 9 rows, each of the 9 columns, and each of the 9 3x3 boxes in the grid has exactly one each of the possible values 1..9, without any duplicates.

A Sudoku problem is a Sudoku grid with some of the grid cells already filled. The solution fills the remaining cells to give a valid Sudoku.

A recursive strategy for finding a solution to a Sudoku problem is as follows:

if all cells are filled, see if this Sudoku is valid. If it is, we have found a solution. If not, this Sudoku is not a solution.

if at least one cell is not filled, see what values are legal in this cell:

If no values are legal, then this Sudoku is not a solution.

If one or more values are legal, place each legal values in the cell in turn, one at a time. For each, recursively attempt to find a solution that fills the remaining empty cells.

If a solution is found for at least one legal value, set the Sudoku to reflect this solution, and return that a solution was found.

If no solution is found for any legal value, reset this cell to the value it had when this method was called, and report that this Sudoku does not have a solution.

Every time the code recursively attempts to find a solution, it will fill cells in the Sudoku grid. If the attempt is not successful, before returning, your code must restore the Sudoku grid to the values it had before the call.

This algorithm is an example of backtracking: at any point in the search, try any one of the available options. If that option doesn't work, return to that point, and try a different option, until all the available options have been tried.

Most of the code you will need has been provided at Sudoku.java and SudokuTest.java. In particular, the method CheckSudoku returns true if a Sudoku is valid, and false otherwise (it can also print where a Sudoku is invalid). The method toString will convert a Sudoku to a printable form, again with an option to check the validity of the Sudoku and provide more information.

SudokuTest.java also provides some test Sudoku with solutions.

All this code assumes that a Sudoku is represented as a 9-element array of rows, where each row is a 9-element array of ints. Each of the ints must have a value in 1..9. The value 0 represents an empty cell.

You must implement the public static boolean fillSudoku (int [] [] sudoku) method to fill all the empty Sudoku cells with values in 1..9. Your method should return true if a solution exists, and return false otherwise. If the method returns true, it must fill in the Sudoku with a valid solution. If it returns false, it must leave the Sudoku unchanged.

Your solution must be recursive. You may want to write a recursive helper method rather than making the fillSudoku method recursive, but this choice is up to you.

Your fillSudoku code may use a for loop to test each of the legal values for one cell. However, it must use recursion to try to find values for all the other empty cells.

Note that CheckSudoku doesn't verify that all cells are filled -- it just verifies that none of the Sudoku rules are broken.

Also note that people do not generally use backtracking to solve Sudoku. That means that the AI Escargot problem in SudokuTest, which is hard for humans to solve, should not be particularly challenging for a backtracking solver.

public class Sudoku { /* check that the sudoku rules hold in this sudoku puzzle. * cells that contain 0 are not checked. * @param the sudoku to be checked * @param whether to print the error found, if any * @return true if this sudoku obeys all of the sudoku rules, otherwise false */  public static boolean checkSudoku (int [] [] sudoku, boolean printErrors) { if (sudoku.length != 9) { if (printErrors) { System.out.println ("sudoku has " + sudoku.length + " rows, should have 9"); } return false; } for (int i = 0; i < sudoku.length; i++) { if (sudoku [i].length != 9) { if (printErrors) { System.out.println ("sudoku row " + i + " has " + sudoku [i].length + " cells, should have 9"); } return false; } } /* check each cell for conflicts */ for (int i = 0; i < sudoku.length; i++) { for (int j = 0; j < sudoku.length; j++) { int cell = sudoku [i] [j]; if (cell == 0) { continue; /* blanks are always OK */ } if ((cell < 1) || (cell > 9)) { if (printErrors) { System.out.println ("sudoku row " + i + " column " + j + " has illegal value " + cell); } return false; } /* does it match any other value in the same row? */ for (int m = 0; m < sudoku.length; m++) { if ((j != m) && (cell == sudoku [i] [m])) { if (printErrors) { System.out.println ("sudoku row " + i + " has " + cell + " at both positions " + j + " and " + m); } return false; } } /* does it match any other value it in the same column? */ for (int k = 0; k < sudoku.length; k++) { if ((i != k) && (cell == sudoku [k] [j])) { if (printErrors) { System.out.println ("sudoku column " + j + " has " + cell + " at both positions " + i + " and " + k); } return false; } } /* does it match any other value in the 3x3? */ for (int k = 0; k < 3; k++) { for (int m = 0; m < 3; m++) { int testRow = (i / 3 * 3) + k; /* test this row */ int testCol = (j / 3 * 3) + m; /* test this col */ if ((i != testRow) && (j != testCol) && (cell == sudoku [testRow] [testCol])) { if (printErrors) { System.out.println ("sudoku character " + cell + " at row " + i + ", column " + j + " matches character at row " + testRow + ", column " + testCol); } return false; } } } } } return true; } /* convert the sudoku to a printable string * @param the sudoku to be converted * @param whether to check for errors * @return the printable version of the sudoku */  public static String toString (int [] [] sudoku, boolean debug) { if ((! debug) || (checkSudoku (sudoku, true))) { String result = ""; for (int i = 0; i < sudoku.length; i++) { if (i % 3 == 0) { result = result + "+-------+-------+-------+ "; } for (int j = 0; j < sudoku.length; j++) { if (j % 3 == 0) { result = result + "| "; } if (sudoku [i] [j] == 0) { result = result + " "; } else { result = result + sudoku [i] [j] + " "; } } result = result + "| "; } result = result + "+-------+-------+-------+ "; return result; } return "illegal sudoku"; } /* find an assignment of values to sudoku cells that makes the sudoku valid * @param the sudoku to be filled * @return whether a solution was found * if a solution was found, the sudoku is filled in with the solution * if no solution was found, restores the sudoku to its original value */  public static boolean fillSudoku (int [] [] sudoku) { System.out.println ("fillSudoku is not yet implemented "); return false; } } ================================ 

public class SudokuTest {  private static boolean isFilled(int [] [] sudoku) { for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) { if (sudoku [i] [j] == 0) { return false; } } } return true; } /* test whether two sudoku are equal. If not, return a new sudoku * that is blank where the two sudoku differ. * @param the sudoku to be checked * @param the solution checked * @return null if the two match, and otherwise a sudoku with 0 in * every cell that differs. */ private static int [] [] sameSudoku(int [] [] sudoku, int [] [] solution) { int [] [] result = new int [9] [9]; for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) { result [i] [j] = sudoku [i] [j]; } } boolean same = true; for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) { if (result [i] [j] != solution [i] [j]) { same = false; result [i] [j] = 0; } } } if (same) { return null; } return result; } /* try to solve a sudoku. If a solution is provided, also check * against the solution. Print the results. * @param the name of this sudoku * @param the sudoku to be solved * @param the given solution, or null */  private static void testSudoku(String name, int [] [] sudoku, int [] [] solution) { System.out.println ("solving " + name + " " + Sudoku.toString (sudoku, true)); if (Sudoku.fillSudoku (sudoku)) { if (isFilled(sudoku) && Sudoku.checkSudoku (sudoku, true)) { System.out.println ("success! " + Sudoku.toString (sudoku, true)); if (solution != null) { int [] [] diff = sameSudoku (sudoku, solution); if (diff != null) { System.out.println ("given solution: " + Sudoku.toString (solution, true)); System.out.println ("difference between solutions: " + Sudoku.toString (diff, true)); } } } else { /* the supposed solution is not a complete or valid sudoku */ if (! isFilled(sudoku)) { System.out.println ("sudoku was not completely filled: " + Sudoku.toString (sudoku, false)); } if (! Sudoku.checkSudoku(sudoku, false)) { System.out.println ("sudoku is not a valid solution: " + Sudoku.toString (sudoku, false)); } } } else { System.out.println ("unable to complete sudoku " + name + " " + Sudoku.toString (sudoku, true)); } }  public static void main (String [] arg) { int [] [] example = {{7, 8, 0, 0, 9, 0, 0, 2, 0}, {1, 0, 0, 0, 0, 0, 9, 6, 4}, {0, 0, 0, 2, 5, 1, 0, 0, 0}, {0, 0, 6, 1, 8, 5, 0, 0, 0}, {5, 0, 4, 0, 0, 0, 3, 0, 2}, {0, 0, 0, 3, 4, 2, 5, 0, 0}, {0, 0, 0, 9, 6, 3, 0, 0, 0}, {6, 4, 1, 0, 0, 0, 0, 0, 3}, {0, 9, 0, 0, 1, 0, 0, 5, 7}}; int [] [] solution = {{7, 8, 3, 4, 9, 6, 1, 2, 5}, {1, 2, 5, 7, 3, 8, 9, 6, 4}, {4, 6, 9, 2, 5, 1, 7, 3, 8}, {2, 3, 6, 1, 8, 5, 4, 7, 9}, {5, 1, 4, 6, 7, 9, 3, 8, 2}, {9, 7, 8, 3, 4, 2, 5, 1, 6}, {8, 5, 7, 9, 6, 3, 2, 4, 1}, {6, 4, 1, 5, 2, 7, 8, 9, 3}, {3, 9, 2, 8, 1, 4, 6, 5, 7}}; int [] [] example2 = {{0, 6, 0, 9, 0, 8, 0, 1, 0}, {0, 0, 4, 0, 0, 0, 0, 0, 0}, {8, 0, 3, 0, 0, 0, 4, 5, 0}, {2, 0, 0, 0, 6, 0, 0, 0, 8}, {9, 0, 0, 0, 0, 0, 0, 0, 4}, {5, 0, 0, 0, 7, 0, 0, 0, 2}, {0, 7, 8, 0, 0, 0, 9, 0, 5}, {0, 0, 0, 0, 0, 0, 6, 0, 0}, {0, 1, 0, 3, 0, 2, 0, 4, 0}}; int [] [] solution2 = {{7, 6, 5, 9, 4, 8, 2, 1, 3}, {1, 2, 4, 5, 3, 6, 7, 8, 9}, {8, 9, 3, 7, 2, 1, 4, 5, 6}, {2, 4, 7, 1, 6, 3, 5, 9, 8}, {9, 3, 6, 2, 8, 5, 1, 7, 4}, {5, 8, 1, 4, 7, 9, 3, 6, 2}, {3, 7, 8, 6, 1, 4, 9, 2, 5}, {4, 5, 2, 8, 9, 7, 6, 3, 1}, {6, 1, 9, 3, 5, 2, 8, 4, 7}}; /* a hard sudoku known as AI Escargot */ int [] [] example3 = {{1, 0, 0, 0, 0, 7, 0, 9, 0}, {0, 3, 0, 0, 2, 0, 0, 0, 8}, {0, 0, 9, 6, 0, 0, 5, 0, 0}, {0, 0, 5, 3, 0, 0, 9, 0, 0}, {0, 1, 0, 0, 8, 0, 0, 0, 2}, {6, 0, 0, 0, 0, 4, 0, 0, 0}, {3, 0, 0, 0, 0, 0, 0, 1, 0}, {0, 4, 0, 0, 0, 0, 0, 0, 7}, {0, 0, 7, 0, 0, 0, 3, 0, 0}}; testSudoku ("example 1", example, solution); testSudoku ("example 2", example2, solution2); testSudoku ("AI Escargot", example3, null); } }