题目描述
数独是一个非常有名的游戏。整个是一个9X9的大宫格,其中又被划分成9个3X3的小宫格。要求在每个小格中放入1-9中的某个数字。要求是:每行、每列、每个小宫格中数字不能重复。 现要求用计算机求解数独。(50分)
输入描述:
输入9行,每行为空格隔开的9个数字,为0的地方就是需要填充的数字。
输出描述:
输出九行,每行九个空格隔开的数字,为解出的答案。
示例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){
// 根据x y的坐标求其所在方格的左上坐标和右下坐标表示不好想。
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;
}
}
参考:
编程题 数独(JAVA)