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 answer: 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
//At the end of the line, skip to the next line
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[9][9];
//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();
System.out.println("answer:");
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.