I’m sure you’ve all played sudoku, so how do we use a program to verify that a 9×9 sudoku is valid? Take a look!

01. Examples of topics

Sudoku is a math game that originated in 18th century Switzerland. Is a logic game using paper and pen. Based on the known numbers on the 9×9 plate, the player needs to deduce the numbers of all remaining Spaces, and satisfy that the numbers in each line, column, and thick line (3 × 3) all contain 1-9, and do not repeat.


Title: Valid Sudoku
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.


Example:

Input:

[



  ["5"."3"."."."."."Seven"."."."."."."."."].



  ["6"."."."."."1"."9"."5"."."."."."."].



  ["."."9"."8"."."."."."."."."."6"."."].



  ["8"."."."."."."."6"."."."."."."."3"].



  ["4"."."."."."8"."."."3"."."."."."1"].



  ["Seven"."."."."."."."2"."."."."."."."6"].



  ["."."6"."."."."."."."."."2"."8"."."].



  ["."."."."."."4"."1"."9"."."."."."5"].



  ["."."."."."."."."8"."."."."."Seven"."9"]



]



Output:true



Explanation:



Sudoku part of the space has been filled in the number, blank space'. 'Said.



Copy the code

Description:

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.

Given sudoku sequences contain only the numbers 1-9 and the characters ‘.’.

Sudoku is always 9×9.


It looks like this:


02, Solution analysis

Talking about sudoku, long ago actually studied for a while, is very interesting. There are many solutions, including remainder method, elimination method and so on. So how do we assess the difficulty of a Sudoku? In general, the more numbers given, the simpler sudoku is.


The key question is:


  • 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.


What we need to do is to use the program to complete the verification process, how to verify? There are really two steps:


  • Step 1: Go through every element in sudoku
  • Step 2: Verify that the element meets the above conditions


There’s nothing to say about traversing this, just traversing left to right, top to bottom. Just a two-level loop. Because the problem itself is of constant size, the time is O(1).


The question arises: How do you verify that an element has no duplicates in a row/column/sudoku?


It’s pretty simple. We create three arrays for each row, each column, and each sudoku (the sudoku is the colored box above).

//JAVA

int[][] rows = new int[9] [9];

int[][] col = new int[9] [9];

int[][] sbox = new int[9] [9];

Copy the code

Of course, they were empty when they started. And then every time we walk through an element, we check to see if that element exists in it, and if it doesn’t, we put it in, and if it does, that means sudoku is illegal.


Take, for example, this sudoku. Row 6, column 5, column 2, so we set rows and col :(1 indicates the element exists)


Rows [current line] [the current element value] = rows [5] [2] = 1 col [current column] [the current element value] = col [4] [2] = 1


But there’s a problem, if the element value is 9, it’s out of bounds! So let’s subtract the value of the current element:

Rows [current line] [the current element value] = rows [5] [] 2-1 = 1 col [current column] [the current element value] = col [4] [] 2-1 = 1


Now the question is, what do I do with sbox? We use the following formula to calculate:

boxIndex = (row / 3) * 3 + columns / 3

Copy the code

It’s easy to understand: let’s substitute row 6, column 5, above into this formula, 5/3 times 3 + 4/3 = 3 + 1 = 4. So this 4 right here is going to be the same area as 4.


I guess someone can’t understand this formula (yes, it’s not even a formula), so I’ll explain where it comes from. For example, in line 6 above, row 5, 5/3=1 means that we are on the first row, and then (5/3)*3 computs the current boxIndex value at the first row. And then finally, plus 4/3, which means we’ve shifted to the right by a couple of big columns.


According to the analysis, the code is given:

class Solution { 

    public boolean isValidSudoku(char[][] board) { 

        int[][] rows = new int[9] [9]; 

        int[][] col = new int[9] [9]; 

        int[][] sbox = new int[9] [9]; 

        for (int i = 0; i < board.length; i++) {

            for (int j = 0; j < board[0].length; j++) { 

                if(board[i][j] ! ='. ') { 

                    int num = board[i][j] - '1';

                    int boxIndex = (i / 3) * 3 + j / 3;

                    if (rows[i][num] == 1) return false;

                    rows[i][num] = 1;

                    if (col[j][num] == 1) return false;

                    col[j][num] = 1;

                    if (sbox[boxIndex][num] == 1) return false;

                    sbox[boxIndex][num] = 1;

                }

            }

        }

        return true;

    }

}

Copy the code

Execution Result:


03,

Finally, I am here to share a very difficult sudoku, welcome everyone to challenge!! Challenge successful, leave your answer in the comments!


I’ve compiled all the problems I’ve written into an e-book, complete with illustrations for each problem. Click to download