This is the 25th day of my participation in the August Genwen Challenge.More challenges in August

There will be table tennis match tonight, just like yesterday, I will do leetcode in the afternoon. I won more than I lost yesterday, but I was still eliminated. I didn’t grasp the key ball of the crucial game, which was a little pity. I plan to buy a good ping-pong board after the competition and play it 3-4 times a month. In this way, I rekindle my passion for playing national tennis when I was young. Today we’re on problem 36 for Leetcode.

The title

Please determine if a 9×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. (Please refer to the sample figure) Numbers have been filled in the space of the Sudoku part, and the blank space is represented by ‘.’.

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.

Input: 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”] [“.”,”.”,”.”,” 8″,”.”,” 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 interpretation: in addition to the first line of the first number changed from 5 to 8, other Numbers are the same as the sample 1 box. But since there are two eights in the 3×3 in the upper left corner, this sudoku is invalid.

Train of thought

Not quite understand leetcode’s difficulty definition logic, this question should be quite water, unexpectedly is a medium. Of course, the premise is to understand the rules of Sudoku. To put it simply, a large area of 99 has 9 rows, 9 columns and 9 small squares of 33. Each row, column and square is a small area. The rows and columns are easy to understand, so let’s draw a picture of the little squares:

The simple part of this problem is that it is only necessary to determine whether a number already exists, rather than whether the sudoku has a solution.

Let’s define three booleans: line, column, and box, representing rows, columns, and squares.

The first dimension of line represents rows 0 through 8 of the array, and the second dimension represents whether the nine digits 1 through 9 occur

The first dimension of column represents the 0 through 8 columns of the array, and the second dimension represents whether the 9 digits 1 through 9 have been present

The first dimension of the box represents 0 to 8 small boxes, and the second dimension represents 1 to 9

The default value is false. If the array is present at that location, change it to true. If it is already true, it is the second occurrence within a small area, which is invalid.

One possible difficulty is how to determine which box a cell belongs to: boxIndex = (I /3)*3 + j/3

Java version code

Class Solution {public Boolean isValidSudoku(char[][] board) {class Solution {public Boolean isValidSudoku(char[][] board) {public Boolean isValidSudoku(char[][] board) { // The first dimension of the column represents the 0 to 8 columns of the array, and the second dimension represents the 1 to 9 numbers of the array. // The first dimension of the box represents the 0 to 8 boxes, False Boolean [][] line = new Boolean [9][9]; boolean[][] column = new boolean[9][9]; boolean[][] box = new boolean[9][9]; for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) { char c = board[i][j]; if (c ! = '.') { int val = c - '0'; if (line[i][val - 1] || column[j][val - 1] || box[(i/3)*3 + j/3][val - 1]) { return false; } else { line[i][val - 1] = true; column[j][val - 1] = true; box[(i/3)*3 + j/3][val - 1] = true; } } } } return true; }}Copy the code