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

芬兰数学家因卡拉花费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 |
——–┼———┼———┤

(0)

相关推荐

  • Java实现九宫格的简单实例

     Java实现九宫格的简单实例 九宫格:共有三行三列九个格子,从1到9共九个数字不重复地填入这九个格子中,条件是每行.每列.两个对角线上三个数字的和相等. 下面用Java实现九宫格: public class NineTable { public static void main(String[] args) { int arr[][] = new int[3][3]; int a = 2; int b = 3 / 2; for (int i = 1; i <= 9; i++) { arr[a+

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

    芬兰数学家因卡拉花费3个月设计出了世界上迄今难度最大的数独游戏,而且它只有一个答案.因卡拉说只有思考能力最快.头脑最聪明的人才能破解这个游戏. 今日,一则腾讯的新闻称中国老头三天破解世界最难九宫格,虽然最后老人是改了一个数字,但是引起本人一时兴趣,想通过计算机程序求解该问题,于是在宿舍呆了一下午,终于成功求解,程序源码如下. 复制代码 代码如下: package numberGame; public class Point {     private int col;// 行号     priv

  • Java详解数据类型的定义与使用

    目录 标识符和关键字 标识符 什么是标识符 标识符的定义规则 关键字 常量和变量 常量 变量 变量的声明格式 变量的声明 基本数据类型 整数类型 浮点类型 浮点类型常量 浮点类型变量 字符类型 字符型 字符串型 布尔类型 基本数据类型的转换 自动类型转换 强制类型转换 标识符和关键字 标识符 读音 biao zhi fu 什么是标识符 包.类.变量.方法…等等,只要是起名的地方,那个名字就是标识符 标识符的定义规则 四个可以:可以是数字.字母.下划线(_).美元符号($),我们一般起名尽量使用英

  • Java详解Swing中的几种常用按钮的使用

    目录 Swing中的常用按钮 AbstractButton的常用方法 JRadionButton(单选按钮) 单选按钮的构造方法 复选框(JCheckBox) 复选框的构造方法 组合框(JComboBox) 组合框的构造方法 下拉列表框的常用方法 小结 Swing中的常用按钮 在Swing中,常见的按钮组件有JButton,JCheckBox,JRadioButton等,它们都是抽象类AbstractButton类的直接或间接子类.在AbstractButton类中提供了按钮组件通用的一些方法.

  • Java压缩/解压文件的实现代码

    用java压缩/解压文件: import java.io.*; import java.awt.*; import java.awt.event.*; import java.util.*; import java.util.zip.*; import javax.swing.*; //从压缩包中提取文件 public class ZipExtractDemo extends JFrame{ JFileChooser fileChooser; //文件选择器 JTextField jtfTarg

  • 详解Java无需解压直接读取Zip文件和文件内容

    整理文档,搜刮出一个Java无需解压直接读取Zip文件和文件内容的代码,稍微整理精简一下做下分享. package test; import java.io.BufferedInputStream; import java.io.BufferedReader; import java.io.FileInputStream; import java.io.InputStream; import java.io.InputStreamReader; import java.util.zip.ZipE

  • Java 详解单向加密--MD5、SHA和HMAC及简单实现实例

    Java 详解单向加密--MD5.SHA和HMAC及简单实现实例 概要: MD5.SHA.HMAC这三种加密算法,可谓是非可逆加密,就是不可解密的加密方法. MD5 MD5即Message-Digest Algorithm 5(信息-摘要算法5),用于确保信息传输完整一致.MD5是输入不定长度信息,输出固定长度128-bits的算法. MD5算法具有以下特点: 1.压缩性:任意长度的数据,算出的MD5值长度都是固定的. 2.容易计算:从原数据计算出MD5值很容易. 3.抗修改性:对原数据进行任何

  • java基础-给出一个随机字符串,判断有多少字母?多少数字?

    我这里用到了String类中的toarray[]方法. 当看到字符串和判断,我想到之前学过的c语言中判断字符数组中元素,我就去API中找字符串转换成数组的方法 实现方法不唯一,此方法仅作初学者(自己)参考..... 在String类中一共找到三个转数组的方法 很显然,第三个是想要的方法. 实现代码: package com.string; import java.util.Scanner; public class Character_Judge { public static void mai

  • Java 详解异常的处理机制

    目录 1.异常概述与异常体系结构 1.1异常概述 1.2运行时异常与编译时异常 1.3异常体系结构 2.常见异常 1. ArrayIndexOutOfBoundsException 2.NullPointerException 3.ArithmeticException 4.ClassCastException 3.异常处理机制 3.1异常的抛出与捕获 3.2异常处理机制:try-catch-finally 5.用户自定义异常类 6.异常处理5个关键字 1.异常概述与异常体系结构 1.1异常概述

  • Java 详解如何获取网络接口信息

    前言 查看本机的网络接口信息,本文有详细的介绍哦. 代码 不废话,上代码. package com.hy.csdn.tools; import java.net.InetAddress; import java.net.NetworkInterface; import java.net.SocketException; import java.util.Enumeration; /** * @Program: hy-utils @ClassName: StuNetworkInterface @A

  • Java 详解如何从尾到头打印链表

    目录 1.题目 2.解法 2.1栈 2.2递归 3.复杂度 3.1栈 3.2递归 1.题目 输入一个链表的头节点,从尾到头反过来返回每个节点的值(用数组返回). 题目来源:力扣(LeetCode) 2.解法 2.1栈 栈的特点是先进后出,所以我们创建一个栈,逐个将节点压入栈内,然后建立一个数组,将栈内的节点数值逐个弹出 class Solution { public int[] reversePrint(ListNode head) { Stack<ListNode> stack = new

随机推荐