数独游戏

数独游戏

/*

• 你一定听说过“数独”游戏。
  如下图所示，玩家需要根据9×9盘面上的已知数字，推理出所有剩余空格的数字，
  并满足每一行、每一列、每一个同色九宫内的数字均含1-9，不重复。
  数独的答案都是唯一的，所以，多个解也称为无解。
  本图的数字据说是芬兰数学家花了3个月的时间设计出来的较难的题目。
  但对会使用计算机编程的你来说，恐怕易如反掌了。
  本题的要求就是输入数独题目，程序输出数独的唯一解。我们保证所有已知数据的格式
  都是合法的，并且题目有唯一的解。
  格式要求，输入9行，每行9个数字，0代表未知，其它数字为已知。
  输出9行，每行9个数字表示数独的解。
  有图
  005300000
  800000020
  070010500
  400005300
  010070006
  003200080
  060500009
  004000030
  000009700
  */

package _8dfs;

import java.util.Scanner;
public class a数独游戏之模板 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
   Scanner sc=new Scanner(System.in);
    char[][]table=new char[9][];
    for(int i=0;i<9;i++) {
    table[i]=sc.nextLine().toCharArray();//输入字符串数字
    }
         dfs(table, 0,0);
	}

	private static void dfs(char[][] table, int x, int y) {//123代码模板
		//1 出口
		if (x == 9) {
			print(table);// 打印表
			System.exit(0);// 退出
		}
        //2 dfs
		if (table[x][y] == '0') {// 虚位以待
			for (int k = 1; k < 10; k++) {// 1到9随便填数字
				if (check(table, x, y, k)) {// 检查行，y列是否有这个数字
					table[x][y] = (char) ('0' + k);// 如果没有则把K数字填进去
					dfs(table, x + (y + 1) / 9, (y + 1) % 9);// 处理下一个状态
				}
			}
			table[x][y] = '0';// 回溯(就是当前状态走不通，有相同的数字了)
		} else {// 3处理下一个状态
			dfs(table, x + (y + 1) / 9, (y + 1) % 9);
		}
	}

	private static void print(char[][] table) {
		//把没一行打出来
		// TODO Auto-generated method stub
		for(int i=0;i<9;i++) {
			System.out.println(new String(table[i]));
		}
}
	private static boolean check(char[][] table, int i, int j, int k) {
		// TODO Auto-generated method stub
		//检查同行和同列
		for(int l=0;l<9;l++) {
			if(table[i][l]==(char)('0'+k)) {
				return false;
			}
			if(table[l][j]==(char)('0'+k)) {
				return false;
			}
		}//检查小九宫格
		for(int l=(i/3)*3;l<(i/3+1)*3;l++) {//(i/3)*九宫格的起点
			for(int m=(j/3)*3;m<(j/3+1)*3;m++) {
				if(table[l][m]==(char)('0'+k)) {
					return false;
				}
			}	
		}
	return true;
	}

}

本文地址：https://blog.csdn.net/weixin_45952706/article/details/107900824