编写一个程序，通过填充空格来解决数独问题。
一个数独的解法需遵循如下规则：
数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
空白格用 ‘.‘ 表示。
思路：可以用搜索的方法来实现，首先用三个boolean数组记录下该数字在某行、某列、某九宫格里面是否出现过。进入搜索判断该格子是否有数字，如果有就进入到右边的格子，如果没有就用1-9每个数字试一次，如果成功就往下走。如果该位置所有数字都无法填入，就退出返回。当搜索到最右边的格子，就到下一行；如果搜索到表格底部，就返回退出。
public void solveSudoku(char[][] board) { //分别为行、列、小九宫格记录用过的格子 boolean[][] rowUsed = new boolean[9][9]; boolean[][] colUsed = new boolean[9][9]; boolean[][][] boxUsed = new boolean[3][3][9]; for (int i = 0; i < board.length; i++) { for (int j = 0; j < board[0].length; j++) { //格子里的数字为1-9，下标为0-8，所以减1 int num = board[i][j] - ‘1‘; //如果是数字就设定为该格子有效 if (0 <= num && num < 9) { rowUsed[i][num] = true; colUsed[j][num] = true; boxUsed[i / 3][j / 3][num] = true; } } } recusiveSolveSudoku(board, rowUsed, colUsed, boxUsed, 0, 0); } private boolean recusiveSolveSudoku(char[][] board, boolean[][] rowUsed, boolean[][] colUsed, boolean[][][] boxUsed, int row, int col) { //如果列走到末尾则重置为零，同时设置到下一行 if (col == board[0].length) { col = 0; row++; //如果到最后一行说明该解有效 if (row == board.length) { return true; } } //如果该格子为空 if (board[row][col] == ‘.‘) { //从1-9一个个试 for (int num = 0; num < 9; num++) { //判断该位置用这个数字，行、列、九宫格内有无重复 boolean canUsed = !(rowUsed[row][num] || colUsed[col][num] || boxUsed[row / 3][col / 3][num]); if (canUsed) { //设为已用 rowUsed[row][num] = true; colUsed[col][num] = true; boxUsed[row / 3][col / 3][num] = true; //索引位置是0-8，加1变为1-9 board[row][col] = (char) (‘1‘ + num); //往下递归，如果该位置往下的搜索都能成功，则该位置的数字有效 if (recusiveSolveSudoku(board, rowUsed, colUsed, boxUsed, row, col + 1)) { return true; } //返回递归前状态 board[row][col] = ‘.‘; rowUsed[row][num] = false; colUsed[col][num] = false; boxUsed[row / 3][col / 3][num] = false; } } }else { //该位置有数字了，往右搜索 return recusiveSolveSudoku(board, rowUsed, colUsed, boxUsed, row, col + 1); } //如果所有数字都不能满足 return false; }
原文：https://www.cnblogs.com/RS-Sakura/p/13956258.html