Sudoku Solver in Java

[randomfox]

import java.io.*;
import java.util.*;

/**
   Sudoku solver.
   Last updated: December 2, 2005
   
   @author Po Shan Cheah
   @version 0.1

   This is a puzzle where you have to fill all the blank spaces with digits
   from 1 to 9 such that no row, column, or 3x3 block of cells have any
   digits repeated.

   Supply the puzzle via standard input or via a file whose file name is
   given as the first command line argument. Example input:

    8xx 69x xx2
    91x xxx xxx
    5xx xx8 xx7

    xxx 2x9 xx6
    xxx 8xx xx3
    2xx 3x4 xxx

    3xx 78x xx9
    xxx xxx xx5
    4xx x5x x28
 */

class Sudoku {
    static void printBoard(int[][] board) {
	for (int i = 0; i < 9; ++i) {
	    for (int j = 0; j < 9; ++j)
		System.out.print(board[i][j] + " ");
	    System.out.println();
	}
    }

    /**
     * Reads a game board from a Reader.
     */
    static void inputBoard(int[][] board, Reader reader) throws IOException {
	String charset = "123456789";
	BufferedReader in = new BufferedReader(reader);
	int row = 0;
	String line;

	while ((line = in.readLine()) != null) {
	    String line2 = line.replaceAll("\\s+", "");

	    // Skip lines that are empty or all whitespace.
	    if (line2.length() == 0)
		continue;

	    if (line2.length() < 9) {
		System.err.println("bad input line: " + line);
		System.exit(1);
	    }

	    for (int i = 0; i < 9; ++i)
		board[row][i] = 1 + charset.indexOf(line2.codePointAt(i));
	    ++row;
	}
	if (row < 9) {
	    System.err.println("not enough rows in board: " + 
		    row + " rows.");
	    System.exit(1);
	}
    }

    /**
     * Determines which digits can be entered in the cell at row, col.
     * @return A stack containing the possible digits.
     */
    static Stack<Integer> getPossible(int[][] board, int row, int col) {
	boolean used[] = new boolean[10];

	for (int i = 0; i < 9; ++i) {
	    used[board[row][i]] = true;
	    used[board[i][col]] = true;
	}

	int blockrow = row - row % 3;
	int blockcol = col - col % 3;

	for (int i = blockrow; i < blockrow + 3; ++i)
	    for (int j = blockcol; j < blockcol + 3; ++j)
		used[board[i][j]] = true;

	Stack<Integer> possible = new Stack<Integer>();
	for (int i = 1; i < 10; ++i)
	    if (!used[i])
		possible.push(i);
	return possible;
    }

    /**
     * Number of nodes examined.
     */
    static int totalNodes = 0;

    /**
     * Recursive search for solutions starting at cell row, col.
     * @return true if solution found.
     */
    static boolean tryBoard(int[][] board, int row, int col) {
	if (row > 8 || col > 8) {
	    System.out.println("Success");
	    printBoard(board);
	    System.out.println(totalNodes + " nodes examined");
	    return true;
	}

	++totalNodes;

	int nextrow = row;
	int nextcol = col + 1;
	if (nextcol > 8) {
	    ++nextrow;
	    nextcol = 0;
	}

	// Skip over cells that are already filled.
	if (board[row][col] != 0)
	    return tryBoard(board, nextrow, nextcol);

	Stack<Integer> possible = getPossible(board, row, col);
	while (!possible.empty()) {
	    board[row][col] = possible.pop();
	    if (tryBoard(board, nextrow, nextcol))
		return true;
	}
	board[row][col] = 0;
	return false;
    }

    public static void main(String[] args) {
	int[][] board = new int[9][9];

	try {
	    inputBoard(board, 
		    args.length > 0 ? 
		    new FileReader(args[0]) : 
		    new InputStreamReader(System.in));
	}
	catch (FileNotFoundException e) {
	    System.err.println("can't open file: " + e.getMessage());
	    System.exit(1);
	}
	catch (IOException e) {
	    System.err.println("I/O error on input: " + e.getMessage());
	    System.exit(1);
	}

	long t0 = System.nanoTime();
	tryBoard(board, 0, 0);
	long elapsed = System.nanoTime() - t0;

	System.out.println("Elapsed time: " + elapsed / 1e9 + " seconds");
    }
}