华为OJ之Sudoku-Java

1.题目描述

2.基本思路

目前想到的是暴力求解。 （1）从第一行开始（第一行没找到，则第二行开始找，依此类推）找到第一个值为0的数的坐标(i,j)，然后记录该i行中已经出现过的数字，以及j列中已经出现的数字，还有当前坐标所在的小九宫格中已经出现的数字，把1-9中第一个尚未出现的数字填进去，如果这里没有找到一个尚未出现的数字，则返回失败。 （2）重复（1）的步骤寻找当前行下一个值为0的坐标，继续执行（递归）。 （3）当找到所有行结束都填满，则成功返回

3.实现代码

public class Main{ public static void main(String[] args){ Scanner sc=new Scanner(System.in); int[][] sudoku=new int[9][9]; for(int i=0;i<9;i++){ for(int j=0;j<9;j++){ sudoku[i][j]=sc.nextInt(); } } fillVancancy(sudoku,0); for(int i=0;i<9;i++){ for(int j=0;j<8;j++){ System.out.print(sudoku[i][j]+" "); } System.out.println(sudoku[i][8]); } } private static boolean fillVancancy(int[][] sudoku,int r) { if(r>8){ return true; } boolean findVancancy=false; int row=r; int col=0; for(int i=r;i<9;i++){ for(int j=0;j<9;j++){ if(sudoku[i][j]==0){ row=i; col=j; findVancancy=true; break; } } } if(findVancancy){ int[] used=new int[10]; for(int i=0;i<9;i++){ used[sudoku[row][i]]=1; used[sudoku[i][col]]=1; } int x=row/3; int y=col/3; for(int i=x*3;i<(x+1)*3;i++){ for(int j=y*3;j<(y+1)*3;j++){ used[sudoku[i][j]]=1; } } for(int i=1;i<10;i++){ if(used[i]!=1){ sudoku[row][col]=i; used[i]=1; if(fillVancancy(sudoku,r)){ return true; } sudoku[row][col]=0; used[i]=0; } } return false; }else{ return true; } } } 输入： 0 9 2 4 8 1 7 6 3 4 1 3 7 6 2 9 8 5 8 6 7 3 5 9 4 1 2 6 2 4 1 9 5 3 7 8 7 5 9 8 4 3 1 2 6 1 3 8 6 2 7 5 9 4 2 7 1 5 3 8 6 4 9 3 8 6 9 1 4 2 5 7 0 4 5 2 7 6 8 3 1 输出： 5 9 2 4 8 1 7 6 3 4 1 3 7 6 2 9 8 5 8 6 7 3 5 9 4 1 2 6 2 4 1 9 5 3 7 8 7 5 9 8 4 3 1 2 6 1 3 8 6 2 7 5 9 4 2 7 1 5 3 8 6 4 9 3 8 6 9 1 4 2 5 7 9 4 5 2 7 6 8 3 1