This is the 16th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

preface

Js daily algorithm problem, today continues, today is still an array processing algorithm problem, the name is effective sudoku, sudoku I believe we have played, sudoku judgment is very complex, this problem only has been filled in the data for judgment, the following look at the problem

Topic describes

Determine if a 9 x 9 sudoku is valid. You only need to verify that the numbers you have entered are valid according to the following rules.

The numbers 1-9 can appear only once in each line. The numbers 1-9 May appear only once in each column. The numbers 1-9 can occur only once in each 3×3 palace separated by a thick solid line. (See sample diagram)

Note:

A valid sudoku (partially filled) is not necessarily solvable. You only need to verify that the entered numbers are valid according to the above rules. Blank cells are represented by ‘.’.

Example 1:

Enter: board =

[[” 5 “, “3”, “”,” “, “7”, “”,” “, “”,” “]

[” 6 “, “. “, “”,” 1 “, “9”, “5”, “”,” “, “”]

[“. “, “9”, “eight”, “”,” “, “”,” “, “6”, “”]

[” 8 “, “. “, “”,” “, “6”, “”,” “, “”,” 3 “]

[” 4 “, “. “, “”,” eight “, “”,” 3 “, “”,” “, “1”]

[” 7 “, “. “, “”,” “, “2”, “”,” “, “”,” 6 “]

[“. “, “6”, “”,” “, “”,” “, “2”, “eight”, “”]

[“. “, “. “, “”,” 4 “, “1”, “9”, “”,” “, “5”]

, “. “, “. “, “”,” “, “eight”, “”,” “, “7”, “9”]]

Output: true,

Example 2:

Enter: board =

[[” 8 “, “3”, “”,” “, “7”, “”,” “, “”,” “]

[” 6 “, “. “, “”,” 1 “, “9”, “5”, “”,” “, “”]

[“. “, “9”, “eight”, “”,” “, “”,” “, “6”, “”]

[” 8 “, “. “, “”,” “, “6”, “”,” “, “”,” 3 “]

[” 4 “, “. “, “”,” eight “, “”,” 3 “, “”,” “, “1”]

[” 7 “, “. “, “”,” “, “2”, “”,” “, “”,” 6 “]

[“. “, “6”, “”,” “, “”,” “, “2”, “eight”, “”]

[“. “, “. “, “”,” 4 “, “1”, “9”, “”,” “, “5”]

, “. “, “. “, “”,” “, “eight”, “”,” “, “7”, “9”]]

Output: false

Explanation: All numbers in the space are the same as in example 1, except that the first number in the first line is changed from 5 to 8. But since there are two eights in the 3×3 in the upper left corner, this sudoku is invalid.

Their thinking

  • 1. Check whether each line contains the same item 2. Check whether there are the same items in each column. 3. Check whether there are the same items in each small nine squares
  • In this case, we only need to iterate through the target array once, and use a hash table to record the number of occurrences in each iteration. Since each item must be between 1 and 9 in size, we use an array instead of a hash table to count
  • First declares three array, used to record line respectively, in the column, and small scratchable latex occurrences, and traverse the target array, due to the value of each item shall be between 1 to 9, here we can use the target array item 1 as the subscript, the subscript of the corresponding item is what we gauge number, row, column is a two-dimensional array, small scratchable latex is a three dimensional array, see the code below
/ * * *@param {character[][]} board
 * @return {boolean}* /
var isValidSudoku = function(board) {
    let rowArr = new Array(9).fill(0).map(() = >new Array(9).fill(0)) // Count arrays of rows
    let columnArr = new Array(9).fill(0).map(() = > new Array(9).fill(0)) // Count array of columns
    let squareArr = new Array(3).fill(0).map(() = > new Array(3).fill(0).map(() = >new  Array(9).fill(0))) // Count array of 9 cells
    for(let i=0; i<9; i++){for(let j=0; j<9; j++){const curr = board[i][j]
            if(curr! = ='. ') {const index = Number(curr)-1 // Subtract 1 from the current item as the index of the count array
                rowArr[i][index]++
                columnArr[j][index]++
                squareArr[Math.floor(i/3] [Math.floor(j/3)][index]++
                // If there are identical items, then the index must be equal
                if (rowArr[i][index] > 1 || columnArr[j][index] > 1 || squareArr[Math.floor(i/3] [Math.floor(j/3)][index] > 1) {return false; }}}}return true
};
Copy the code

conclusion

The last point is to identify the three cases, row, column, nine cells, and then go through the number group, hash table to count