static public void solveSudoku(char[][] board) {

		int count = 0;

		for (int i = 0; i < board.length; i++)

			for (int j = 0; j < board[0].length; j++)

				if (board[i][j] == '.')

					count++;

		dfs(board, count);

	}

	public static int dfs(char[][] board, int count) {

		if (count == 0)

			return 0;

		for (int i = 0; i < board.length; i++) {

			for (int j = 0; j < board[0].length; j++) {

				if (board[i][j] == '.') {

					for (int k = 1; k <= 10; k++) {

						if (k == 10)

							return count;

						board[i][j] = (char) ('0' + k);

						if (!isValid(board, i, j))

							board[i][j] = '.';

						else {

							count--;

							count = dfs(board, count);

							if (count == 0)

								return count;

							count++;

							board[i][j] = '.';

						}

					}

				}

			}

		}

		return count;

	}

	static public boolean isValid(char[][] board, int row, int col) {

		HashMap<Character, Integer> hashmap = new HashMap<Character, Integer>();

		for (int j = 0; j < board[0].length; j++) {

			if (board[row][j] != '.') {

				if (hashmap.containsKey(board[row][j]))

					return false;

				hashmap.put(board[row][j], 1);

			}

		}

		hashmap = new HashMap<Character, Integer>();

		for (int i = 0; i < board.length; i++) {

			if (board[i][col] != '.') {

				if (hashmap.containsKey(board[i][col]))

					return false;

				hashmap.put(board[i][col], 1);

			}

		}

		hashmap = new HashMap<Character, Integer>();

		int rowTemp = (row / 3) * 3;

		int colTemp = (col / 3) * 3;

		for (int k = 0; k < 9; k++) {

			if (board[rowTemp + k / 3][colTemp + k % 3] != '.') {

				if (hashmap

						.containsKey(board[rowTemp + k / 3][colTemp + k % 3]))

					return false;

				hashmap.put(board[rowTemp + k / 3][colTemp + k % 3], 1);

			}

		}

		return true;

	}