实现的java代码如下（该算法只是将结果打印输出，并没有对原数组实现更改）：
//判断a[i][j]取值val是否有效
public boolean isValid(int[][] a, int i, int j, int val){
//判断是否跟同行冲突
for(int j1=0;j1<9;j1++){
if(a[i][j1]==val)
return false;
}
//判断是否跟同列冲突
for(int i1=0;i1<9;i1++){
if(a[i1][j]==val)
return false;
}
//找出a[i][j]所在的九宫格
int i1 = 0, j1 = 0;
boolean flag = true;
for(i1=0;i1<3&&flag;i1++){
if(!(i>=i1*3&&i<3*(i1+1)))
continue;
for(j1=0;j1<3;j1++){
if(j>=j1*3&&j<3*(j1+1)){
flag = false;
break;
}
}
}
i1--;
//判断值是否跟所在九宫格冲突
for(int i2=3*i1;i2<3*(i1+1);i2++){
for(int j2=3*j1;j2<3*(j1+1);j2++){
if(a[i2][j2]==val)
return false;
}
}
return true;
}
//打印数独
public void printMatrix(int[][] a){
for(int i=0;i<9;i++){
for(int j=0;j<9;j++){
System.out.print(a[i][j]+" ");
}
System.out.println();
}
}
//回溯法求解数独
public void shuDu(int[][] a, int i, int j){
if(i==8&&j>=9){
printMatrix(a);
return;
}
if(j==9){
j=0;
i++;
}
if(a[i][j]==0){
for(int k=1;k<=9;k++){
if(isValid(a,i,j,k)){
a[i][j] = k;
//向下继续找
shuDu(a,i,j+1);
//如果没有找到全部答案将a[i][j]的值恢复
a[i][j] = 0;
}
}
}else{
shuDu(a,i,j+1);
}
}
算法调用示例如下：
public static void main(String[] args) {
Solution solu = new Solution();
int ma1[][]={
{0,3,0,0,0,5,0,6,0},
{0,1,0,0,0,3,0,8,0},
{0,4,0,0,0,0,0,0,7},
{0,0,7,0,2,4,0,0,0},
{5,0,0,0,9,0,0,0,0},
{0,8,0,3,0,0,5,0,0},
{0,0,0,8,0,0,0,0,0},
{0,0,9,0,0,0,0,7,3},
{0,5,0,9,0,0,0,0,2}};
int[][] sudoku = {
{8,0,0,0,0,0,0,0,0},
{0,0,3,6,0,0,0,0,0},
{0,7,0,0,9,0,2,0,0},
{0,5,0,0,0,7,0,0,0},
{0,0,0,0,4,5,7,0,0},
{0,0,0,1,0,0,0,3,0},
{0,0,1,0,0,0,0,6,8},
{0,0,8,5,0,0,0,1,0},
{0,9,0,0,0,0,4,0,0}};
solu.shuDu(sudoku, 0, 0);
}
不进行打印，实现更改数组的改进算法（数组为字符数组，可根据需要进行更改）：
public class Solution {
//判断a[i][j]取值val是否有效
public boolean isValid(char[][] a, int i, int j, char val){
//判断是否跟同行冲突
for(int j1=0;j1<9;j1++){
if(a[i][j1]==val)
return false;
}
//判断是否跟同列冲突
for(int i1=0;i1<9;i1++){
if(a[i1][j]==val)
return false;
}
//找出a[i][j]所在的九宫格
int i1 = 0, j1 = 0;
boolean flag = true;
for(i1=0;i1<3&&flag;i1++){
if(!(i>=i1*3&&i<3*(i1+1)))
continue;
for(j1=0;j1<3;j1++){
if(j>=j1*3&&j<3*(j1+1)){
flag = false;
break;
}
}
}
i1--;
//判断值是否跟所在九宫格冲突
for(int i2=3*i1;i2<3*(i1+1);i2++){
for(int j2=3*j1;j2<3*(j1+1);j2++){
if(a[i2][j2]==val)
return false;
}
}
return true;
}
//回溯法求解数独
public boolean shuDu(char[][] a, int i, int j){
if(i==8&&j>=9){
return true;
}
if(j==9){
j=0;
i++;
}
if(a[i][j]=='.'){
char ch = '1';
for(int k=0;k<9;k++){
if(isValid(a,i,j,(char)(ch+k))){
a[i][j] = (char) (ch+k);
//向下继续找
if(shuDu(a,i,j+1))
return true;
//如果没有找到全部答案将a[i][j]的值恢复
a[i][j] = '.';
}
}
}else{
if(shuDu(a,i,j+1))
return true;
}
return false;
}
public void solveSudoku(char[][] board) {
shuDu(board, 0, 0);
}
}
算法调用示例如下：
public class Main {
public static void main(String[] args) {
Solution solu = new Solution();
char[][] sudoku = {
{'8','.','.','.','.','.','.','.','.'},
{'.','.','3','6','.','.','.','.','.'},
{'.','7','.','.','9','.','2','.','.'},
{'.','5','.','.','.','7','.','.','.'},
{'.','.','.','.','4','5','7','.','.'},
{'.','.','.','1','.','.','.','3','.'},
{'.','.','1','.','.','.','.','6','8'},
{'.','.','8','5','.','.','.','1','.'},
{'.','9','.','.','.','.','4','.','.'}};
long start = System.nanoTime();
solu.solveSudoku(sudoku);
long time = System.nanoTime() - start;
System.out.println(time);
for(int i=0;i<9;i++){
for(int j=0;j<9;j++){
System.out.print(sudoku[i][j]+" ");
}
System.out.println();
}
}
}