编写一个程序，通过已填充的空格来解决数独问题。

一个数独的解法需遵循如下规则：

  1. 数字 1-9 在每一行只能出现一次。
  2. 数字 1-9 在每一列只能出现一次。
  3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

空白格用 '.' 表示。

一个数独。

答案被标成红色。

Note:

  • 给定的数独序列只包含数字 1-9 和字符 '.' 。
  • 你可以假设给定的数独只有唯一解。
  • 给定数独永远是 9x9 形式的。

 

思路：使用Java递归回溯

分别记录一个数字所在的行，列以及所在的3*3小方格是否存在该数字，3*3的小方格总共9个（0-8）可以用i / 3 * 3 + j / 3计算，，先遍历一遍进行统计，第二次遍历的时候，对空白的地方进行填写数字，也是填1-9数字进行尝试的过程。

public void solveSudoku(char[][] board) {
		// 记录某行，某位数字是否已经被摆放 申请10 只用它的1-9
		boolean[][] row = new boolean[9][10]; // row[i][j]表示第i行数字j是否存在
		// 记录某列，某位数字是否已经被摆放
		boolean[][] col = new boolean[9][10];
		// 记录某 3x3 宫格内，某位数字是否已经被摆放
		boolean[][] block = new boolean[9][10]; // 表示第几个的方格中数字是否存在
		for (int i = 0; i < 9; i++) { // 遍历9行9列
			for (int j = 0; j < 9; j++) {
				if (board[i][j] != '.') { // 记录出现过的数字
					int num = board[i][j] - '0';
					row[i][num] = true; // 第i行数字num已经存在
					col[j][num] = true; // 第j列数字num已经存在
					block[i / 3 * 3 + j / 3][num] = true;// 第i / 3 * 3 + j / 3个block的方格num已经存在
				}
			}
		}

		dfs(board, row, col, block, 0, 0); // 从0位置开始递归
	}

	private boolean dfs(char[][] arr, boolean[][] row, boolean[][] col, boolean[][] block, int i, int j) {
		while (arr[i][j] != '.') { // 直到找到为空的位置
			j++;
			if (j >= 9) { // 来到下一行第一个位置
				j = 0;
				i++;
			}
			if (i>=9) return true;
		}
		for (int num = 1; num <=9; num++) {  //用数字1-9来填补空白
			int blockIndex=i / 3 * 3 + j / 3;   //计算是属于哪一块3*3的
			//如果 行 列  以及3*3的block都不包含num  则去递归
			 if (!row[i][num] && !col[j][num] && !block[blockIndex][num]) {
				 arr[i][j] = (char) ('0' + num);  //把当前位置赋值为  num
				 row[i][num] = true; 
				 col[j][num] = true; 
				 block[i / 3 * 3 + j / 3][num] = true;
				 if (dfs(arr, row, col, block, i, j)) {  //能接着递归下去  就返回true
	                    return true;
	             }else {   //否则进行回溯倒退
	            	    row[i][num] = false;
	                    col[j][num] = false;
	                    block[blockIndex][num] = false;
	                    arr[i][j] = '.';
				}
			 }
		}
		return false;   //到最后就数独就解不了了
	}