My LeetCode: https://leetcode-cn.com/u/ituring/
My LeetCode brush Title source [GitHub]: https://github.com/izhoujie/Algorithmcii
LeetCode 36. Valid Sudoku
subject
Determine if a 9x9 Sudoku is valid.Just u according to the following rule u, verify that the number that has been filled in is valid.
- Numbers 1-9 can only appear once per line.
- Numbers 1-9 can only appear once in each column.
- The numbers 1-9 can only appear once in each 3x3 uterus separated by a thick solid line.
The figure above is a partially filled valid Sudoku.
Sudoku spaces are filled with numbers, and the spaces are denoted by'.'.
Example 1:
Input: [ ["5","3",".",".","7",".",".",".","."], ["6",".",".","1","9","5",".",".","."], [".","9","8",".",".",".",".","6","."], ["8",".",".",".","6",".",".",".","3"], ["4",".",".","8",".","3",".",".","1"], ["7",".",".",".","2",".",".",".","6"], [".","6",".",".",".",".","2","8","."], [".",".",".","4","1","9",".",".","5"], [".",".",".",".","8",".",".","7","9"] ] Output: true
Example 2:
Input:
[
["8","3",".",".","7",".",".",".","."],
["6",".",".","1","9","5",".",".","."],
[".","9","8",".",".",".",".","6","."],
["8",".",".",".","6",".",".",".","3"],
["4",".",".","8",".","3",".",".","1"],
["7",".",".",".","2",".",".",".","6"],
[".","6",".",".",".",".","2","8","."],
[".",".",".","4","1","9",".",".","5"],
[".",".",".",".","8",".",".","7","9"]
]
Output: false
Interpretation: The numbers in the space are the same as example 1 except that the first number in the first line changes from 5 to 8.
This number is invalid because there are two eight in the 3x3 uterus located in the upper left corner.
Explain:
- A valid Sudoku (partially filled) is not necessarily solvable.
- Simply verify that the numbers you have filled in are valid according to the rules above.
- The given Sudoku sequence contains only the numbers 1-9 and the characters'.'.
- Given Sudoku is always in the form of 9x9.
Source: LeetCode
Links: https://leetcode-cn.com/problems/valid-sudoku
Copyright shall be owned by the withholding network.For commercial reprinting, please contact the official authorization. For non-commercial reprinting, please indicate the source.
Solving problems
This question is relatively simple to make. Violence can be checked separately for each row, vertical and small palace, so that at least three full scans are needed.
How can I do this with just one scan?After analysis, it may be found that the most difficult problem to solve is the index problem of small palaces. Secondly, if you want to save the original data, you should need to
There are three two-dimensional arrays (or set sets) in the small horizontal grid, but we just need to know if 1-9 is a number or not and only one, corresponding to the code 0 and 1, so we can further compress the two-dimensional arrays into one-digit arrays.
The first 9 bit s of int in each array are used to store whether 1-9 has occurred or not, and only once. To sum up, from three two-dimensional arrays that need to be scanned three times to three two-dimensional arrays at one time and then to the last three one-dimensional arrays, the efficiency of the algorithm is significantly improved.
Ideas 1-3 scans, small horizontal palaces for verification
Steps:
- Create three new set s corresponding to the small horizontal and vertical palaces;
- Three scans were used to check the small transverse and vertical palaces.
Idea 2 - Scan once only
The key to scanning only once is to locate the index of the small grid:
The index formula of key point small palettes: (i/3)*3 + j/3;
This is understandable:
- i/3 represents the row of the small palace, with values of 0, 1 and 2 corresponding to the actual first, second and third rows;
-(i/3) 3 denotes the starting number of the small palace subscript for the third row, for example, the first row starts from 0, the second row from 3, and the third row from 6;
- j/3 represents the j/3 palace of the row, and values of 0, 1 and 2 correspond to the actual first, second and third small palaces;
-(i/3) 3 + j/3 together means that the first half represents the row of the small palace and its starting subscript, and the second half represents the number of small palaces in the current row. All possible values of the combination of 0, 1, 2, 3, 4, 5, 6, 7, 8 correspond to nine small palaces.
Idea 3 - Scan once, further compress auxiliary space, use bit bits to record data
There is no big difference between the actual practice and code and Idea 2. The only difference is that the array is transposed in one dimension and the bit records and comparison checks are used in the checking.
Sample algorithm source
package leetcode;
import java.util.HashSet;
/**
* @author ZhouJie
* @date 2020 February 1, 2001, 4:30:05 p.m.
* @Description: 36. Valid Sudoku
*
*/
public class LeetCode_0036 {
}
class Solution_0036 {
/**
* @author ZhouJie
* @date 2020 February 1, 2001, 8:27:14 p.m.
* @Description: TODO(Method Brief)
* @return boolean
* @UpdateUser-UpdateDate:[ZhouJie]-[2020 February 1, 2001, 8:27:14 p.m.]
* @UpdateRemark:1-The rows and columns traverse the check separately, using a set
*
*/
public boolean isValidSudoku_1(char[][] board) {
if (board == null) {
return false;
}
HashSet<Character> set = new HashSet<Character>();
// Row and Column Judgment
for (int x = 0; x < 9; x++) {
set.clear();
// Line judgment
for (int y = 0; y < 9; y++) {
if (!check(set, board[x][y])) {
return false;
}
}
set.clear();
// Column Judgment
for (int y = 0; y < 9; y++) {
if (!check(set, board[y][x])) {
return false;
}
}
}
// To judge a small palace, first locate the position of a single small palace, and then traverse the numbers of the small palace
for (int i = 0; i < 9; i += 3) {
for (int j = 0; j < 9; j += 3) {
set.clear();
for (int x = 0; x < 3; x++) {
for (int y = 0; y < 3; y++) {
if (!check(set, board[x + i][y + j])) {
return false;
}
}
}
}
}
return true;
}
private boolean check(HashSet<Character> set, char c) {
if (c == '.') {
return true;
} else if (set.contains(c)) {
return false;
} else {
set.add(c);
return true;
}
}
/**
* @author ZhouJie
* @date 2020 February 1, 2001, 8:27:38 p.m.
* @Description: TODO(Method Brief)
* @return boolean
* @UpdateUser-UpdateDate:[ZhouJie]-[2020 February 1, 2001, 8:27:38 p.m.]
* @UpdateRemark:2-The rows and columns of the small palaces are checked at the same time using their own checkspace, one traversal
*
*/
public boolean isValidSudoku_2(char[][] board) {
// Numbering of rows and rows of small palaces
int[][] rows = new int[9][9];
int[][] columns = new int[9][9];
int[][] boxes = new int[9][9];
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
char c = board[i][j];
if (c != '.') {
int num = c - '1';
// Focus, Calculate Small Grid Index Formula
int boxIndex = (i / 3) * 3 + j / 3;
// Line judgment
if (rows[i][num] == 1) {
return false;
} else {
rows[i][num] = 1;
}
// Column Judgment
if (columns[j][num] == 1) {
return false;
} else {
columns[j][num] = 1;
}
// Small Palace Judgment
if (boxes[boxIndex][num] == 1) {
return false;
} else {
boxes[boxIndex][num] = 1;
}
}
}
}
return true;
}
/**
* @author: ZhouJie
* @date: 2020 April 3, 2003 9:30:03 p.m.
* @param: @param board
* @param: @return
* @return: boolean
* @Description: 3-Compress space further so that bit s are used to calculate data
*
*/
public boolean isValidSudoku_3(char[][] board) {
// Numbering of rows and rows of small palaces
int[] rows = new int[9];
int[] columns = new int[9];
int[] boxes = new int[9];
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
char c = board[i][j];
if (c != '.') {
int num = c - '1';
// Focus, Calculate Small Grid Index Formula
int boxIndex = (i / 3) * 3 + j / 3;
// Line judgment
if (((rows[i] >> num) & 1) == 1) {
return false;
} else {
rows[i] |= 1 << num;
}
// Column Judgment
if (((columns[j] >> num) & 1) == 1) {
return false;
} else {
columns[j] |= 1 << num;
}
// Small Palace Judgment
if (((boxes[boxIndex] >> num) & 1) == 1) {
return false;
} else {
boxes[boxIndex] |= 1 << num;
}
}
}
}
return true;
}
}