欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

数独游戏

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

数独游戏

/*

  • 你一定听说过“数独”游戏。
    如下图所示,玩家需要根据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