- 2020-07-02 08:37
*views 6*- algorithm

Judge one 9x9 Is Sudoku valid . Just follow these rules , It is enough to verify whether the filled number is valid .

* number 1-9 It can only appear once per line .

* number 1-9 It can only appear once in each column .

* number 1-9 In each of the 3x3 Only once in utero .

The picture above is a partially filled valid Sudoku .

The blank of Sudoku is filled with numbers , Blank space '.' express .

Examples 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

Examples 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 explain : Except for the first number in the first line from 5 Change to 8 outside , Other numbers in the space are the same as Examples 1 identical . But because of the 3x3 There are two in the palace 8

existence , So this Sudoku is invalid .

explain :

* An effective Sudoku （ Part has been filled ） Not necessarily solvable .

* Just follow the above rules , It is enough to verify whether the filled number is valid .

* A given Sudoku sequence contains only numbers 1-9 And characters '.' .

* Given Sudoku is always 9x9 Formal .

Thinking of problem solving ：

We can use three two-dimensional arrays to quickly determine whether Sudoku meets the requirements

Core ideas ： Use the number in Sudoku as the subscript , Quickly judge whether the subscript position is used or not .

The three arrays are ： Row array （rows), Column array (coulmns), Lattice array (boxes)

They are used for testing Are there duplicate numbers in each line , Are there duplicate numbers in each column , Are there duplicate numbers in each grid

Take row array as an example ：

Of row array

The first subscript is the serial number of the line （ Which line of Sudoku is the number on ）

The number two subscript is a specific number （0-9）

When a number in the line is scanned （ As in the first line 5）, that rows[0][5]++

If Sudoku has a mistake in the first line , There are two 5, So after scanning the second one 5 Time ,rows[0][5] Should be equal to 2, There is a mistake in Sudoku , Not meeting requirements

If the row has only one 5 Or not 5, that rows[0][5] Should be less than 2, No mistakes in Sudoku

In the same way, the array should be able to detect whether all the values in all rows of the whole Sudoku are repeated

In the same way coulmns Time , Use the column number as the first subscript , All columns can be detected for duplicate values

Will each 3*3 Label the box , It should also be possible to detect whether the values in the box are repeated

Attention point ： The first subscript of the box

When labeling boxes , We need each one 3*3 The elements in the box can be located in the same box by calculation , Same subscript

So there is the formula boxIndex = i / 3 * 3 + j / 3;

You can group Sudoku into boxes

class Solution { public boolean isValidSudoku(char[][] board) { int[][] rows =

new int[9][10]; int[][] columns = new int[9][10]; int[][] boxes = new

int[9][10]; for(int i = 0;i < 9;i++){ for(int j = 0;j < 9;j++){

if(board[i][j]!='.'){ int num = board[i][j] - '0'; int boxIndex = i / 3 * 3 + j

/ 3; rows[i][num] += 1; columns[j][num] += 1; boxes[boxIndex][num] += 1;

if(rows[i][num]==2||columns[j][num]==2||boxes[boxIndex][num]==2) return false;

} } } return true; } }

Time complexity O(n^2)

Execution time : 34 ms, stay Valid Sudoku Of Java Defeated in submission 68.50% Users of

Memory consumption : 54.2 MB, stay Valid Sudoku Of Java Defeated in submission 0.88% Users of

Technology

- Java426 articles
- Python242 articles
- Vue127 articles
- Linux119 articles
- MySQL100 articles
- javascript77 articles
- SpringBoot72 articles
- C++68 articles
- more...

Daily Recommendation

©2019-2020 Toolsou All rights reserved,

It's unexpected Python Cherry tree （turtle The gorgeous style of Library ） Some East 14 Pay change 16 salary , Sincerity or routine ? Browser kernel （ understand ）java Four functional interfaces （ a key , simple ）HashMap Explain in detail html Writing about cherry trees , Writing about cherry trees os Simple use of module