`
mushme
  • 浏览: 790103 次
  • 性别: Icon_minigender_1
  • 来自: 西安
社区版块
存档分类
最新评论

用java解数独

 
阅读更多
自己写的,没解出来,搜到这个,没试过
package info.frady;

public class SudokuSolver {
	public void solveSudoku(char[][] board) {
		solve(board);
	}
	public boolean solve(char[][] board){
		for(int i=0;i<9;i++){
			for(int j=0;j<9;j++){
				if(board[i][j]=='.'){
					for(int k=0;k<9;k++){
						board[i][j]=(char) ('1'+k);
						if(isValid(board, i, j)&&solve(board))
							return true;
						board[i][j]='.';
					}
					return false;
				}
			}
		}
		return true;
	}
	private boolean isValid(char[][] board,int x,int y){
		for(int i=0;i<9;i++)
			if(i!=x&&board[i][y]==board[x][y])
				return false;
		for(int j=0;j<9;j++)
			if(j!=y&&board[x][j]==board[x][y])
				return false;
		for(int i=3*(x/3);i<3*(x/3+1);i++){
			for(int j=3*(y/3);j<3*(y/3+1);j++){
				if((i!=x||j!=y)&&board[i][j]==board[x][y])
					return false;
			}
		}
		return true;
	}
	public static void main(String[] args) {
		char[][] board={
				{'5','3','.','.','7','.','.','.','.'},
				{'6','.','.','1','9','5','.','.','.'},
				{'.','9','8','.','.','.','.','6','.'},
				{'8','.','.','.','6','.','.','.','3'},
				{'4','.','.','8','.','3','.','.','1'},
				{'7','.','.','.','2','.','.','.','6'},
				{'.','6','.','.','.','.','2','8','.'},
				{'.','.','.','4','1','9','.','.','5'},
				{'.','.','.','.','8','.','.','7','9'},
		};
		new SudokuSolver().solveSudoku(board);
		for(int i=0;i<9;i++){
			for(int j=0;j<9;j++)
				System.out.print(board[i][j]+" ");
			System.out.println();
		}
	}
}




这个是我写的,复杂的应该解不出来,因为算法中未包含某些特殊情况。
package info.frady;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * 
 *  2016.7.4
3 2 4 8 9 1 5 6 7
8 1 9 7 6 5 2 4 3
7 5 6 3 4 2 1 9 8
6 7 1 4 5 3 8 2 9
4 3 5 9 2 8 0 1 6
9 8 2 6 1 7 3 5 4
2 9 3 1 8 6 4 7 5
1 6 8 5 7 4 9 3 2
5 4 7 2 3 9 6 8 1

3 2 4 8 9 1 5 6 7
8 1 9 7 6 5 2 4 3
7 5 6 3 4 2 1 9 8
6 7 1 4 5 3 8 2 9
4 3 5 9 2 8 0 1 6
9 8 2 6 0 7 3 5 4
2 9 3 1 0 6 4 7 5
1 6 8 5 7 4 9 3 2
5 4 7 2 3 9 6 8 1

2 5 0 0 0 9 0 4 0
4 0 7 1 0 3 0 0 6
8 0 3 4 0 7 5 9 0
3 0 8 0 7 0 0 6 9
0 1 0 3 0 2 4 0 0
5 0 4 9 0 6 0 8 3
9 0 6 0 3 0 7 0 8
0 3 0 6 0 8 0 1 0
1 0 2 0 9 0 6 0 4

1 0 8 7 3 6 5 0 0
0 7 0 0 1 5 0 3 0
0 3 6 0 9 8 7 1 4
2 0 7 5 6 3 0 8 0
0 0 1 8 0 7 3 0 9
3 8 5 9 4 1 0 6 0
0 5 0 6 0 9 1 2 0
7 0 9 0 5 0 6 0 0
6 2 0 1 8 0 9 7 5
 */
public class Shudo {
	static boolean log=false;
	static int step=0;

	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		
		//1.接收数据进来,0为需要填写的数据
		Chess chesses[][]=new Chess[9][9];
		for(int i=0;i<9;i++){
			for(int j=0;j<9;j++){
				Chess c=new Chess();
				c.setPx(i);
				c.setPy(j);
				c.setNum(sc.nextInt());
				if(c.getNum()==0){
					step++;
				}
				chesses[i][j]=c;
			}
		}//数据接收完毕
		
		
		while(step>0){
			
			chesses=guessChess(chesses);//先计算出所有未确定格子的可能数字
			chesses=oneChooseLess(chesses);//运用唯一选择法进行扫描
			
		}
		
	
		if(isSloveRight(chesses)){
			System.out.println("Slove right!The answer is blow.");
			for(int i=0;i<9;i++){
				System.out.println(" ");
			for(int j=0;j<9;j++){
				Chess chess=chesses[i][j];
					System.out.print(" "+chess.getNum());
			}
			}
		}else{
			System.out.print("Slove error!");
		}
		
		
		
		sc.close();
	}
	
	public static boolean isSloveRight(Chess[][] chesses){//检查是否有重复的数据,以确认是否问题正确解决,应先检查是否有0
		if(!isSlove(chesses)){
			return false;//都没有解决呢,不要来混答案
		}
		for(int i=0;i<9;i++){
			for(int j=0;j<9;j++){
				Chess chess=chesses[i][j];
				for(int x=0;x<9;x++){
					if(x!=i && chesses[x][j].getNum()==chesses[i][j].getNum()){//同一列有相同的数
						return false;
					}
					if(x!=j && chesses[i][x].getNum()==chesses[i][j].getNum()){//同一行有相同的数
						return false;
					}
				}
				
				int startx=i/3*3;
				int starty=j/3*3;
				for(int m=startx;m<startx+3;m++){
					for(int n=starty;n<starty+3;n++){
						if(i!=m && j!=n && chesses[m][n].getNum()==chesses[i][j].getNum()){//同一个圈有相同的数
							return false;
						}
					}
					
				}
			}
		}
		return true;
	}
	public static boolean isSlove(Chess[][] chesses){//检查是否还有0,以确认是否完成问题解决
		for(int i=0;i<9;i++){
			for(int j=0;j<9;j++){
				Chess chess=chesses[i][j];
				if(chess.getNum()==0){//还有没有计算出的数字
					return false;
				}
			}
		}
		return true;
	}
	public static Chess[][] oneChooseLess(Chess[][] chesses){//只有一个候选数字,那数字就应该是这个数字
		for(int i=0;i<9;i++){
			for(int j=0;j<9;j++){
				Chess chess=chesses[i][j];
				if(log){
					System.out.println(i+","+j+":");
				}
				if(chess.getChooseNum()!=null && chess.getChooseNum().size()==1){
					if(log){
						System.out.println("--------------------------------------");
					}
					chess.setNum( chess.getChooseNum().get(0));
					step--;//确定一个,减去一个
					chesses=guessChess(chesses);
				}
			}
		}
		return chesses;
	}
	
	public static Chess[][] guessChess(Chess[][] chesses){//重新生成数独中每个未知棋子的可能棋子,当有任意棋子被新确定时,都应该执行此方法,以更新新局面
		
		for(int m=0;m<9;m++){
			for(int n=0;n<9;n++){
				Chess chess=chesses[m][n];
				//chess=guessChess(chess,chesses);
				List<Integer> sList=new ArrayList<Integer>();
				int px=chess.getPx();
				int py=chess.getPy();
				int num=chess.getNum();
				if(num==0){
					if(log){
						System.out.println("["+px+","+py+"]");
					}
					for(int i=0;i<9;i++){//行和列中已经有的数字,不应该被包含了
						Chess c1=chesses[px][i];//一行
						if(c1.getNum()!=0){
							sList.add(c1.getNum());//行中已经有的数
							if(log){
								System.out.println("["+px+","+i+"]添加了: "+c1.getNum());
							}
						}
						Chess c2=chesses[i][py];//一列
						if(c2.getNum()!=0){
							sList.add(c2.getNum());//列中已经有的数
							if(log){
								System.out.println("["+i+","+py+"]添加了: "+c2.getNum());
							}
						}
					}
					//圈中已经有的数字,也不应该被包含了
					int startx=px/3*3;
					int starty=py/3*3;
					for(int i=startx;i<startx+3;i++){
						for(int j=starty;j<starty+3;j++){
							if(chesses[i][j].getNum()!=0){
								sList.add(chesses[i][j].getNum());
							}
						}
						
					}
					
					List<Integer> mList=new ArrayList<Integer>();
					mList.add(1);
					mList.add(2);
					mList.add(3);
					mList.add(4);
					mList.add(5);
					mList.add(6);
					mList.add(7);
					mList.add(8);
					mList.add(9);
					List<Integer> rList=subList(mList,sList);
					if(log){
						System.out.print("["+m+","+n+"]可能的数字: ");
					
						for (Integer rc : rList) {
							System.out.print(" "+rc);
						}
						System.out.println(" ");
					}
					chess.setChooseNum(rList);
				}
			}
		}
		
		
		
		return chesses;//
	}
	
	//mList是所有的,sList是部分数据,返回未包含的数据
	public static List<Integer> subList(List<Integer> mList ,List<Integer> sList){
		List<Integer> rList=new ArrayList<Integer>();
		for (Integer mint : mList) {
			boolean has=false;
			for (Integer sint : sList) {
				if(sint.intValue()==mint.intValue() && sint!=0){
					has=true;
					break;
				}
				
			}
			if(!has){
				rList.add(mint);
			}
			
		}
		return rList;
		
	}
	

}
class Chess{
	int px;//第几列
	int py;//第几行
	int num;//0为未确定
	List<Integer> chooseNum;//可能是哪几个数字
	public int getPx() {
		return px;
	}
	public void setPx(int px) {
		this.px = px;
	}
	public int getPy() {
		return py;
	}
	public void setPy(int py) {
		this.py = py;
	}
	public int getNum() {
		return num;
	}
	public void setNum(int num) {
		this.num = num;
	}
	public List<Integer> getChooseNum() {
		return chooseNum;
	}
	public void setChooseNum(List<Integer> chooseNum) {
		this.chooseNum = chooseNum;
	}
	
	
	
}

分享到:
评论

相关推荐

    java解数独

    标题中的“Java解数独”指的是使用Java编程语言来实现数独问题的解决方案。数独是一种逻辑游戏,玩家需要在9x9的格子中填入数字,使得每一行、每一列以及每一个3x3的小九宫格内的数字都从1到9不重复。这个项目可能是...

    不同方法解数独 java代码

    内涵若干未解数独和已解数独 通过comment和uncomment Sudoku.java里的注解选择不同方法解数独 数独分2^2乘2^2的和3^2乘3^2的,注意BruteForceSolver 和StaticSolver 两个方法不要解2^2乘2^2以上的数独,否则太慢

    唯一解数独 生成算法 java

    在Java编程语言中实现唯一解数独的生成算法是一项挑战,涉及到深度优先搜索(DFS)、回溯等技术。 ### 数独生成算法原理 1. **挖洞思想**:数独生成过程中,通常采用“挖洞”策略。即从一个已填充好的完整数独开始...

    一个解数独的程序

    3. **编程语言**:解数独的程序可以使用多种编程语言实现,如Python、Java、C++等。Python因其简洁的语法和丰富的库常被用于快速原型开发,而Java和C++在效率上有优势,适用于大型或性能敏感的项目。 4. **用户界面...

    java超高速解数独软件 源码

    标题中的“java超高速解数独软件 源码”表明这是一个使用Java编程语言实现的高效数独求解器,其核心算法是Dancing Links。数独是一种逻辑推理游戏,玩家需要通过填充数字来完成一个9x9的网格,使得每一行、每一列...

    Java实现解数独的小程序共4页.pdf.zip

    在本压缩包中,我们关注的是一个使用Java编程语言实现的解数独小程序。数独是一种逻辑推理游戏,玩家需要填充一个9x9的网格,使得每一行、每一列以及每一个3x3的小宫格(也称为宫)都包含数字1至9,且每个数字在每个...

    java自动解数独问题

    1、在网页上发现一个数独游戏,工作闲时无聊,写了一份代码用来解数独难题,测试下来容易的数独没啥问题,复杂的可能会遇到所有未知值的单元格都找不到唯一值的情况,需要假设值的无法解答。 2、思路: (1)定义...

    Java实现解数独的小程序

    最近在学习Java,然后上个月迷上了九宫格数独,玩了几天,觉得实在有趣,就想着能不能用编程来解决,于是就自己写了个,还真解决了...下面这篇文章就给大家主要介绍了Java实现解数独的小程序,需要的朋友可以参考借鉴。

    解数独的---APP

    本来写了一个C语言纯代码的解数独代码,运行前需要修改数组的元素(将题目输入进去),但是感觉用户体验不好,想做出一个使用移动平台的APP在手机运行。在此分享给大家。本软件解数独分两部分,一部分是通过数独的...

    解数独的java源码

    该源码仅有150行,可以对指定的数独题解出结果,并打印到控制台。

    数独解题算法,java代码,采用回溯+递归的做法,仅供学习

    数独的算法,把数独题按照二位数组的方式填入到代码中的original,并复制一个到sudoku,然后直接...提供了java的源代码,可以为长期受数独大坑困扰的人民服务,祝大家早日脱坑,也为学生朋友提供回溯+递归算法的学习。

    回溯法解数独游戏

    这种游戏具有唯一解,因此非常适合用回溯法来求解。 回溯法的基本思想是试探性地进行解答,如果发现当前的尝试无法得到正确的解,就撤销最近的决策,尝试其他的可能性,直到找到解决方案或确定无解。在数独问题中,...

    回溯解数独算法

    在实际编程实现中,可以使用二维数组表示数独网格,用一个循环结构来遍历每个空格,然后用递归函数处理回溯过程。在递归函数中,可以先检查当前数字是否合法,如果合法就继续填充下一个空格;如果不合法,就回溯至上...

    java回溯算法解数独问题

    "java回溯算法解数独问题" java回溯算法是一种常用的算法,可以用来解决数独问题。数独问题是指在一个9x9的矩阵中,填充数字1-9,使得每行、每列、每个3x3的子矩阵中数字不重复。java回溯算法的基本思路是,从第0行...

    数独逻辑问题的实现

    2. 剪枝策略:在回溯过程中,通过一些启发式规则(如唯一候选数、隐含数等)提前排除不可能的选项,减少无效尝试,提高解题效率。 三、Java实现 1. 数据结构:使用二维数组或ArrayList来表示数独盘面,每个元素可以...

    java版本破解新浪验证码程序

    本篇文章将详细探讨Java版本的新浪验证码破解程序的相关知识点。 首先,我们要理解验证码的工作原理。验证码通常包含一些扭曲的字母、数字或者图像,用户需要正确识别并输入这些字符才能继续操作。新浪验证码可能...

    java使用回溯法求解数独示例

    Java 使用回溯法求解数独示例 本文主要介绍了使用 Java 语言实现回溯法解决数独问题的方法。数独是一种非常流行的逻辑游戏,通过数字的排列来解决矩阵中的问题。回溯法是一种常用的解决数独问题的方法,通过递归和...

    用java写的数独游戏代码

    5. **算法**:解数独的主要算法有深度优先搜索(DFS)、回溯法等。当一个单元格为空时,尝试填入1到9的数字,如果填入的数字在整个棋盘上合法,则继续填充下一个单元格,否则回溯到上一步,尝试下一个数字。回溯法是...

Global site tag (gtag.js) - Google Analytics