題目描述
數(shù)獨是一個非常有名的游戲懦窘。整個是一個9X9的大宮格询件，其中又被劃分成9個3X3的小宮格。要求在每個小格中放入1-9中的某個數(shù)字楞卡。要求是：每行霜运、每列、每個小宮格中數(shù)字不能重復(fù)蒋腮。 現(xiàn)要求用計算機求解數(shù)獨淘捡。（50分）
輸入描述:
輸入9行，每行為空格隔開的9個數(shù)字池摧，為0的地方就是需要填充的數(shù)字焦除。
輸出描述:
輸出九行，每行九個空格隔開的數(shù)字作彤，為解出的答案膘魄。
示例1
輸入
0 9 0 0 0 0 0 6 0
8 0 1 0 0 0 5 0 9
0 5 0 3 0 4 0 7 0
0 0 8 0 7 0 9 0 0
0 0 0 9 0 8 0 0 0
0 0 6 0 2 0 7 0 0
0 8 0 7 0 5 0 4 0
2 0 5 0 0 0 8 0 7
0 6 0 0 0 0 0 9 0
輸出
7 9 3 8 5 1 4 6 2
8 4 1 2 6 7 5 3 9
6 5 2 3 9 4 1 7 8
3 2 8 4 7 6 9 5 1
5 7 4 9 1 8 6 2 3
9 1 6 5 2 3 7 8 4
1 8 9 7 3 5 2 4 6
2 3 5 6 4 9 8 1 7
4 6 7 1 8 2 3 9 5
答案
import java.util.Scanner;
import java.util.ArrayList;
public class Main{
public static void main(String[] args){
Scanner in = new Scanner(System.in);
while(in.hasNext()){
int[][] A = new int[9][9];
for(int i =0;i<9;i++){
for(int j =0;j<9;j++){
A[i][j] = in.nextInt();
}
}
solvesudoku(A,0);
for(int i =0;i<9;i++){
for(int j =0;j<9;j++){
if(j != 8)
System.out.print(A[i][j] + " ");
else
System.out.print(A[i][j]);
}
if(i != 8)
System.out.println();
}
}
}
static boolean solvesudoku(int[][] sd,int index){
if(index == 81)
return true;
int x = index/9;
int y = index%9;
if(sd[x][y]==0){
for(int n=1;n<=9;n++){
sd[x][y] = n;
if(CheckrowAndcol(sd,x,y,n) && CheckGrid(sd,x,y,n))
if(solvesudoku(sd,index+1))
return true;
sd[x][y] = 0;
}
}else
return solvesudoku(sd,index+1);
return false;
}
// 判斷 n 所在的行列是否包含 n
static boolean CheckrowAndcol(int[][] sd,int x ,int y,int n){
// x 行
for(int j=0;j<9;j++){
if(j!=y && sd[x][j] ==n )
return false;
}
// y列
for(int i=0;i<9;i++){
if(i!=x && sd[i][y]==n )
return false;
}
return true;
}
// 判斷所在的方格是否包含 n
static boolean CheckGrid(int[][] sd,int x,int y,int n){
// 根據(jù)x y的坐標(biāo)求其所在方格的左上坐標(biāo)和右下坐標(biāo)表示不好想。
for(int i = (x/3)*3;i<(x/3+1)*3;i++){
for(int j=(y/3)*3;j<(y/3+1)*3;j++){
if(i!=x && j!=y && sd[i][j]==n)
return false;
}
}
return true;
}
}
