Cell.java

package sudoku;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Iterator;

/**
 * Represents a single cell in a Sudoku.  Tracks cell's row number and column number in the sudoku.
 * If the cell is unsolved, stores a hashset of possible values (candidates). 
 * @author
 */
public class Cell implements Comparable<Cell>, Cloneable {
    private static final Integer[] SUDOKU_VALUES = {1,2,3,4,5,6,7,8,9};
	private int solution;
	private boolean solved;
	private int rowNum;
	private int colNum;
	private HashSet<Integer> values;
	
	public Cell(int solution, int rowNum, int colNum) throws IllegalArgumentException {
		values = new HashSet<Integer>();
		this.rowNum = rowNum;
		this.colNum = colNum;
		set(solution);
	}
	
	public boolean isSolved() {
		return solved;
	}
	
	public int get() {
		return solution;
	}
	
	public int getRowNum() {
		return rowNum;
	}
	
	public int getColNum() {
		return colNum;
	}
	
	/**
	 * Removes a candidate from the hashset
	 * @param value
	 */
	public void remove(int value) {
		values.remove(value);
		if(numCandidates() == 1) {
			solution = values.iterator().next();
			solved = true;
		}
	}
	
	public void remove(int[] values) {
		for(int i = 0; i < values.length; i++) {
			this.values.remove(values[i]);
		}		
		if(numCandidates() == 1) {
			solution = this.values.iterator().next();
			solved = true;
		}
	}
	
	public void set(int solution) throws IllegalArgumentException {
		if(solution < 0 || solution > 9) throw new IllegalArgumentException();
		if(solution == 0) {
			values.addAll(Arrays.asList(SUDOKU_VALUES));
			solved = false;
		}
		else solved = true;
		this.solution = solution;
	}
	
	/**
	 * Selects a candidate from the hashset as the value in this cell.
	 * Does not flag this cell as solved.
	 * @throws IllegalStateException
	 */
	public void guess() throws IllegalStateException {
		if(isSolved()) throw new IllegalStateException();
		solution = values.iterator().next();
		values.remove(solution);
	}
	
	public int numCandidates() {
		return values.size();
	}
	
	public int[] getCandidates() {
		Iterator<Integer> iter = values.iterator();
		int[] output = new int[values.size()];
		int i = 0;
		while(iter.hasNext()) {
			output[i] = iter.next();
			i++;
		}
		return output;
	}
	
	@Override
	public String toString() {
		return String.valueOf(solution);
	}

	@Override
	public int compareTo(Cell c) {
		if(this.numCandidates() > c.numCandidates()) return -1;
		else if(this.numCandidates() < c.numCandidates()) return 1;
		else return 0;
	}
	
	@Override
	public Object clone() {
		Cell c = new Cell(solution, rowNum, colNum);
		return (Object) c;
	}
}

DFS

//Pseudocode for DFS

    public Sudoku search(Sudoku puzzle) {
		if(puzzle.solved()) return puzzle;
		
		Sudoku s = (Sudoku) puzzle.clone();
		//get cell with fewest candidates
        Cell c = s.getEasiest();
		c.guess();
		s.constraintPropagation();
		
		//if cell has other candidates try again
		if(s.hasContradiction() && s.getEasiest().numCandidates() > 0) {
			puzzle.getEasiest().remove(c.get());
			search(puzzle);
		}
		
		//if cell does not have any other candidates
		if(s.hasContradiction() && s.getEasiest().numCandidates() < 1) {
			//TODO
		}
	}

Solve.java

package sudoku;

public class Solve {
    public static void main(String[] args) {
		int[][] puzzle = 
	   {{0,0,3,0,2,0,6,0,0},
		{9,0,0,3,0,5,0,0,1},
		{0,0,1,8,0,6,4,0,0},
		{0,0,8,1,0,2,9,0,0},
		{7,0,0,0,0,0,0,0,8},
		{0,0,6,7,0,8,2,0,0},
		{0,0,2,6,0,9,5,0,0},
		{8,0,0,2,0,3,0,0,9},
		{0,0,5,0,1,0,3,0,0}};
		
		Sudoku s = new Sudoku(puzzle);
		System.out.println(s.numUnsolved());
		s.constraintPropagation();
		System.out.println(s);
		System.out.println(s.numUnsolved());
	}
}

Sudoku.java

package sudoku;

import java.util.Arrays;
import java.util.Iterator;

/**
 * Stores a 9x9 Sudoku and implements basic operations to check rows, columns and 3x3 grids.
 * @author
 */
public class Sudoku implements Iterable<Cell>, Cloneable {
    private Cell[][] cells;
	private int numUnsolved;
	
	public Sudoku(int[][] puzzle) throws IllegalArgumentException {
		if(puzzle.length != 9) throw new IllegalArgumentException();
		cells = new Cell[9][9];
		numUnsolved = 0;
		for(int rowNum = 0; rowNum < puzzle.length; rowNum++) {
			initRow(rowNum, puzzle[rowNum]);
		}
	}
	
	public Sudoku(Cell[][] cells, int numUnsolved) {
		this.cells = cells;
		this.numUnsolved = numUnsolved;
	}
	
	private void initRow(int rowNum, int[] row) throws IllegalArgumentException {
		if(row.length != 9) throw new IllegalArgumentException();
		for(int colNum = 0; colNum < row.length; colNum++) {
			if(row[colNum] == 0) numUnsolved++;
			cells[rowNum][colNum] = new Cell(row[colNum], rowNum, colNum);
		}
	}
	
	public void set(int rowNum, int colNum, int num) throws IllegalArgumentException {
		if(num < 0 || num > 9) throw new IllegalArgumentException();
		cells[rowNum][colNum].set(num);
	}
	
	public int get(int rowNum, int colNum) {
		return cells[rowNum][colNum].get();
	}
	
	public int[] getRow(int rowNum) {
		int[] row = new int[9];
		for(int colNum = 0; colNum < 9; colNum++) {
			row[colNum] = cells[rowNum][colNum].get();
		}
		return row;
	}
	
	public int[] getCol(int colNum) {
		int[] column = new int[9];
		for(int rowNum = 0; rowNum < 9; rowNum++) {
			column[rowNum] = cells[rowNum][colNum].get();
		}
		return column;
	}
	
	public int[] getGrid(int rowNum, int colNum) {
		int[] sub = new int[9];
		int addOffsetX = 3 - ( (rowNum % 3) + 1 );
		int addOffsetY = 3 - ( (colNum % 3) + 1 ); ;
		int minusOffsetX = (rowNum % 3) ;
		int minusOffsetY = (colNum % 3) ;
		
		int index = 0;
		for(int row = rowNum - minusOffsetX; row < rowNum + addOffsetX + 1; row++) {
			for(int col = colNum - minusOffsetY; col < colNum + addOffsetY + 1; col++) {
				sub[index] = cells[row][col].get();
				index++;
			}
		}
		return sub;
	}
	
	/**
	 * Returns cell with fewest candidates.
	 * @return
	 */
	public Cell getEasiest() {
		Cell easiest = null;
		Iterator<Cell> iter = iterator();
		while(iter.hasNext()) {
			Cell c = iter.next();
			if(easiest == null && !c.isSolved()) easiest = c;
			if(!c.isSolved() && easiest.compareTo(c) < 0) easiest = c;
		}
		return easiest;
	}
	
	/**
	 * Returns number of unsolved cells in Sudoku.
	 * @return
	 */
	public int numUnsolved() {
		return numUnsolved;
	}
	
	/**
	 * Checks if column, row or grid contain duplicate numbers
	 * @param region Column, row or grid
	 * @return
	 */
	public boolean checkValid(int[] region) {
		boolean[] check = new boolean[9];
		for(int i = 0; i < region.length; i++) {
			if(region[i] == 0) ; //do nothing
			else if(check[region[i] - 1]) return false;
			else check[region[i] - 1] = true;
		}
		return true;
	}
	
	public boolean checkSolved() {
		return numUnsolved == 0;
	}
	
	/**
	 * Performs one iteration of constraint propagation.  For each unsolved cell, checks
	 * the row, column and grid and removes those values from the list of candidates.
	 */
	private void propogate() {
		for(int rowNum = 0; rowNum < cells.length; rowNum++) {
			for(int colNum = 0; colNum < cells[rowNum].length; colNum++) {
				if(!cells[rowNum][colNum].isSolved()) {
					cells[rowNum][colNum].remove(getRow(rowNum));
					cells[rowNum][colNum].remove(getCol(colNum));
					cells[rowNum][colNum].remove(getGrid(rowNum,colNum));
					if(cells[rowNum][colNum].isSolved()) numUnsolved--;
				}
			}
		}
	}
	
	/**
	 * Loops constraint propagation
	 */
	public void constraintPropagation() {
		int prevNumUnsolved = -1;
		int newNumUnsolved = numUnsolved;
		while(prevNumUnsolved != newNumUnsolved) {
			propogate();
			prevNumUnsolved = newNumUnsolved;
			newNumUnsolved = numUnsolved();
		}
	}
	
	//TODO
	public Sudoku search(Sudoku puzzle) {
		//recursive depth first search
	}
	
	@Override
	public Object clone() {
		Cell[][] copy = new Cell[9][9];
		for(int rowNum = 0; rowNum < cells.length; rowNum++) {
			for(int colNum = 0; colNum < cells[rowNum].length; colNum++) {
				copy[rowNum][colNum] = (Cell) cells[rowNum][colNum].clone();
			}
		}
		Sudoku s = new Sudoku(copy, numUnsolved);
		return (Object) s;
	}
	
	@Override
	public String toString() {
		return Arrays.deepToString(cells);
	}

	@Override
	public Iterator<Cell> iterator() {
		return new SudokuIterator();
	}
	
	public class SudokuIterator implements Iterator<Cell> {
		private int index = 0;
		
		@Override
		public boolean hasNext() {
			return index == 80;
		}

		@Override
		public Cell next() {
			int row = (index / 9);
			int col = (index % 9);
			Cell toReturn = cells[row][col];
			index++;
			return toReturn;
		}

		@Override
		public void remove() throws UnsupportedOperationException {
			throw new UnsupportedOperationException();
		}
	}
}