用java解数独
其实也就是用到了回溯算法。
回溯算法也叫试探法,它是一种系统地搜索问题的解的方法。回溯算法的基本思想是:从一条路往前走,能进则进,不能进则退回来,换一条路再试。
首先定义一个Sudoku类,用来保存和处理9*9的数组
import java.util.ArrayList;
import java.util.List;
/**
* Created shellingford on 2017/3/4.
*/
public class Sudoku {
private int[][] src;
private List<IRule> ruleList = new ArrayList<>();
private List<Result> resultList = new ArrayList<>();
private boolean findOne = true;
/**
* 判断是否符合规则
* @param x
* @param y
* @return
*/
private boolean check(int x,int y){
if(ruleList.size()>0){
for (IRule iRule : ruleList) {
boolean flag=iRule.check(src,x,y);
if(flag==false){
return false;
}
}
}
return true;
}
public Result backTrace(int x,int y){
if(x==8 && y==9){
//已经解出答案
Result result = new Result(src,x,y);
resultList.add(result);
return result;
}
//行末换行
if(y==9){
x++;
y=0;
}
if(src[x][y]==0){
//该值可以替换
for (int i = 1; i <=9 ; i++) {
//先暂时赋值
src[x][y] = i;
if(check(x,y)){
//如果没有问题
Result result = backTrace(x,y+1);
if(result.isSuccess() && findOne){
//只要找一个答案 并且已经找到
return result;
}
}
src[x][y]=0;
}
//已经替换完所有的可能了,还是没有正确的
return new Result(x,y);
}else{
//固定值,不能变换
Result result = backTrace(x,y+1);
return result;
}
}
public List<Result> getResultList() {
return resultList;
}
public void addRule(IRule rule){
ruleList.add(rule);
}
public void clearRule(){
ruleList.clear();
}
public Sudoku(String[] str){
int[][] x=new int[9][9];
for (int i = 0; i <9 ; i++) {
for (int j = 0; j <9 ; j++) {
x[i][j]=Integer.parseInt(str[i].charAt(j)+"");
}
}
src=x;
}
public Sudoku(int[][] x){
src=x;
}
public void display(){
for (int i = 0; i <src.length ; i++) {
for (int j = 0; j <src[i].length ; j++) {
System.out.print(src[i][j]);
}
System.out.println();
}
}
public boolean isFindOne() {
return findOne;
}
public void setFindOne(boolean findOne) {
this.findOne = findOne;
}
}
可以看到主要的解题算法在backTrace函数中,通过不断尝试,正确的则继续调用自身,错误的则返回上层尝试其他数值。
check方法用来判断当前数组是否符合规范,这里为了扩展一些其他特殊数独规则,使用了接口,把判断依据放入了ruleList里面。
接着看一下规则接口
/**
* Created shellingford on 2017/3/4.
* 数独规则接口
*/
public interface IRule {
public boolean check(final int[][] src,int x,int y);
}
只是简单的定义入参,和判断返回boolean值
接着是基础的规则,横竖判断不能重复
import java.util.ArrayList; import java.util.List; /** * Created shellingford on 2017/3/4. * 行列规则 */ public class BaseSudokuRule implements IRule { private final boolean isX; public BaseSudokuRule(boolean isX) { this.isX = isX; } @Override public boolean check(int[][] src, int x, int y) { if(isX){ //判断X List<Integer> list = new ArrayList<>(9); for (int i = 0; i <9 ; i++) { if(src[i][y]!=0){ Integer one = new Integer(src[i][y]); if(list.contains(one)){ return false; } list.add(one); } } }else{ //判断Y List<Integer> list = new ArrayList<>(9); for (int i = 0; i <9 ; i++) { if(src[x][i]!=0){ Integer one = new Integer(src[x][i]); if(list.contains(one)){ return false; } list.add(one); } } } return true; } }
还有3*3不能重复规则
import java.util.ArrayList; import java.util.List; /** * Created shellingford on 2017/3/4. * 3*3规则 */ public class SubSudokuRule implements IRule{ @Override public boolean check(int[][] src, int x, int y) { int startX=x/3; int startY=y/3; List<Integer> list = new ArrayList<>(9); for (int i = startX*3; i <startX*3+3 ; i++) { for (int j = startY*3; j <startY*3+3 ; j++) { if(src[i][j]!=0){ Integer one = new Integer(src[i][j]); if(list.contains(one)){ return false; } list.add(one); } } } return true; } }以及保存正确结果的返回对象
/** * Created shellingford on 2017/3/4. * 数独解析结果 */ public class Result { private int x; private int y; private int[][] src; private boolean success=true; public boolean hasNext(){ if(x==8 && y>=9){ return false; } return true; } public int getX() { return x; } public int getY() { return y; } public int[][] getSrc() { return src; } public boolean isSuccess() { return success; } public void display(){ if(src!=null){ for (int i = 0; i <src.length ; i++) { for (int j = 0; j <src[i].length ; j++) { System.out.print(src[i][j]); } System.out.println(); } } } public Result(int x,int y){ this(null,x,y); } public Result(int[][] data,int x,int y){ this.x=x; this.y=y; if(data==null){ success=false; }else{ src=new int[9][9]; for (int i = 0; i <9 ; i++) { for (int j = 0; j <9 ; j++) { src[i][j]=data[i][j]; } } } } }
可以额外增加规则,例如与之上下左右相邻的总和等于多少的规则
import java.util.ArrayList; import java.util.List; /** * Created shellingford on 2017/3/4. * 相邻四格之和规则 */ public class SumRule implements IRule{ private final int destX; private final int destY; private final int sum; public SumRule(int destX, int destY, int sum) { this.destX = destX; this.destY = destY; this.sum = sum; } @Override public boolean check(int[][] src, int x, int y) { //首先判断是否相邻 boolean needCheck=false; if(destX == x && destY==y){ needCheck=true; }else if(destX==x){ if(destY==y-1 || destY==y+1){ needCheck=true; } }else if(destY==y){ if(destX==x-1 || destX==x+1){ needCheck=true; } } if(needCheck==false){ //这里是因为变动数据并不影响这个规则,所以返回检查通过 return true; } List<Integer> list = new ArrayList<>(); list.add(src[destX-1][destY]); list.add(src[destX+1][destY]); list.add(src[destX][destY]); list.add(src[destX][destY+1]); list.add(src[destX][destY-1]); int sum=0; for (Integer integer : list) { if(integer==0){ //这里是因为有存在未填充的数据,所以不用检查 return true; } sum=sum+integer; } return this.sum==sum; } }
最后是main函数调用
import java.util.List; /** * Created shellingford on 2017/3/4. */ public class Demo { public static void main(String[] args) { String x[]={ "001000500", "020000010", "500000009", "000000000", "000000000", "000000000", "900000004", "010000060", "004000100" }; Sudoku sudoku = new Sudoku(x); //构造基础规则 BaseSudokuRule xRule = new BaseSudokuRule(true); BaseSudokuRule yRule = new BaseSudokuRule(false); sudoku.addRule(xRule); sudoku.addRule(yRule); SubSudokuRule subSudokuRule = new SubSudokuRule(); sudoku.addRule(subSudokuRule); //增加特殊规则 sudoku.addRule(new SumRule(1,4,17)); sudoku.addRule(new SumRule(2,2,29)); sudoku.addRule(new SumRule(2,6,22)); sudoku.addRule(new SumRule(4,1,34)); sudoku.addRule(new SumRule(4,4,23)); sudoku.addRule(new SumRule(4,7,20)); sudoku.addRule(new SumRule(6,2,22)); sudoku.addRule(new SumRule(6,6,29)); sudoku.addRule(new SumRule(7,4,33)); sudoku.backTrace(0,0); List<Result> list = sudoku.getResultList(); for (Result result : list) { if(result.isSuccess()){ System.out.println("============"); result.display(); System.out.println("============"); } } } }
匿名
商学院
名人名言
论文服务