当前位置： 移动技术网 > IT编程>开发语言>Java > Java实现解出世界最难九宫格问题

Java实现解出世界最难九宫格问题

2019年07月22日  | 移动技术网IT编程  | 我要评论

芬兰数学家因卡拉花费3个月设计出了世界上迄今难度最大的数独游戏，而且它只有一个答案。因卡拉说只有思考能力最快、头脑最聪明的人才能破解这个游戏。

今日，一则腾讯的新闻称中国老头三天破解世界最难九宫格，虽然最后老人是改了一个数字，但是引起本人一时兴趣，想通过计算机程序求解该问题，于是在宿舍呆了一下午，终于成功求解，程序源码如下。

复制代码 代码如下:

package numbergame;

public class point {
    private int col;// 行号
    private int row;// 列号
    private boolean flag;// 真为未设置。
    private int value;
    // 构造点
    public point(int col, int row, boolean flag, int value) {
        super();
        this.col = col;
        this.row = row;
        this.flag = flag;
        this.value = value;
    }

    public void changeflag() {
        flag = !flag;
    }

    public boolean getflag() {
        return flag;
    }

    public int getvalue() {
        return value;
    }

    public void setvalue(int value) {
        this.value = value;
    }

    public boolean canhere(point[][] parr) {
        boolean cb = cancol(parr);
        boolean cr = canrow(parr);
        boolean cminiarr = canminiarr(parr);
        return cb && cr && cminiarr;
    }
    //判断在小3*3格子里是否有相同元素
    private boolean canminiarr(point[][] parr) {
        int coltemp = this.col % 3;
        int rowtemp = this.row % 3;

        for (int i = this.col - coltemp; i < col + (3 - coltemp); i++) {
            for (int j = this.row - rowtemp; j < row + (3 - rowtemp); j++) {
                if(i == this.col && j == this.row){
                    continue;
                }else{              
                    if(this.value == parr[i][j].getvalue()){
                        return false;
                    }               
                }
            }
        }
        return true;
    }

    // 判断列上是否有相同元素
    private boolean canrow(point[][] parr) {
        for (int i = 0; i < 9; i++) {
            if (i == this.col) {
                continue;
            } else {
                if (this.value == parr[i][this.row].value) {// 行变，列不变
                    return false;
                }
            }
        }
        return true;
    }

    // 判断行上是否有相同元素
    private boolean cancol(point[][] parr) {
        for (int i = 0; i < 9; i++) {
            if (i == this.row) {
                continue;
            } else {
                if (this.value == parr[this.col][i].value) {// 列边，行不变
                    return false;
                }
            }
        }
        return true;
    }
}

—–主程序

复制代码 代码如下:

package numbergame;

import java.io.bufferedreader;
import java.io.ioexception;
import java.io.inputstreamreader;
import java.util.arraylist;

public class number99 {

    public static void main(string[] args) throws ioexception{
        point[][] nummat = new point[9][9];
        arraylist<point> al = new arraylist<point>();

        initnummat(nummat,al);

        setnum(nummat,al);
        printmat(nummat);
    }

    private static void setnum(point[][] nummat,arraylist<point> al) {
        int i = 0;
        int j = 0;
        do{
            if (nummat[i][j].getflag()) {
                for (int v = nummat[i][j].getvalue()+1; v <= 9; v++) {//给回退到的位置的值加一。
                    nummat[i][j].setvalue(v);
                    if (nummat[i][j].canhere(nummat)) {//满足条件，不冲突。
                        nummat[i][j].changeflag();//改变标记为假。表示已设置过。
                        break;
                    }else{//满足不条件，冲突。value值自加一次
                    }   

                    while(v == 9){//如果1-9都不能满足要求，则先将本位重置为0，并回退一格,给回退到的位置的值加一（当回退位置的值不为9时,并且保证回退到的位置不是九宫格原本的点）。
                        nummat[i][j].setvalue(0);
                        j--;
                        if(j==-1){
                            i--;j=8;
                        }
                        while(al.contains(nummat[i][j])){//如果回退到的位置为九宫格本来的点时，继续回退，直到不是本身的点时跳出while。
                            j--;
                            if(j==-1){
                                i--;j=8;
                            }
                        }
                        nummat[i][j].changeflag();//将标记
                        v = nummat[i][j].getvalue();
                    }
                }           
            }
            j++;
            if(j==9){
                j=0;i++;//此处i++ 可能使i自加为9，故下面需要i!=9判断
            }
            if(i!=9){           
                while(al.contains(nummat[i][j])){
                    j++;
                    if(j==9){
                        j=0;i++;
                    }
                }
            }
        }while(i!=9);

    }

    public static void initnummat(point[][] nummat,arraylist<point> al) throws ioexception {
        for (int i = 0; i < nummat.length; i++) {
            for (int j = 0; j < nummat[i].length; j++) {
                nummat[i][j] = new point(i, j, true, 0);
            }
        }
        initnummat2(nummat, al);

    }

    public static void initnummat2(point[][] nummat, arraylist<point> al) throws ioexception {
        bufferedreader br = new bufferedreader(new inputstreamreader(system.in));
        string[] p = new string[3];
        string line=null;
        system.out.println("请按格式输入点信息（i行号, j列号 v值）,输入结束输入over: i j v ");

        while((line = br.readline())!=null){
            if(line.equals("over"))
                break;
            p = line.trim().split(" +");
            nummat[integer.parseint(p[0])][integer.parseint(p[1])].setvalue(integer.parseint(p[2]));
            nummat[integer.parseint(p[0])][integer.parseint(p[1])].changeflag();
            al.add(nummat[integer.parseint(p[0])][integer.parseint(p[1])]);
        }
    }

    public static void printmat(point[][] nummat) {
        system.out.println("--------┬---------┬---------┐");

        for (int i = 0; i < nummat.length; i++) {
            for (int j = 0; j < nummat[i].length; j++) {
                if ((j + 1) % 3 == 0)
                    system.out.print(nummat[i][j].getvalue() + " | ");
                else
                    system.out.print(nummat[i][j].getvalue() + "  ");
            }
            if ((i + 1) % 3 == 0)
                system.out.println("\r\n--------┼---------┼---------┤");
            else
                system.out.println();
        }
    }

}

——-运行程序

请按格式输入点信息（i行号, j列号 v值）,输入结束输入over: i j v
0 0 8
1 2 3
1 3 6
2 1 7
2 4 9
2 6 2
3 1 5
3 5 7
4 4 4
4 5 5
4 6 7
5 3 1
5 7 3
6 2 1
6 7 6
6 8 8
7 2 8
7 3 5
7 7 1
8 1 9
8 6 4
over
——–┬———┬———┐
8  1  2 | 7  5  3 | 6  4  9 |
9  4  3 | 6  8  2 | 1  7  5 |
6  7  5 | 4  9  1 | 2  8  3 |
——–┼———┼———┤
1  5  4 | 2  3  7 | 8  9  6 |
3  6  9 | 8  4  5 | 7  2  1 |
2  8  7 | 1  6  9 | 5  3  4 |
——–┼———┼———┤
5  2  1 | 9  7  4 | 3  6  8 |
4  3  8 | 5  2  6 | 9  1  7 |
7  9  6 | 3  1  8 | 4  5  2 |
——–┼———┼———┤

您可能感兴趣的文章:

如对本文有疑问， 点击进行留言回复！！

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网