解数独

---

title: 解数独
categories: 数据结构与算法

---

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

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

数字1-9在每一行只能出现一次。
数字1-9在每一列只能出现一次。
数字1-9在每一个以粗实线分隔的3x3宫内只能出现一次。
空白格用'.'表示。


一个数独。

答案被标成红色。
Note:
给定的数独序列只包含数字1-9和字符'.'。
你可以假设给定的数独只有唯一解。
给定数独永远是9x9形式的。

主要思路：
1.首先这里用到了几个技巧，首先是visited数组的设置来标记行使用，列使用，和3*3的方格内的使用情况
2.关于返回值为booelan型的递归时，如何确定返回条件

class Solution {
     boolean [][] lineUsed;
	 boolean [][] colUsed;
	 boolean [][][] boardUsed;
    public void solveSudoku(char[][] board) {
        lineUsed = new boolean[9][10];//记录行使用情况
		colUsed = new boolean[9][10];//列使用情况
		boardUsed = new boolean[9][9][10];//3*3方格内的使用情况
		for(int i = 0;i<9;i++) {
			for(int j = 0;j<9;j++) {
				if(board[i][j]!='.') {
					int num = board[i][j]-'0';
					lineUsed[i][num] = true;
					colUsed[j][num] = true;
					boardUsed[i/3][j/3][num] = true;
				}
			}
		}//先将已经填好的给标记
		recursion(board,0,0);//递归填剩下的空白处
    }
    public  boolean recursion(char[][] board,int i,int j) {
		if(j==9) {
			j = 0;
			i++;
			if(i==9) {
				return true;
			}
		}
		if(board[i][j]!='.') return recursion(board,i,j+1);//不是空白直接递归下一个位置
		for(int k= 1;k<=9;k++) { //尝试填入1-9
			if(lineUsed[i][k]||colUsed[j][k]||boardUsed[i/3][j/3][k])
				continue;//用过了就跳过
			board[i][j] = (char)(k+'0');
			lineUsed[i][k] = true;
			colUsed[j][k] = true;
			boardUsed[i/3][j/3][k] = true;
			if(recursion(board, i, j+1))return true;
			//回溯，状态重置
			board[i][j] = '.';
			lineUsed[i][k] = false;
			colUsed[j][k] = false;
			boardUsed[i/3][j/3][k] = false;
		}
		//如果1-9填入都不行那就return false
		return false;
	}
}