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 |
-------------------------