你一定听说过“数独”游戏。如【图1.png】，玩家需要根据9×9盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个同色九宫内的数字均含1-9，不重复。数独的答案都是唯一的，所以，多个解也称为无解。本图的数字据说是芬兰数学家花了3个月的时间设计出来的较难的题目。但对会使用计算机编程的你来说，恐怕易如反掌了。本题的要求就是输入数独题目，程序输出数独的唯一解。我们保证所有已知数据的格式都是合法的，并且题目有唯一的解。格式要求，输入9行，每行9个字符，，0代表未知，其它数字为已知。输出9行，每行9个数字表示数独的解。例如：输入（即图中题目）：005300000800000020070010500400005300010070006003200080060500009004000030000009700程序应该输出：145327698839654127672918543496185372218473956753296481367542819984761235521839764再例如，输入：800000000003600000070090200050007000000045700000100030001000068008500010090000400程序应该输出：812753649943682175675491283154237896369845721287169534521974368438526917796318452资源约定：峰值内存消耗 < 256M
CPU消耗 < 2000ms
解题思路： 数据量小，回溯法的效率是可观的。import java.util.Scanner;/** * * * 数独游戏 *测试数据1：0 0 5 3 0 0 0 0 08 0 0 0 0 0 0 2 00 7 0 0 1 0 5 0 04 0 0 0 0 5 3 0 00 1 0 0 7 0 0 0 60 0 3 2 0 0 0 8 00 6 0 5 0 0 0 0 90 0 4 0 0 0 0 3 00 0 0 0 0 9 7 0 0测试数据2：8 0 0 0 0 0 0 0 00 0 3 6 0 0 0 0 00 7 0 0 9 0 2 0 00 5 0 0 0 7 0 0 00 0 0 0 4 5 7 0 00 0 0 1 0 0 0 3 00 0 1 0 0 0 0 6 80 0 8 5 0 0 0 1 00 9 0 0 0 0 4 0 0 * */public class Main{public static boolean flag = false; // 标记是否已找到public static void main(String[] args){Scanner sc = new Scanner(System.in);int arr[][] = new int [10][10];for (int i = 1; i < arr.length; i++)for (int j = 1; j < arr[i].length; j++)arr[i][j] = sc.nextInt();sc.close();dfs(1, 1, arr);}private static void dfs(int x, int y, int[][] arr){if (flag) return ;if (x > 9) {output(arr); flag = true;return ;}if (y > 9){dfs(x+1, 1, arr);}else if (arr[x][y] != 0) dfs(x,y+1,arr);else{for (int i = 1; i < 10; i++){if (check(x, y, i, arr)){arr[x][y] = i;dfs(x, y+1, arr);arr[x][y] = 0;}}}}private static boolean check(int x, int y, int num, int[][] arr){// 检查x轴for (int i = 1; i < 10; i++){if (arr[x][i] == num) return false;}// 检查y轴for (int i = 1; i < 10; i++){if (arr[i][y] == num) return false;}// 检查九宫格for (int i = (x-1)/3*3+1; i <= (x-1)/3*3+3; i++){for (int j = (y-1)/3*3+1; j <= (y-1)/3*3+3; j++){if (arr[i][j] == num) return false;}}return true;}private static void output(int[][] arr){ for (int i = 1; i < arr.length; i++) {for (int j = 1; j < arr[i].length; j++){System.out.print(arr[i][j] + " ");}System.out.println(); }}}
没有预兆目的地在哪，前进的脚步不能停下，
