Java解世界最難九宮格問(wèn)題
2018-07-20 來(lái)源：編程學(xué)習(xí)網(wǎng)
芬蘭數(shù)學(xué)家因卡拉花費(fèi)3個(gè)月設(shè)計(jì)出了世界上迄今難度最大的數(shù)獨(dú)游戲，而且它只有一個(gè)答案。因卡拉說(shuō)只有思考能力最快、頭腦最聰明的人才能破解這個(gè)游戲。
今日，一則騰訊的新聞稱中國(guó)老頭三天破解世界最難九宮格，雖然最后老人是改了一個(gè)數(shù)字，但是引起本人一時(shí)興趣，想通過(guò)計(jì)算機(jī)程序求解該問(wèn)題，于是在宿舍呆了一下午，終于成功求解，程序源碼如下。
package numberGame;
public class Point {
private int col;// 行號(hào)
private int row;// 列號(hào)
private boolean flag;// 真為未設(shè)置。
private int value;
// 構(gòu)造點(diǎn)
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();//改變標(biāo)記為假。表示已設(shè)置過(guò)。
break;
}else{//滿足不條件，沖突。value值自加一次
}
while(v == 9){//如果1-9都不能滿足要求，則先將本位重置為0，并回退一格,給回退到的位置的值加一（當(dāng)回退位置的值不為9時(shí),并且保證回退到的位置不是九宮格原本的點(diǎn)）。
numMat[i][j].setValue(0);
j--;
if(j==-1){
i--;j=8;
}
while(al.contains(numMat[i][j])){//如果回退到的位置為九宮格本來(lái)的點(diǎn)時(shí)，繼續(xù)回退，直到不是本身的點(diǎn)時(shí)跳出while。
j--;
if(j==-1){
i--;j=8;
}
}
numMat[i][j].changeFlag();//將標(biāo)記
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("請(qǐng)按格式輸入點(diǎn)信息（i行號(hào), j列號(hào) v值）,輸入結(jié)束輸入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();
}
}
}
——-運(yùn)行程序
請(qǐng)按格式輸入點(diǎn)信息（i行號(hào),?j列號(hào)?v值）,輸入結(jié)束輸入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?|
——–┼———┼———┤
標(biāo)簽：
版權(quán)申明：本站文章部分自網(wǎng)絡(luò)，如有侵權(quán)，請(qǐng)聯(lián)系：west999com@outlook.com
特別注意：本站所有轉(zhuǎn)載文章言論不代表本站觀點(diǎn)！
本站所提供的圖片等素材，版權(quán)歸原作者所有，如需使用，請(qǐng)與原作者聯(lián)系。
