Leetcode37题，解数独

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

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

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
数独部分空格内已填入了数字，空白格用 ‘.’ 表示。

主要思想的话就是先创建三个数组来存储每一列每一行每一个块这个字符出现的情况，遍历数独，将每个位置存在的数存入数组，将’.‘所在的行列存入一个数组集合。之后调用递归，来对每一个’.'位置的字符进行尝试，如果尝试失败，则进行回溯。题解如下：

class Solution {private boolean[][] row = new boolean[9][9];private boolean[][] col = new boolean[9][9];private boolean[][][] block = new boolean[3][3][9];private boolean valid = false;private List<int[]> list = new ArrayList<>();public void solveSudoku(char[][] board) {for(int i = 0; i < 9;i++){for(int j = 0;j < 9; j++){if(board[i][j] == '.') list.add(new int[]{i,j});else{int digit = board[i][j] - '0' - 1;row[i][digit] = col[j][digit] = block[i/3][j/3][digit] = true;}}}dfs(board,0);}public void dfs(char[][] board,int num){if(num == list.size()){valid = true;return;}int[] temp = list.get(num);int i = temp[0] , j = temp[1];for(int n = 0;n < 9 && !valid ;n++){if(!row[i][n] && !col[j][n] && !block[i/3][j/3][n]){row[i][n] = col[j][n] = block[i/3][j/3][n] = true;board[i][j] = (char)(n + '0' + 1);dfs(board,num+1);row[i][n] = col[j][n] = block[i/3][j/3][n] = false;}}}
}

源自：fzzf的博客

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！