文档章节

数独算法

月生无界
 月生无界
发布于 2016/06/07 16:43
字数 2537
阅读 117
收藏 4
package test;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
import java.util.TreeSet;

/**
 * 数独算法
 * @author Mr li
 *
 */
public class Sudokus {
	//将数组分成九个宫,记录每个宫的横纵初始横纵坐标
	Map<Integer,Integer> row = new HashMap<Integer,Integer>();
	Map<Integer,Integer> line = new HashMap<Integer,Integer>();
	//数独数组长度
	static int le = 9;
	//一个坐标允许填的所有值
	static int aRow[] = {1,2,3,4,5,6,7,8,9};
	//初始化数组
	static int sudoku[][] = new int[le][le];
	//获取数独数组中所有为0的位置的坐标,并且存入一个map中
	TreeSet<String> zeroCoord = new TreeSet<String>();

	//thirdSolution方法需要
	static int testSudoku[][] = new int[le][le];
	static int isOk = 1;

	/**
	 * 位解:排除法,根据该坐标获取该坐标行,列,宫的所有数字,然后排除掉,如果该此时剩余唯一一个值,表示这个值为数独解
	 * @param sudoku 传入的数独数组
	 * @param zeroCoord 数组中为0的坐标,即需要解的所有坐标集
	 * @return
	 */
	public int firstSolution(int[][] sudoku,TreeSet<String> zeroCoord){
		System.out.println("firstSolution---start");
		//获取“0”的个数
		int zeroNum = zeroCoord.size();
		//转为数组再进行处理
		Object[] zCoord = zeroCoord.toArray();
		for(int i=0;i<zCoord.length;i++){
			String[] rlArr = zCoord[i].toString().split(",");
			int ro = Integer.parseInt(rlArr[0]);
			int li = Integer.parseInt(rlArr[1]);
			TreeSet<Integer> numCanSet = new TreeSet<Integer>();
			numCanSet = this.getNumCanSet(sudoku,ro,li);//根据坐标获取该坐标可填入的数组集
			if(numCanSet.size() == 1){
				sudoku[ro][li] = numCanSet.first();
				zeroCoord.remove(ro+","+li);//如果该坐标获取到解,则移除该坐标
				System.out.println("坐标:("+ro+","+li+") 值:"+numCanSet.first()+"剩余"+zeroCoord.size());//记录每次解值的坐标以及该坐标的值
			}else if(numCanSet.size() == 0){
				return -1;//出现悖论位
			}
		}
		System.out.println("firstSolution---end");
		if(zeroCoord.size() == zeroNum){
			return 0;//本次过程没有获得一个解
		}
		return 1;
	}
	/**
	 * 宫解:首先遍历一个宫内的九个坐标,并且获取每个坐标可填入的所有值,然后判断在本宫内,哪个值只出现了一次,表示该值只可以填入该坐标
	 * @param sudoku 传入的数独数组
	 * @param zeroCoord 数组中为0的坐标,即需要解的所有坐标集
	 * @return
	 */
	public int secondSolution(int[][] sudoku,TreeSet<String> zeroCoord){
		System.out.println("secondSolution---start");
		//获取“0”的个数
		int zeroNum = zeroCoord.size();
		for(int i=0;i<le;i++){
			//存入每个宫里面的1到9还没有填入的数字,并且存入,每个数字在本宫内可填入几次,如果是一次,表示获取到一个解
			Map<Integer,Integer> canInNum = new HashMap<Integer,Integer>();
			//存入每个宫里面的1到9还没有填入的数字,并且存入,遍历之下,每个数字可填入的最新坐标,然而我们依然只关心只有一个值的解,那么其坐标只存入一次
			Map<Integer,String> newCoord = new HashMap<Integer,String>();
			//获取宫的初始坐标
			int rowF = row.get(i);
			int lineF = line.get(i);
			//循环遍历宫内九个坐标		
			for(int m=0;m<3;m++){
				for(int n=0;n<3;n++){
					//每个坐标可填入的值的集
					TreeSet<Integer> setCan = new TreeSet<Integer>();
					int num = sudoku[rowF+m][lineF+n];
					if(num == 0){
						setCan = this.getNumCanSet(sudoku,rowF+m,lineF+n);
						if(setCan.size() == 0){
							return -1;//出现悖论位
						}
						for(int a : setCan){
							try {
								canInNum.put(a, canInNum.get(a)+1);
							} catch (Exception e) {
								canInNum.put(a, 1);
							}
							newCoord.put(a, (rowF+m)+","+(lineF+n));
						}
					}
				}
			}
			//遍历canInNum,获取只出现一次的值,以及该值的坐标
			for(int key : canInNum.keySet()){
				if(canInNum.get(key) == 1){
					String coord = newCoord.get(key);
					String[] coordArr = coord.split(",");
					int ro = Integer.parseInt(coordArr[0]);
					int le = Integer.parseInt(coordArr[1]);
					//将值填入数组中,同时将zeroNum减1
					sudoku[ro][le] = key;
					zeroCoord.remove(ro+","+le);
					System.out.println("坐标:("+ro+","+le+") 值:"+key+"剩余"+zeroCoord.size());
				}
			}
		}
		System.out.println("secondSolution---end");
		if(zeroCoord.size() == zeroNum){
			return 0;//本次过程没有获得一个解
		}
		return 1;
	}
	/**
	 * 双值位测解:获取某个只可以填入两个值的坐标,然后分别将此值填入其中,并继续解此数独,如果其中一个值填入数独中,出现错误,则可以确定另外一个值为正确值
	 * @param sudoku 传入的数独数组
	 * @param zeroCoord 数组中为0的坐标,即需要解的所有坐标集
	 * @return
	 */
	public int thirdSolution(int[][] sudoku,TreeSet<String> zeroCoord){
		System.out.println("thirdSolution---start");
		//获取“0”的个数
		int zeroNum = zeroCoord.size();
		Object[] zCoord = zeroCoord.toArray();
		for(int i=0;i<zCoord.length;i++){
			String[] rlArr = zCoord[i].toString().split(",");
			int ro = Integer.parseInt(rlArr[0]);
			int li = Integer.parseInt(rlArr[1]);
			TreeSet<Integer> numCanSet = new TreeSet<Integer>();
			numCanSet = getNumCanSet(sudoku,ro,li);//根据坐标获取该坐标可填入的数组集
			if(numCanSet.size() == 2){
				//建立一个set集,存放正确的坐标值
				TreeSet<Integer> trueSet = new TreeSet<Integer>();
				for(int q=0;q<2;q++){
					TreeSet<String> testZeroCoord = new TreeSet<String>();
					//测试数组建立
					int testSudoku[][] = new  int[sudoku.length][sudoku.length];
					for(int m=0;m<sudoku.length;m++){
						for(int n=0;n<sudoku[m].length;n++){
							testSudoku[m][n] = sudoku[m][n];
						}
					}
					int a = (int) numCanSet.toArray()[q];
					testSudoku[ro][li] = a;
					//调用测试方法,如果为1表示改值可填入,当然,如果最后两值判断都正确,则忽略该坐标,继续下一坐标
					testZeroCoord.addAll(zeroCoord);
					testZeroCoord.remove(ro+","+li);
					int r = this.isOk(testSudoku,testZeroCoord);
					if(r == 1){
						trueSet.add(a);
					}
					if(r == -1){
						return -1;
					}
				}
				//集长度为1,表示获取到正确解值
				if(trueSet.size() == 1){
					int a = trueSet.first();
					sudoku[ro][li] = a;
					zeroCoord.remove(ro+","+li);
					System.out.println("成功"+numCanSet.size()+"值位("+ro+","+li+"),值为:"+a+",剩余"+zeroCoord.size());
				}else{
					System.out.println("失败"+numCanSet.size()+"值位("+ro+","+li+"),值集为:"+numCanSet);
				}
			}

		}
		System.out.println("thirdSolution---end");
		if(zeroCoord.size() == zeroNum){
			return 0;
		}
		return 1;
	} 
	/**
	 * 获取该坐标可输入值集合,并返回
	 * @param ro 行坐标
	 * @param li 列坐标
	 * @return
	 */
	public TreeSet<Integer> getNumCanSet(int[][] sudoku,int ro,int li){
		TreeSet<Integer> setNo = new TreeSet<Integer>();
		TreeSet<Integer> setCan = new TreeSet<Integer>();
		//行数组
		int row[] = sudoku[ro];
		for(int i=0;i<le;i++){
			if(row[i] != 0){
				setNo.add(row[i]);	
			}
		}
		//列处理
		for(int j=0;j<le;j++){
			if(sudoku[j][li] != 0){
				setNo.add(sudoku[j][li]);	
			}
		}
		//宫处理
		int r = ro/3*3;//宫的初始行坐标
		int l= li/3*3;//宫的初始列坐标
		for(int m=0;m<3;m++){
			for(int n=0;n<3;n++){
				if(sudoku[r+m][l+n] != 0){
					setNo.add(sudoku[r+m][l+n]);
				}
			}
		}
		Object[] judgeArr = setNo.toArray();
		for(int a : aRow){
			boolean isA = true;
			for(Object b : judgeArr){
				if((int) b == a){
					isA = false;
					break;
				};
			}
			if(isA){
				setCan.add(a);
			}
		}
		return setCan;
	}
	/**
	 * 宫的横纵初始坐标
	 */
	public void rLInitialCoord(){
		//该循环表示九个宫的初始坐标都会分别存入row与line中,i对应的是一到九宫
		for(int i=0;i<le;i++){
			if(i<3){
				row.put(i, 0);
				line.put(i, i*3);
			}else if(i<6){
				row.put(i, 3);
				line.put(i, i%3*3);
			}else{
				row.put(i, 6);
				line.put(i, i%6*3);
			}
		}
	}
	/**
	 * 获取输入的数独,空值位用0表示,纯数字输入
	 */
	public void getInSudoku(){
		@SuppressWarnings("resource")
		Scanner sc = new Scanner(System.in);
		String sudokuIn = sc.next();
		if(sudokuIn.length() != 81){//判断输入的数组是否正确
			System.out.println("请输入正确的数组");
		}else{
			for(int i=0;i<le;i++){//遍历纯数字字符串,并且插入数独数组中
				for(int j=0;j<le;j++){
					int n = Integer.parseInt(sudokuIn.substring(le*i+j,le*i+j+1));
					sudoku[i][j] = n;
				}
			}
		}
	}
	/**
	 * 获取数独数组中所有为0的位置的坐标,并且存入一个map中,初始化zeroNum的值
	 */
	public void getAllZeroNumCoord(){
		for(int i=0;i<le;i++){
			for(int j=0;j<le;j++){
				if(sudoku[i][j] == 0){
					zeroCoord.add(i+","+j);
				}
			}
		}
	}
	/**
	 * 打印数独结果
	 */
	public void printSudoku(int[][] sudoku){
		for(int i=0;i<le;i++){
			int pr[] = sudoku[i];
			System.out.println(Arrays.toString(pr));
		}
	}
	/**
	 * 递归函数
	 */
	public void recursion(){
		int isSuccess = this.callBack();
		if(isSuccess == 1){
			this.recursion();
		}else{
			return;
		}
	}
	/**
	 * 递归函数中调用,返回1表示数独解成功,0表示还未完全解出,-1表示数独解失败
	 * @return
	 */
	public int callBack(){
		//为0的时候表示已经获取全部解,打印最终解
		if(zeroCoord.size() == 0){
			System.out.println("成功:");
			this.printSudoku(sudoku);
			return 0;
		}
		if(this.firstSolution(sudoku, zeroCoord) == 1){
			return 1;
		}else{
			if(this.secondSolution(sudoku, zeroCoord) == 1){
				return 1;
			}else{
				int thr = this.thirdSolution(sudoku, zeroCoord);
				if( thr == 1){
					return 1;
				}else if(thr == -1){
					System.out.println("成功:");
					this.printSudoku(testSudoku);
					return 0;
				}else{
					System.out.println("失败:");
					this.printSudoku(sudoku);
					return -1;
				}
			}
		}
	}
	/**
	 * 判断数独是否出现悖论位
	 * 0出现,1无错,-1填入测试值直接完成解数独
	 * @return
	 */
	public int isOk(int[][] sudoku,TreeSet<String> zeroCoord) {
		//将测试数据的初始化
		for(int m=0;m<le;m++){
			for(int n=0;n<le;n++){
				testSudoku[m][n] = sudoku[m][n];
			}
		}
		isOk = 1;
		this.testRecursion(zeroCoord);
		return isOk;
	}
	/**
	 * 递归函数
	 */
	public void testRecursion(TreeSet<String> testZeroCoord){
		int isSuccess = this.testCallBack(testZeroCoord);
		if(isSuccess == 1){
			this.testRecursion(testZeroCoord);
		}else{
			return;
		}
	}
	/**
	 * 递归函数中调用,返回1表示数独解成功,0表示还未完全解出,-1表示数独解失败
	 * @return
	 */
	public int testCallBack(TreeSet<String> testZeroCoord){
		//为0的时候表示已经获取全部解,打印最终解
		if(testZeroCoord.size() == 0){
			isOk = -1;
			return -1;
		}else{
			int fir = this.firstSolution(testSudoku, testZeroCoord);
			if(fir == 1){
				return 1;
			}else{
				if(fir == 0){
					int sec = this.secondSolution(testSudoku, testZeroCoord);
					if(sec == 1){
						return 1;
					}else{
						if(sec == -1){
							isOk = 0;
							return 0;
						}
					}
				}else{
					isOk = 0;
					return 0;
				}
			}
		}
		return 0;
	}
	/**
	 * main方法测试
	 * @param args
	 */
	public static void main(String[] args) {
		
		Sudokus sd = new Sudokus();
		//获取输入的数独数组
		sd.getInSudoku();
		//初始化数独需要填入的总个数以及其坐标
		sd.getAllZeroNumCoord();
		//宫的横纵初始坐标
		sd.rLInitialCoord();
		//递归函数解数独开始
		sd.recursion();
		System.exit(0);
	}
}

直接复制到java类中运行即可

键盘输入例子:001000600059002000400006002000870010200090007040053000800500006000100790004000500

如上,将每一行的数字全部输入,空值的位置用0表示

主要逻辑:

1、核心:三个主要解值方法,个人命名为位解,宫解,双值位测解,层级递进,第一个只有前一个方法失效,才调用下一个,每次解完如果成功,都需从第一个方法重新开始解。

    (1)位解:普通数独玩家逻辑,找出当前坐标位,行列宫内的所有数字,然后排出掉不可以填的,剩下的就是可以填的,如果可以填的数字个数刚好为1,成功获得一个解

    (2)宫解:以宫为单位,数独9*9八十一格,分为九个宫,宫解则是将该宫内的所有空值的坐标位可以填入的值全部取出来,然后判断在该宫内,是否存在某个数字,只出现一次,如此,即使在这个坐标位可以填入多个值,但是解依然是这个只出现一次的值

    (3)双值位测解:当位解与宫解都无法继续解出任何一个值的时候,调用此方法,找出某个只有两个可填值的坐标位,然后将两个值分别填入该坐标,进行位解与宫解,如果最后结果出现一个数字填入出现错误位,则另外一个为正确解,如果填入测试值的时候,数独直接全部解出,则将测试数组打印出来,结束程序

2、由于测试量不大,算法可能存在问题,单该算法应该可以解决大部分的数独,如果你发现任何问题,请告诉我,谢谢!

© 著作权归作者所有

月生无界
粉丝 9
博文 31
码字总数 40210
作品 0
广州
后端工程师
私信 提问
shenxgan/sudoku

数独生成与求解 记得第一次写数独的算法的时候是在大学期间,那时候闲来无事;在手机上玩着数独游戏,看着自己解不出来的题,想着是不是折腾折腾数独,写出一个求解数独的算法出来。 想到就做...

shenxgan
2017/04/28
0
0
请问各位大神在JAVA中同一个工程下的两个包之间如何实现数据传递?

该工程是关于数独的生成与破解,该两个包为"数独挖洞算法设计"跟“数独棋盘文件管理”。其中在包“数独挖洞算法设计”中我已实现了数独的生成与破解功能,并且用二维数组的形式跟字符数组的形...

桔子大人
2015/09/16
1K
3
数独完全解生成- 高效回溯算法

由于上篇的算法存在一些不足,我们不免要继续研究数独游戏的完全解,以获得更高效高质量的生成算法,对于完全解的生成过程,我们一般是采用回溯法来产生整个九宫格的所有的数据。而对于九九八...

9plus
2017/11/12
0
0
数独完全解生成-分组轮转算法

数独(日语:数独すうどく)是一种源自18世纪末的瑞士,后在美国发展、并在日本得以发扬光大的数学智力拼图游戏。拼图是九宫格(即3格宽×3格高)的正方形状,每一格又细分为一个九宫格。在每...

9plus
2017/11/12
0
0
zhangwanjun/sudoku

数独 基于JavaFX和DLX算法实现的数独游戏,可快速生成和解出数独。 操作 移动:方向键 (↑↓←→) 或鼠标。 输入:数字键。 功能 难度等级:简单、正常、困难、疯狂。 打开:接收外部已有数独...

zhangwanjun
2017/09/14
0
0

没有更多内容

加载失败,请刷新页面

加载更多

5.设计模式之四:抽象工厂模式【创建型模式】

前面介绍的工厂方法模式中考虑的是一类产品的生产,如畜牧场只养动物、电视机厂只生产电视机、计算机软件学院只培养计算机软件专业的学生等。 同种类称为同等级,也就是说:工厂方法模式只考...

Eappo_Geng
8分钟前
2
0
一个基于springSecurity的Json Web Token的实现

SecurityJwt 一个基于springSecurity的Json Web Token的实现 GitHub地址 提要 一、SpringSecurity Spring Security,一种基于 Spring AOP 和 Servlet 过滤器的安全框架。它提供全面的安全性解...

左羽
24分钟前
4
0
七牛云批量下载图片到本地

使用七牛云提供的下载工具批量下载 下载:https://pan.baidu.com/s/1kVcdFDH xp1p下载解压后,qiniu文件里有qshell.conf 和 qshell.exe两个文件,编辑qshell.conf`{"dest_dir": "F://qi......

闊苡訆涐囍醣
27分钟前
4
0
米联客(MSXBO) 基于VIVADO实现FPGA时序笔记之概述(一)

FPGA时序要满足要求,这个基本原理大家基本都知道,但是如何使用VIVADO IDE工具进行时序设计、时序分析、判断时序是否满足要求,这个对很多FPGA工程师来说,还是比较抽象,因为时序分析的工具...

msxbo
40分钟前
6
0
Centos7 命令行下kvm安装windows,linux

查看是否支持 egrep "svm|vmx" /proc/cpuinfo |uniq 安装软件 yum install libvirt -yyum -y install qemu-kvmsystemctl enable libvirtd && systemctl start libvirtd# 启动lib......

以谁为师
41分钟前
8
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部