唯品会-数独-java

题目描述

数独是一个非常有名的游戏。整个是一个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)