The Java implementation solves the world's most difficult problem
- 2020-04-01 03:37:03
- OfStack
A Finnish mathematician has spent three months designing the world's most difficult sudoku game, and it has only one answer. Inkala says only the fastest and brightest minds can crack the game.
Today, a tencent news that the Chinese old man three days to crack the world's most difficult jiugong, although the final old man is changed a number, but I was interested in a moment, want to solve the problem through a computer program, so in the dormitory for an afternoon, finally successfully solved, the program source code as follows.
package numberGame;
public class Point {
private int col;//The line number < br / >
private int row;//Column number < br / >
private boolean flag;//True is not set. < br / >
private int value;
//Construct point
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;
}
//Determine if there is the same element
in cell 3 by 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;
}
//Determines if there is the same element
on the column
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) {//Rows change, columns change
return false;
}
}
}
return true;
}
//Determines if there is the same element
on the row
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) {//Column edge, row unchanged
return false;
}
}
}
return true;
}
}
- � the main program
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++) {//Add one to the value of the position to which you are backing. < br / >
numMat[i][j].setValue(v);
if (numMat[i][j].canHere(numMat)) {//Satisfy the condition, no conflict. < br / >
numMat[i][j].changeFlag();//Change the flag to false. Indicates that it has been set. < br / >
break;
}else{//Satisfy no condition, conflict. The value is added once by itself
}
while(v == 9){//If 1-9 does not meet the requirements, first reset the standard to 0, and back one space, to the back to the position of the value of a plus one (when the value of the back position is not 9, and ensure that the back position is not the original point of the nine-cell). < br / >
numMat[i][j].setValue(0);
j--;
if(j==-1){
i--;j=8;
}
while(al.contains(numMat[i][j])){//If you fall back to the original point of the lattice, continue to fall back until the point is not itself out of while. < br / >
j--;
if(j==-1){
i--;j=8;
}
}
numMat[i][j].changeFlag();//Will be marked
v = numMat[i][j].getValue();
}
}
}
j++;
if(j==9){
j=0;i++;//Here I ++ may add I to itself as 9, so I! =9 determines
}
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(" Please enter the point information ( i The line Numbers , j Column number v Value) , End of input 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("rn-------- ┼ --------- ┼ --------- ┤ ");
else
System.out.println();
}
}
}
-- run the program
Please enter the point information in the format (I row number, j column number v value), and enter over: I j v at the end of the input
0 0 8
1 2 3
1 3 6
2 1 7
2 April 9
June 2
3 1 5
3 5 7
4 April 4
4 5 5
4 June 7
5 3 1
5 July 3
6 2 1
6, 7
6 August 8
7 2 8
7 3 5
7 July 1
8 1 9
8 June 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 | 3 & 4 have spent 6 8 |
4 3 8 | 5 2 6 | 9 1 7 |
7 9 | 3 & 6 have spent 1 8 | 4 5 2 |
- � ┼ -- ┼ - ┤