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