- 2020-07-02 08:37
*views 2*- 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

Daily Recommendation

views 4

views 2

views 2

©2019-2020 Toolsou All rights reserved,

[work] python read txt Last line of file Novices play hiss HI3520D Development board （ One , upgrade ） Theory and formula derivation of univariate linear regression and multiple linear regression Three.js - OrbitControls Orbit control around target target parameter @Repository The role of annotations Vue + Element-ui Drop down box for el-select Get extra parameters iPhone 12 price , Configure full exposure ： Cut it off 64GB, Battery 2227mAh start experiment 11-1-6 Output string at specified position （20 branch ）( Essence )2020 year 6 month 26 day C# Class library Enum( Extension method ) subversion ! Never take a nap longer than this time ! Watch out for fatal diseases …