# Java crack 9X9 Sudoku games

## background

Recently, I brushed this interesting topic on LeetCode and thought of my love for Sudoku in junior high school. I couldn't help feeling very much. It turns out that this program can produce results in less than 1m, which made me waste so much time to study before.

## effect

It is said that this is the most difficult Sudoku topic [click this link to enter], let's take it

```Initial situation:
8........
..36.....
.7..9.2..
.5...7...
....457..
...1...3.
..1....68
..85...1.
.9....4..

Start solving time:
2021/06/12 11:59:45

812753649
943682175
675491283
154237896
369845721
287169534
521974368
438526917
796318452

End solution time:
2021/06/12 11:59:45

time consuming:33ms

```

## source code

1, Algorithm code: solution java

```public class Solution {
/**
* that 's ok
*/
final int ROW=9;
/**
* column
*/
final int COL=9;
/**
* Is line i filled with value
*/
boolean [][]row=new boolean[ROW][COL];
/**
* Is column i filled with value
*/
boolean [][]col=new boolean[ROW][COL];
/**
* Is the i-th little nine palaces filled with value
*/
boolean [][]mid=new boolean[ROW][COL];

/**
* Sudoku
*/
char[][] board;
/**
* Have you got the answer
*/
boolean solve=false;

/**
* Solving Sudoku
* @param board Sudoku
*/
public void solveSudoku(char[][] board) {

//Initialize three Boolean arrays
for(int i=0;i<ROW;i++) {
for(int j=0;j<COL;j++) {
if(board[i][j]=='.') {
continue;
}else {
row[i][board[i][j]-'0'-1]=true;
col[j][board[i][j]-'0'-1]=true;
mid[i/3*3+j/3][board[i][j]-'0'-1]=true;
}
}
}

this.board=board;

dfs(0,0);
}

/**
* Depth first
* @param i
* @param j
*/
public void dfs(int i,int j) {
//If it has been solved, it will not be calculated
if(solve) {
return;
}

//Conditions resolved
if(i>=ROW||j>=COL) {
solve=true;
return;
}

//If it is not a space, you cannot fill in the number
if(board[i][j]!='.') {
if(j==COL-1) {
dfs(i+1,0);
}else {
dfs(i,j+1);
}
return;
}

//Try to fill in 1 ~ 9. Only those that have not appeared can be filled in. After filling, update the filled Boolean array immediately and change it back to the original state afterwards
for(int number=1;number<=9;number++) {
//It's illegal to skip
if(row[i][number-1]||col[j][number-1]||mid[i/3*3+j/3][number-1]) {
continue;
//Otherwise try to fill in
}else {
//Try filling
board[i][j]=(char)(number+48);
//Update filled Boolean array
row[i][number-1]=true;
col[j][number-1]=true;
mid[i/3*3+j/3][number-1]=true;

//Go to the next element
if(j==COL-1) {
dfs(i+1,0);
//Before the end of the line, skip to the next element of the line
}else {
dfs(i,j+1);
}

//The attempt ends. If there is no result, reset it as it is
if(solve) {
return;
}else {
board[i][j]='.';
row[i][number-1]=false;
col[j][number-1]=false;
mid[i/3*3+j/3][number-1]=false;
}
}
}
}
}

```

2, Test code main java

```import java.text.SimpleDateFormat;
import java.util.Date;

public class Main {

public static void main(String[] args) {
// TODO Auto-generated method stub
char[][]board=new char;
//String value="530070000\n600195000\n098000060\n800060003\n400803001\n700020006\n060000280\n000419005\n000080079";
String value="800000000\n003600000\n070090200\n050007000\n000045700\n000100030\n001000068\n008500010\n090000400";

String []rows=value.split("\n");
for(int i=0;i<rows.length;i++) {
for(int j=0;j<rows[i].length();j++) {
board[i][j]=rows[i].charAt(j);
if(board[i][j]=='0') {
board[i][j]='.';
}
}
}

System.out.println("Initial situation:");
display(board);

SimpleDateFormat sdf=new SimpleDateFormat("yyyy/MM/dd HH:mm:ss");

Date start=new Date();
System.out.println();
System.out.println("Start solving time:");
System.out.println(sdf.format(start));
long s=System.currentTimeMillis();

Solution solution=new Solution();
solution.solveSudoku(board);
System.out.println();

display(board);

System.out.println();
Date end=new Date();
System.out.println("End solution time:");
System.out.println(sdf.format(end));
System.out.println();

long e=System.currentTimeMillis();
System.out.println("time consuming:"+(e-s)+"ms");
}

public static void display(char[][] board) {
for(int i=0;i<9;i++) {
for(int j=0;j<9;j++) {
System.out.print(board[i][j]);
}
System.out.println();
}
}
}

```

## Algorithm idea

Let the computer simulate people's thinking. According to the Sudoku rules, the numbers 1-9 in each row, column and small nine house can appear only once. According to this rule, we can define three hash arrays to store these three cases.

Boolean array row, give it nine rows and nine columns, and let row[i][number] indicate whether number+1 has appeared in line i+1 [note that the array subscript of the computer starts from zero, of course, you can abandon row 0 and start from 1 according to your habit].

Boolean array col, give it nine rows and nine columns, and let col[i][number] indicate whether number+1 has appeared in i+1 column [note that the array subscript of the computer starts from zero, of course, you can abandon row 0 and start from 1 according to your habit].

Boolean array mid, give it nine rows and nine columns, and let mid[i][number] indicate whether number+1 has appeared in i+1 small nine palaces [note that the array subscript of the computer starts from zero, of course, you can abandon row 0 and start from 1 according to your habit].

When we get the title, we first fill in the three Boolean arrays we set according to the given information. Then it is one of the templates of our universal cracking trial Games: depth first search. In order to make the program simple, we use recursive writing. In order to reduce the number of pits here, I have summarized four experiences [let's start from line 1 and try to fill in the number line by line. Function prototype: f(i,j), indicating that the elements currently trying are i+1 line and j+1 column].

1. Set the sentinel [boolean type] as the sign of the end of the solution, that is, when a result is obtained, notify the recursive function to jump out.

2. When the row and column of the attempt exceeds 9, it indicates that the result is obtained. The sentry reaches true and jumps out of recursion.

3. The current element has been filled in, so skip it and try the next element

4. If the current element has not been filled in, fill in the possible values, update the three Boolean arrays indicating that they have been filled in, and try the next element. If the problem is solved after the attempt, exit the recursive function, otherwise reset the state just now: including the situation and three Boolean arrays.

Added by sabbagh on Mon, 31 Jan 2022 09:15:13 +0200