搜索经典题——填充 9*9矩阵

题目：给定一个九行九列矩阵，填充矩阵元素，要求：

1、每一行每一列，每个小九宫格（图片画粗的地方就是）不能包含相同元素

2、每一行，每一列，每个小九宫格均会完整出现1-9的数字 

思路：DFS回溯填充数字，一行一行填充，当填充到第十行说明填充成功，每填充一个位置，都需要用"istrue"函数验证一下该位置是否合法（需要判断每一行，每一列，每个小九宫格是否包含了相同元素，唯一难点就是判断当前填充位置的小九宫格起点位置）  

//分治回溯 回溯的应用 之 数独问题
/*
判断填入的数据是否满足条件 一行中没有相同的 并且 一列中没有相同的 并且 当前方格所在的子方块中没有相同的
虽然数独问题只有一个解 但是我们解决数独问题时 是向多个解的方向去求解的*/
public class SudoKu {//表示第count个解private static int count = 0;//表示存放数独数据的矩阵容器private static int[][] board= new int[9][9];public static void main(String[] args) throws IOException {readFile("SudoKu_data"); //读取数独文件solve(0, 0); //向数独矩阵中添加元素}//向数独矩阵中添加元素/*向下一个位置递归的 列的更新为：col=(col+1)%9行的更新：更新行必须将col递归到当前行的末尾时才能更新 更新为：row=row+(col+1)/9先判断递归临界条件 当行row递归到9时 则表示已经出现了一个解了否则判断指定位置(row,col)是否已经有数字了如果已经有数字了 直接跳过当前位置 向下一个位置继续递归即可否则 循环数字1-9 判断指定位置能够填入的数字(1-9中的哪个数字) 将其填入再向下一个位置继续递归即可当一种填法行不通时 必须要将当前位置填入的数字清空后 再向上回溯*/private static void solve(int row, int col) {if(row == 9){ //判断递归临界条件count++;System.out.println("第" + count + "个解");printBoard();}else{//如果当前位置没有数字if(board[row][col] == 0){//就要填入1-9中满足条件的数字for(int num = 1; num <= 9; num++){//判断当前位置要填入的数字 是否满足条件/*条件：一行中没有与要填入的数字num相同的 并且 一列中没有与要填入的数字num相同的并且 当前方格所在的子方块中没有与要填入的数字num相同的*/if(!isExist(row, col, num)){//将满足条件的数字填入到指定位置board[row][col] = num;//向下递归 解决下一个格子solve(row + (col + 1) / 9, (col + 1) % 9);}board[row][col] = 0; //如果此处没解 必须清零此处的数字}}else{//已经存在一个已知数字 直接跳过去解决下一个格子solve(row + (col + 1) / 9, (col + 1) % 9);}}}/*判断当前位置要填入的数字 是否满足条件 如果指定范围中包含要添加的数字 则返回true若没有包含 表示可以将数字添加到指定方格中 返回false*/private static boolean isExist(int row, int col, int num) {//同一行中是否包含指定元素numfor(int c = 0; c < 9; c++){if(board[row][c] == num){return true;}}//同一列中是否包含指定元素numfor(int r = 0; r < 9; r++){if(board[r][col] == num){return true;}}//在子方格(九宫格)中是否包含指定元素num 若总共是9*9 则就有九个3*3的子方格int rowMin = 0; //子方格中最小行的编号，默认值为0int colMin = 0; //子方格中最小列的编号，默认值为0int rowMax = 0; //子方格中最大行的编号，默认值为0int colMax = 0; //子方格中最大列的编号，默认值为0//设置子方格中的最小行，最小列，最大行，最大列的值 即子方格的行 列范围if(row >= 0 && row <= 2){rowMin = 0;rowMax = 2;}if(row >= 3 && row <= 5){rowMin = 3;rowMax = 5;}if(row >= 6 && row <= 8){rowMin = 6;rowMax = 8;}if(col >= 0 && col <= 2){colMin = 0;colMax = 2;}if(col >= 3 && col <= 5){colMin = 3;colMax = 5;}if(col >= 6 && col <= 8){colMin = 6;colMax = 8;}//遍历子方格 判断其中是否包含指定元素numfor(int r = rowMin; r <= rowMax; r++){for(int c = colMin; c < colMax; c++){if(board[r][c] == num){return true;}}}//若以上条件都不满足 则返回false 表示指定位置可以填入数字return false;}//读取文件中的数独矩阵private static void readFile(String fileName) throws IOException {File file = new File(fileName);FileReader fr = new FileReader(file);BufferedReader br = new BufferedReader(fr);int row = 0;String line = null;while ((line = br.readLine()) != null){for(int col = 0; col < line.length(); col++){board[row][col] = Integer.parseInt(line.charAt(col) + "");}row++;}}//打印数独矩阵private static void printBoard() {for(int i = 0; i < 9; i++){for(int j = 0; j < 9; j++){System.out.print(board[i][j] + " ");}System.out.println();}}
}