public class Sudoku {
	public static final int UNSET = 0;

	public static int[] possibleNumbers(int sudoku[][], int x, int y) {
        boolean[] poss = new boolean[10];
        java.util.Arrays.fill(poss, true);
     
        for (int i = 0; i < 9; i++)
        {
            poss[sudoku[y][i]] = false;
            poss[sudoku[i][x]] = false;
            poss[sudoku[(y/3)*3+(i/3)][(x/3)*3+(i%3)]] = false;
        }
        int count = 0;
        for (int i = 1; i <= 9; i++) if (poss[i]) count++;
        int[] num = new int[count];
        count = 0;
        for (int i = 1; i <= 9; i++) if (poss[i]) num[count++] = i;
        return num;
    }
     
    // returns true if given sudoku is solvable
    public static boolean isSolvableHelper(int sudoku[][], int x, int y) {
        if (y > 8) return true;
        int pos = y*9+x+1;
        if (sudoku[y][x] != UNSET)
        {
            if (isSolvableHelper(sudoku, pos%9, pos/9)) return true;
        }
        else
        {
            for (int val : possibleNumbers(sudoku, x, y))
            {
                sudoku[y][x] = val;
                if (isSolvableHelper(sudoku, pos%9, pos/9)) return true;
                sudoku[y][x] = UNSET;
            }
        }
        return false;
    }
	
	public static boolean isSolvable(int sudoku[][]) {
		return isSolvableHelper(sudoku, 0, 0);
	}

	public static void printSudoku(int sudoku[][]) {
		for (int i = 0; i < 9; i++) {
			if (i == 3 || i == 6) {
				System.out.println("-----------");
			}
			for (int j = 0; j < 9; j++) {
				if (j == 3 || j == 6) {
					System.out.print("| ");
				}
				System.out.print(sudoku[i][j] + " ");
			}
			System.out.println("");
		}
	}

	public static void main(String args[]) {
		// TODO: test your implementation
		int solvable[][] = new int[][] {
					{5,3,0, 0,7,0, 0,0,0},
					{6,0,0, 1,9,5, 0,0,0},
					{0,9,8, 0,0,0, 0,6,0},

					{8,0,0, 0,6,0, 0,0,3},
					{4,0,0, 8,0,3, 0,0,1},
					{7,0,0, 0,2,0, 0,0,6},

					{0,6,0, 0,0,0, 2,8,0},
					{0,0,0, 4,1,9, 0,0,5},
					{0,0,0, 0,8,0, 0,7,9}
		};
		
		int unsolvable[][] = new int[][] {
					{5,3,0, 0,7,0, 0,0,4},
					{6,0,0, 1,9,5, 0,0,7},
					{0,9,8, 0,0,0, 0,6,2},

					{8,0,0, 0,6,0, 0,0,3},
					{4,0,0, 8,0,3, 0,0,1},
					{7,0,0, 0,2,0, 0,0,6},

					{0,6,0, 0,0,0, 2,8,0},
					{0,0,0, 4,1,9, 0,0,5},
					{0,0,0, 0,8,0, 0,7,9}
		};

		int unsolvable2[][] = new int[][] {
					{5,3,4, 0,0,8, 9,1,0},
					{6,7,2, 1,9,5, 3,4,8},
					{1,9,8, 3,6,0, 5,0,7},

					{8,5,9, 6,0,1, 4,0,3},
					{4,2,6, 8,5,3, 7,9,1},
					{7,1,3, 9,2,4, 8,5,6},

					{9,6,1, 5,3,7, 2,8,4},
					{2,8,7, 4,1,9, 6,3,5},
					{3,4,5, 2,8,6, 1,7,9}
		};
		
		printSudoku(solvable);
		System.out.println(isSolvable(solvable) + " (true)\n");
		
		printSudoku(unsolvable);
		System.out.println(isSolvable(unsolvable) + " (false)");

		printSudoku(unsolvable2);
		System.out.println(isSolvable(unsolvable2) + " (false)");
	}
}