本文共 2721 字，大约阅读时间需要 9 分钟。

题目描述

数独是一个非常有名的游戏。整个是一个9X9的大宫格，其中又被划分成9个3X3的小宫格。要求在每个小格中放入1-9中的某个数字。要求是：每行、每列、每个小宫格中数字不能重复。 现要求用计算机求解数独。

输入描述

输入9行，每行为空格隔开的9个数字，为0的地方就是需要填充的数字。

输出描述

输出九行，每行九个空格隔开的数字，为解出的答案。

示例

输入：0 9 0 0 0 0 0 6 08 0 1 0 0 0 5 0 90 5 0 3 0 4 0 7 00 0 8 0 7 0 9 0 00 0 0 9 0 8 0 0 00 0 6 0 2 0 7 0 00 8 0 7 0 5 0 4 02 0 5 0 0 0 8 0 70 6 0 0 0 0 0 9 0输出：7 9 3 8 5 1 4 6 28 4 1 2 6 7 5 3 96 5 2 3 9 4 1 7 83 2 8 4 7 6 9 5 15 7 4 9 1 8 6 2 39 1 6 5 2 3 7 8 41 8 9 7 3 5 2 4 62 3 5 6 4 9 8 1 74 6 7 1 8 2 3 9 5

import java.util.Scanner;public class T_77 {
   	public static void main(String[] args) {
   		// TODO Auto-generated method stub		Scanner sc = new Scanner(System.in);		int a[][] = new int[9][9];		for (int i = 0; i < 9; i++) {
   			for (int j = 0; j < 9; j++) {
   				a[i][j] = sc.nextInt();			}		}			backTrace(0,0,a);		}		/**     * 数独算法     *     * @param i 行号     * @param j 列号     */    public static void backTrace(int i, int j, int a[][]) {
           if (i == 8 && j == 9) {
               //已经成功了，打印数组即可            printArray(a);            return;        }         //已经到了列末尾了，还没到行尾，就换行        if (j == 9) {
               i++;            j = 0;        }         //如果i行j列是空格，那么才进入给空格填值的逻辑        if (a[i][j] == 0) {
               for (int k = 1; k <= 9; k++) {
                   //判断给i行j列放1-9中的任意一个数是否能满足规则                if (check(i, j, k, a)) {
                       //将该值赋给该空格，然后进入下一个空格                    a[i][j] = k;                    backTrace(i, j + 1, a);                    //初始化该空格                    a[i][j] = 0;                }            }        } else {
               //如果该位置已经有值了，就进入下一个空格进行计算            backTrace(i, j + 1, a);        }    }    /**     * 判断给某行某列赋值是否符合规则     *     * @param row    被赋值的行号     * @param line   被赋值的列号     * @param number 赋的值     * @return     */    private static boolean check(int row, int line, int number, int a[][]) {
           //判断该行该列是否有重复数字        for (int i = 0; i < 9; i++) {
               if (a[row][i] == number || a[i][line] == number) {
                   return false;            }        }        //判断小九宫格是否有重复        int tempRow = row / 3;        int tempLine = line / 3;        for (int i = 0; i < 3; i++) {
               for (int j = 0; j < 3; j++) {
                   if (a[tempRow * 3 + i][tempLine * 3 + j] == number) {
                       return false;                }            }        }        return true;    }	/**     * 打印矩阵     */    public static void printArray(int a[][]) {
           for (int i = 0; i < 9; i++) {
               for (int j = 0; j < 9; j++) {
                   if(j==8)                	System.out.println(a[i][j]);                else                	System.out.printf("%d ",a[i][j]);            }        }    }}

转载地址：http://sctez.baihongyu.com/