网站建设技术开发,srm系统,ftp上传php网站,长沙做网站公司题目#xff1a;给定一个九行九列矩阵#xff0c;填充矩阵元素#xff0c;要求#xff1a; 1、每一行每一列#xff0c;每个小九宫格#xff08;图片画粗的地方就是#xff09;不能包含相同元素 2、每一行#xff0c;每一列#xff0c;每个小九宫格均会完整出现1-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(col1)%9行的更新更新行必须将col递归到当前行的末尾时才能更新 更新为rowrow(col1)/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();}}
}
