Finnish mathematician Inkara spent three months designing the most difficult Sudoku puzzle in the world, and it has only one answer. Inkara said only the fastest thinkers and the brightest minds can crack the game.
Today, a piece of news from Tencent said that a Chinese old man cracked the world's most difficult nine-square grid in three days. Although the old man changed a number in the end, it aroused my interest and wanted to solve the problem through a computer program, so I stayed in the dormitory for an afternoon and finally solved it. Successfully solved, the program source code is as follows.
Copy the code code as follows:
package numberGame;
public class Point {
private int col;//line number
private int row;//column number
private boolean flag; // True is not set.
private int value;
//Construction 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;
}
//Judge whether there are the same elements in the small 3*3 grid
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;
}
// Determine whether there are the same elements in 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) {//The row changes, the column remains unchanged
return false;
}
}
}
return true;
}
// Determine whether there are the same elements 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 edges, rows unchanged
return false;
}
}
}
return true;
}
}
―The main program copy code is as follows:
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 returned to.
numMat[i][j].setValue(v);
if (numMat[i][j].canHere(numMat)) {//The conditions are met and there is no conflict.
numMat[i][j].changeFlag();//Change the flag to false. Indicates it has been set.
break;
}else{//Satisfy no condition, conflict. The value value increments itself once
}
while(v == 9){//If 1-9 cannot meet the requirements, reset the home position to 0 first, and go back one space, and add one to the value of the returned position (when the returned position is When the value is not 9, it is guaranteed that the position returned to is not the original point of the Jiugong grid).
numMat[i][j].setValue(0);
j--;
if(j==-1){
i--;j=8;
}
while(al.contains(numMat[i][j])){//If the position returned to is the original point of the Jiugong grid, continue to retreat until it is not the own point and jump out of while.
j--;
if(j==-1){
i--;j=8;
}
}
numMat[i][j].changeFlag();//Will mark
v = numMat[i][j].getValue();
}
}
}
j++;
if(j==9){
j=0;i++;//i++ here may cause i to increase to 9, so the following judgment requires 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("Please enter the point information according to the format (i row number, j column number and v value), enter over: ijv ");
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();
}
}
}
---Run the program
Please enter the point information according to the format (i row number, j column number and v value), and enter over: ijv when entering.
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 |
――┼―――┼―――┤