This is the third day of my participation in the August Text Challenge.More challenges in August

preface

The valid sudoku of question 36 is as follows:

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.

  1. digital1-9You can only appear once in each line.
  2. digital1-9You can only appear once in each column.
  3. digital1-9In each one separated by a thick solid line3x3You can only be in the palace once. (See sample diagram)

Numbers have been filled in the blank space of sudoku, 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.

 

Example 1:

A, thinking

It’s a long question, but if you know sudoku, it shouldn’t be too difficult to understand. In a 9×9 square, the numbers 1 to 9 can appear only once in each row, column, and 3×3 square. Verify whether sudoku is valid according to the rules

The approximate implementation of the implementation is also very simple, the idea is a traversal, verify three times

So how do you do a single traversal, checking rows, columns, and 3×3 squares?

For example

We can use three arrays to store the row, column, and position of the corresponding number in a 3×3 square.

As shown below, this is a 9×9 grid:

Assume the position of the number 8 in the grid as follows:

It is obvious that the number 8 is the fifth position in the second row, second column, and 3×3 square, so the specific storage is as follows:

Int [][] rowRecords = new Int [9][9] : rowRecords int[][] colRecords = new Int [9][9] : rowRecords int[][] subBoxRecords = new int[9][9] : Subbox records Tips: All two-dimensional arrays are used to store all the columns and subboxes

RowRecords [1][7] = 1, the eighth digit in the second row already exists colRecords[1][7] = 1, the seventh digit in the second column already exists subBoxRecords[0][7] = 1, the seventh digit in the first subbox already exists

So we just need to check if the values already exist before we assign to the three arrays. If it already exists, return false to indicate that the sudoku is illegal.

Second, the implementation

The implementation code

public boolean isValidSudoku(char[][] board) {
    / / rows
    int[][] rowRecords = new int[9] [9];
    / / column records
    int[][] colRecords = new int[9] [9];
    // Subbox record
    int[][] subBoxRecords = new int[9] [9];
    // Check 3 times
    for (int i=0; i<9; i++) {
        for (int j=0; j<9; j++) {
            char c = board[i][j];
            if (c == '. ')
                continue;
            // subbox subscript
            int boxIndex = i/3 + j/3*3;
            / / check
            int val =  Integer.parseInt(String.valueOf(c)) - 1;
            boolean rowIncluded = rowRecords[i][val] == 1;
            boolean colIncluded = colRecords[j][val] == 1;
            boolean subBoxIncluded = subBoxRecords[boxIndex][val] == 1;
            if (rowIncluded || colIncluded || subBoxIncluded)
                return false;
            / / assignment
            rowRecords[i][val] = 1;
            colRecords[j][val] = 1;
            subBoxRecords[boxIndex][val] = 1; }}return true;
}
Copy the code

The test code

public static void main(String[] args) {
    char[][] board = 
            {{'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'}};
    new Number36().isValidSudoku(board);
    
}
Copy the code

The results of

Third, summary

Thank you to see the end, very honored to help you ~♥