public class Sudoku {
	public static void main(String[] args) {
		int grid[] = {
				0, 1, 0, 6, 0, 7, 0, 0, 4, 
				0, 4, 2, 0, 0, 0, 0, 0, 0, 
				8, 7, 0, 3, 0, 0, 6, 0, 0, 
				0, 8, 0, 0, 7, 0, 0, 2, 0, 
				0, 0, 0, 8, 9, 3, 0, 0, 0, 
				0, 3, 0, 0, 6, 0, 0, 1, 0, 
				0, 0, 8, 0, 0, 6, 0, 4, 5, 
				0, 0, 0, 0, 0, 0, 1, 7, 0,
				4, 0, 0, 9, 0, 8, 0, 6, 0 
		}; 

		System.out.println("Initial grid");
		displayGrid(grid);

		boolean[] fixed = new boolean[grid.length];

		for(int i=0; i<grid.length; i++)
			fixed[i] = grid[i] != 0; /* if(grid[i] != 0) fixed[i] = true; else fixed[i] = false; */

		int cur = 0;

		while(cur >= 0 && cur < grid.length) {
			if(fixed[cur])
				cur++;
			else {
				grid[cur]++;

				if(grid[cur] == 10) {
					grid[cur] = 0; /* reinitialize for the next time */
					for(--cur; cur>=0 && fixed[cur]; cur--); /* backtrack */
				} else {
					boolean valid = true;
					int line = cur / 9;
					int col = cur % 9;
					int sline = (line / 3) * 3;
					int scol = (col / 3) * 3;

					for(int i=0; valid && i<9; i++) {
						int icol = line*9 + i;
						int iline = i*9 + col;
						int isquare = 9 * (sline + (i / 3)) + scol + (i % 3);

						valid &= icol == cur || grid[icol] != grid[cur];
						valid &= iline == cur || grid[iline] != grid[cur];
						valid &= isquare == cur || grid[isquare] != grid[cur];
					}

					if(valid)
						cur++;
				}
			}
		}

		if(cur < 0)
			System.out.println("Unable to find a solution");
		else {
			System.out.println("Final grid");
			displayGrid(grid);
		}
	}

	static void displayGrid(int[] grid) {
		for(int i=0; i<9; i++) {
			if(i%3 == 0)
				System.out.println("-------------------------");

			for(int j=0;j<9;j++) {
				if(j%3 == 0)
					System.out.print("| ");

				int x = grid[j + i*9];
				if(x > 0)
					System.out.print(x + " ");
				else
					System.out.print(". ");
			}

			System.out.println("|");
		}
		System.out.println("-------------------------");
	}
}