Example Depot

1. Find an empty cell 1a. If there are no more empty cells, the puzzle is solved 2. Fill the empty cell with the lowest possible valid number 2a. If no valid number exists, backtrack to the previous empty cell and try the next higher valid number in that cell 3. Go to step 1

/** * This program is executed in the following way: * java SudokuSolver <input-file> * For details of the input-file format, see the Grid.java class. * * @author Patrick Chan * @version 1, 12/31/05 * @see Grid */ import java.io.*; import java.util.*; public class SudokuSolver { public static void main(String[] args) throws Exception { // Open the file containing the givens File file = new File(args[0]); FileReader rd = new FileReader(args[0]); // Process each grid in the file while (true) { Grid grid = Grid.create(rd); if (grid == null) { // No more grids break; } // Find a solution List<Grid> solutions = new ArrayList<Grid>(); solve(grid, solutions); printSolutions(grid, solutions); } } // Recursive routine that implements the bifurcation algorithm private static void solve(Grid grid, List<Grid> solutions) { // Return if there is already a solution if (solutions.size() >= 2) { return; } // Find first empty cell int loc = grid.findEmptyCell(); // If no empty cells are found, a solution is found if (loc < 0) { solutions.add(grid.clone()); return; } // Try each of the 9 digits in this empty cell for (int n=1; n<10; n++) { if (grid.set(loc, n)) { // With this cell set, work on the next cell solve(grid, solutions); // Clear the cell so that it can be filled with another digit grid.clear(loc); } } } private static void printSolutions(Grid grid, List<Grid> solutions) { // Print the grid with the givens System.out.println("Original"); System.out.println(grid); // Print the solution if (solutions.size() == 0) { System.out.println("Unsolveable"); } else if (solutions.size() == 1) { System.out.println("Solved"); } else { System.out.println("At least two solutions"); } // Print the solution(s) for (int i=0; i<solutions.size(); i++) { System.out.println(solutions.get(i)); } System.out.println(); System.out.println(); } }

/** * @author Patrick Chan * @version 1, 12/31/05 * @see SudokuSolver */ import java.io.*; import java.util.*; /** * A Grid object holds the currently known values of the Sudoku puzzle. * The grid consists of 9x9 cells that hold integer values from 0 to 9. * A value of 0 indicates that the cell is empty. * * Each of the 81 cells has a location which is used to identify a * specific cell. There are 81 locations, labelled location 0 to location 80. * Cell locations are ordered from left-to-right and top-down. * For example, location 0 refers to the top-leftmost cell. * Location 8 refers to the top-righttmost cell. * Location 71 refers to the bottom-leftmost cell. * Location 80 refers to the bottom-rightmost cell. * * The grid consists of 9 columns, labelled column 0 to column 8. * The grid consists of 9 rows, labelled row 0 to row 8. * * The grid consists of 9 subgrids, labelled subgrid 0 to subgrid 8. * Each subgrid contains a subgrid of 3x3 cells. * Subgrid 0 contains cells - 0, 1, 2, 9, 10, 11, 18, 19, 20. * Subgrid 8 contains cells - 60, 61, 62, 69, 70, 71, 78, 79, 80 */ public class Grid implements Cloneable { // Array that contains values of all 81 cells in the grid. int[] cells = new int[81]; // A set of bit-vectors that represent the known values for each column. // Specifically, if column c contains the digits d1 and d2, // colsSet[c] = 2^(d1-1)|2^(d2-1) // For example, if column 0 contains the values 1 and 4, colsSet[0] = 9. // The information in this variable is redundant with the information // in the cells variable. The purpose of this variable is to reduce // the cost of determining whether a particular digit can be set in // a particular cell. int[] colsSet = new int[9]; // This purpose and behavior of this variable is similar to colsSet. int[] rowsSet = new int[9]; // This purpose and behavior of this variable is similar to colsSet. int[] subgridSet = new int[9]; /** * This method returns a grid of givens and empty cells ready to be solved. * The cells containing givens have values between 1 and 9. * Empty cells have the value 0. * * Characters are read one at a time from the input stream and placed * into the grid in left-to-right and top-down order. * - The characters 0 or . indicates an empty cell. * - The characters 1 to 9 indicates a given. * - The character # is used for comments; subsequent characters are * ignored until a newline is encountered. * - All other characters are simply ignored. * * @param rd Reader containing the givens * @return null if there are not enough characters in 'rd' to form a grid. */ public static Grid create(Reader rd) throws Exception { Grid grid = new Grid(); // Read until all 81 cells are filled for (int loc=0; loc<grid.cells.length; ) { // Read a character int ch = rd.read(); // -1 is returned if the input stream has no more characters if (ch < 0) { // No more characters so return null return null; } if (ch == '#') { // Skip to end-of-line while (ch >= 0 && ch != '\n' && ch != '\r') { ch = rd.read(); } } else if (ch >= '1' && ch <= '9') { // A given grid.set(loc, ch-'0'); loc++; } else if (ch == '.' || ch == '0') { // Empty cell loc++; } } return grid; } /* * Finds an empty cell. * @return the location of an empty cell or -1 if there are no empty cells. * Values must be in the range [-1, 80]. */ public int findEmptyCell() { for (int i=0; i<cells.length; i++) { if (cells[i] == 0) { return i; } } return -1; } /* * Sets a number in a cell. This method checks to see if * 1. the cell is empty * 2. the cell is allowed to contain the specified number. E.g. if * the number is 5 but the row already has a 5, the cell will * not be set and false is returned. * @param loc the location of the target cell. * Values must be in the range [0, 80]. * @param num the number to set in the cell. * Values must be in the range [1, 9]. * @return true if the set was successful. */ public boolean set(int loc, int num) { // Compute row and column int r = loc/9; int c = loc%9; int blockLoc = (r/3)*3+c/3; boolean canSet = cells[loc] == 0 && (colsSet[c] & (1<<num)) == 0 && (rowsSet[r] & (1<<num)) == 0 && (subgridSet[blockLoc] & (1<<num)) == 0; if (!canSet) { return false; } cells[loc] = num; colsSet[c] |= (1<<num); rowsSet[r] |= (1<<num); subgridSet[blockLoc] |= (1<<num); return true; } /* * Removes the number in a cell. * @param loc the location of the target cell. * Values must be in the range [0, 80]. */ public void clear(int loc) { // Compute row and column int r = loc/9; int c = loc%9; int blockLoc = (r/3)*3+c/3; int num = cells[loc]; cells[loc] = 0; colsSet[c] ^= (1<<num); rowsSet[r] ^= (1<<num); subgridSet[blockLoc] ^= (1<<num); } /** * Returns a copy of this grid. Any modifications to the returned * grid will not affect this grid. * * @return a non-null deep copy of this grid. */ public Grid clone() { Grid grid = new Grid(); grid.cells = cells.clone(); grid.colsSet = colsSet.clone(); grid.rowsSet = rowsSet.clone(); grid.subgridSet = subgridSet.clone(); return grid; } /** * Returns a string representing the current contents of the grid. * Used for debugging purposes. * * @return a non-null string representing the current contents of the grid. */ public String toString() { StringBuffer buf = new StringBuffer(); for (int r=0; r<9; r++) { if (r%3 == 0) { buf.append("-------------------------\n"); } for (int c=0; c<9; c++) { if (c%3 == 0) { buf.append("| "); } int num = cells[r*9+c]; if (num == 0) { buf.append(". "); } else { buf.append(num+" "); } } buf.append("|\n"); } buf.append("-------------------------"); return buf.toString(); } }

# This puzzle was obtained from sudoku.com .6.|1.4|.5. ..8|3.5|6.. 2..|...|..1 ---+---+--- 8..|4.7|..6 ..6|...|3.. 7..|9.1|..4 ---+---+--- 5..|...|..2 ..7|2.6|9.. .4.|5.8|.7. ----------- # http://www.sudoku.org.uk/bifurcation.htm 1 0 0 9 0 7 0 0 3 0 8 0 0 0 0 0 7 0 0 0 9 0 0 0 6 0 0 0 0 7 2 0 9 4 0 0 4 1 0 0 0 0 0 9 5 0 0 8 5 0 4 3 0 0 0 0 3 0 0 0 7 0 0 0 5 0 0 0 0 0 4 0 2 0 0 8 0 6 0 0 9 # This puzzle has multiple solutions 1 2 3 4 5 6 7 8 9 0 6 0 0 0 0 0 3 0 0 7 0 0 0 0 0 4 0 7 8 9 1 2 3 4 5 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 5 6 7 8 9 1 2 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Original ------------------------- | . 6 . | 1 . 4 | . 5 . | | . . 8 | 3 . 5 | 6 . . | | 2 . . | . . . | . . 1 | ------------------------- | 8 . . | 4 . 7 | . . 6 | | . . 6 | . . . | 3 . . | | 7 . . | 9 . 1 | . . 4 | ------------------------- | 5 . . | . . . | . . 2 | | . . 7 | 2 . 6 | 9 . . | | . 4 . | 5 . 8 | . 7 . | ------------------------- Solved ------------------------- | 9 6 3 | 1 7 4 | 2 5 8 | | 1 7 8 | 3 2 5 | 6 4 9 | | 2 5 4 | 6 8 9 | 7 3 1 | ------------------------- | 8 2 1 | 4 3 7 | 5 9 6 | | 4 9 6 | 8 5 2 | 3 1 7 | | 7 3 5 | 9 6 1 | 8 2 4 | ------------------------- | 5 8 9 | 7 1 3 | 4 6 2 | | 3 1 7 | 2 4 6 | 9 8 5 | | 6 4 2 | 5 9 8 | 1 7 3 | ------------------------- Original ------------------------- | 1 . . | 9 . 7 | . . 3 | | . 8 . | . . . | . 7 . | | . . 9 | . . . | 6 . . | ------------------------- | . . 7 | 2 . 9 | 4 . . | | 4 1 . | . . . | . 9 5 | | . . 8 | 5 . 4 | 3 . . | ------------------------- | . . 3 | . . . | 7 . . | | . 5 . | . . . | . 4 . | | 2 . . | 8 . 6 | . . 9 | ------------------------- Solved ------------------------- | 1 6 4 | 9 5 7 | 2 8 3 | | 3 8 5 | 6 2 1 | 9 7 4 | | 7 2 9 | 4 3 8 | 6 5 1 | ------------------------- | 5 3 7 | 2 8 9 | 4 1 6 | | 4 1 2 | 7 6 3 | 8 9 5 | | 6 9 8 | 5 1 4 | 3 2 7 | ------------------------- | 8 4 3 | 1 9 5 | 7 6 2 | | 9 5 6 | 3 7 2 | 1 4 8 | | 2 7 1 | 8 4 6 | 5 3 9 | ------------------------- Original ------------------------- | 1 2 3 | 4 5 6 | 7 8 9 | | . 6 . | . . . | . 3 . | | . 7 . | . . . | . 4 . | ------------------------- | 7 8 9 | 1 2 3 | 4 5 6 | | . . . | . . . | . . . | | . . . | . . . | . . . | ------------------------- | 4 5 6 | 7 8 9 | 1 2 3 | | . . . | . . . | . . . | | . . . | . . . | . . . | ------------------------- At least two solutions ------------------------- | 1 2 3 | 4 5 6 | 7 8 9 | | 5 6 4 | 8 9 7 | 2 3 1 | | 9 7 8 | 2 3 1 | 6 4 5 | ------------------------- | 7 8 9 | 1 2 3 | 4 5 6 | | 2 3 1 | 5 6 4 | 8 9 7 | | 6 4 5 | 9 7 8 | 3 1 2 | ------------------------- | 4 5 6 | 7 8 9 | 1 2 3 | | 3 1 2 | 6 4 5 | 9 7 8 | | 8 9 7 | 3 1 2 | 5 6 4 | ------------------------- ------------------------- | 1 2 3 | 4 5 6 | 7 8 9 | | 5 6 4 | 8 9 7 | 2 3 1 | | 9 7 8 | 2 3 1 | 6 4 5 | ------------------------- | 7 8 9 | 1 2 3 | 4 5 6 | | 2 3 1 | 5 6 4 | 8 9 7 | | 6 4 5 | 9 7 8 | 3 1 2 | ------------------------- | 4 5 6 | 7 8 9 | 1 2 3 | | 8 9 7 | 3 1 2 | 5 6 4 | | 3 1 2 | 6 4 5 | 9 7 8 | -------------------------