Sudoku-Solver

gistfile1.java

/*Sudoku Solver
This Sudoku solver gives solution to a Sudoku given a Sudoku problem in Row Major Form*
I am going to first try solving this using Depth First Search.
TODO I also want to try solving it like a human would using constraints.
The assumption is that a Soduku is a 9 x 9 solution

Solution inspired by JOHANNES BRODWALL 
Written by Andrew Tam

Input Form:
*/
import java.io.File;
import java.io.FileReader;
import java.io.BufferedReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Arrays;
import java.lang.Character;

public class SudokuSolver {
	public static final int SIZE = 9; //Assumes Sudoku is 9 x 9
	private static int[][] sudokuBoard;

	public static void main(String[] args) {
		try {
			File file = new File(args[0]);
			BufferedReader in = new BufferedReader(new FileReader(file));
			String sudokuInRowMajorForm;
			while ((sudokuInRowMajorForm = in.readLine()) != null) {
				System.out.println();
				// Check if valid 9 x 9 board
				if (sudokuInRowMajorForm.length() == SIZE * SIZE) {
					System.out.println("Row Major Form: " + sudokuInRowMajorForm);
					sudokuBoard = new int[SIZE][SIZE];
					sudokuBoard = getSudokuBoardFromRowMajorForm(sudokuInRowMajorForm);

					System.out.println("Input:");
					printSudokuBoard();
					findSolution();
					System.out.println();

					System.out.println("Output:");
					printSudokuBoard();
				} else {
					System.out.println("Input not valid sudoku puzzle");
				}
			}
		} catch (Exception e) {
			e.printStackTrace();
		}
	}

	public static boolean findSolution() {
		return findSolution(0);
	}

	//Depth First Search
	public static boolean findSolution(int cell) {
		// Visited all cells
		if (cell == SIZE * SIZE) {
			return true;
		}
		boolean isEmpty = (sudokuBoard[getRow(cell)][getCol(cell)] == 0);
		for (Integer value : getPossibleValues(getRow(cell), getCol(cell))) {
			sudokuBoard[getRow(cell)][getCol(cell)] = value;
			if (findSolution(cell + 1)) {
				return true;
			}
		}
		// No solution found
		if (isEmpty) {
			sudokuBoard[getRow(cell)][getCol(cell)] = 0;
		}
		return false;
	}

	// This returns the possible values of a particular cell if it is empty. Searches row, col and box for repeats.
	// Else it just returns the current value
	public static List<Integer> getPossibleValues(int row, int col) {
		if (sudokuBoard[row][col] != 0) {
			return Arrays.asList(sudokuBoard[row][col]);
		}
		Integer[] allValues = {1, 2, 3, 4, 5, 6, 7, 8, 9}; //These are all possible values in Sudoku
		List<Integer> possibleValues = new LinkedList<Integer>(Arrays.asList(allValues));
		// Remove values in row
		for (int i = 0; i < SIZE; i++) {
			possibleValues.remove((Integer)sudokuBoard[row][i]);
		}
		// Remove values in col
		for (int i = 0; i < SIZE; i++) {
			possibleValues.remove((Integer)sudokuBoard[i][col]);
		}
		// Remove values in box
		for (int i = 0; i < 3; i++) {
			for (int j = 0; j < 3; j++) {
				possibleValues.remove((Integer)sudokuBoard[i + 3 * (row / 3)][j + 3 * (col / 3)]);
			}
		}
		return possibleValues;
	}

	/** Helper Methods **/
	public static int getRow(int cell) {
		return (int)Math.floor(cell / SIZE);
	}

	public static int getCol(int cell) {
		return cell % SIZE;
	}

	public static void printSudokuBoard() {
		for (int row = 0; row < SIZE; row++) {
			if (row % 3 == 0) {
				System.out.println("---------------------");
			}
			for (int col = 0; col < SIZE; col++) {
				if (col % 3 == 0) {
					System.out.print("|");
				}
				System.out.print(sudokuBoard[row][col] + " ");
			}
			System.out.println();
		}
	}

	public static int[][] getSudokuBoardFromRowMajorForm(String sudokuInRowMajorForm) {
		for (int row = 0; row < SIZE; row++) {
			for (int col = 0; col < SIZE; col++) {
				int cellValue = Character.getNumericValue(sudokuInRowMajorForm.charAt(row * SIZE + col));
				if (cellValue != 0) {
					sudokuBoard[row][col] = cellValue;
				}
			}
		}
		return sudokuBoard;
	}
}