SudokuBoard.java

import java.util.ArrayList;

public class SudokuBoard {
	
	private int[][] board;
	
	public SudokuBoard() {
		board = new int[9][9];
	}
	
	public SudokuBoard(int[][] setBoard) {
		board = setBoard;
	}
	
	public String toString() {
		String answer = "";
		for(int r=0; r < board.length; r++) {
			for(int c=0; c < board.length; c++) {
				answer += getCell(r,c) + " ";
			}
			answer += "\n";
		}
		return answer;
	}
	
	public void setCell(int r, int c, int value) {
		board[r][c] = value;
	}
	
	public void clearCell(int r, int c) {
		setCell(r,c,0);
	}
	
	public int getCell(int r, int c) {
		return board[r][c];
	}
	
	private boolean isEmpty(int r, int c) {
		return board[r][c] == 0;
	}
	
	private boolean takenInRow(int value, int row) {
		for(int c=0; c < board[row].length; c++) {
			if(getCell(row,c) == value) return true;
		}
		return false;
	}
	
	private boolean takenInCol(int value, int col) {
		for(int r=0; r < board.length; r++) {
			if(getCell(r,col) == value) return true;
		}
		return false;
	}
	
	private boolean takenInBox(int value, int row, int col) {
		for(int r=row*3; r < row*3+3; r++) {
			for(int c=col*3; c < col*3+3; c++) {
				if(getCell(r,c) == value) return true;
			}
		}
		return false;
	}
	
	private int[] nextEmpty(int startrow, int startcol) {
		for(int r=startrow; r < board.length; r++) {
			int col;
			if(r == startrow) col = startcol;
			else col = 0;
			for(int c=col; c < board[r].length; c++) {
				if(isEmpty(r,c)) return new int[]{r,c};
			}
		}
		return new int[]{-1,-1};
	}
	
	private ArrayList<Integer> possibilities(int row, int col) {
		ArrayList<Integer> possibilities = new ArrayList<Integer>();
		for(int n=1; n <=9; n++) possibilities.add(n);
		int boxrow = row/3;
		int boxcol = col/3;
		for(int n=1; n <=9; n++) {
			if(takenInRow(n,row)) possibilities.remove(new Integer(n));
			if(takenInCol(n,col)) possibilities.remove(new Integer(n));
			if(takenInBox(n,boxrow,boxcol)) possibilities.remove(new Integer(n));
		}
		return possibilities;
	}
	
	private boolean solveCell(int row, int col) {
		ArrayList<Integer> poss = possibilities(row,col);
		for(int n: poss) {
			setCell(row,col,n);
			int[] next = nextEmpty(row,col);
			if(next[0] == -1) return true; // no more empty cells: done!
			else {
				if(solveCell(next[0],next[1])) return true;
				else clearCell(row,col);
			}
		}
		return false;
	}
	
	public boolean solve() {
		int[] next = nextEmpty(0,0);
		return solveCell(next[0],next[1]);
	}
	
}