用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里面。

接着看一下规则接口

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);
        sudoku.setFindOne(false);
        //构造基础规则
        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("============");
            }
        }
    }
}