36 Valid Sudoku ( Leetcode Top Interview question 150 –34/150 ) — Java solution

Valid Sudoku - LeetCode

Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

1. Each row must contain the digits 1-9 without repetition.
2. Each column must contain the digits 1-9 without repetition.
3. Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.

Note:

• A Sudoku board (partially filled) could be valid but is not necessarily solvable.
• Only the filled cells need to be validated according to the mentioned rules.

Example 1:

Input: 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"]]
Output: true

Example 2:

Input: board = 
[["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
Explanation: Same as Example 1, except with the 5 in the top left corner being modified to 8. Since there are two 8's in the top left 3x3 sub-box, it is invalid.

Constraints:

• board.length == 9
• board[i].length == 9
• board[i][j] is a digit 1-9 or '.'.

Solution:

The approach to solve this problem is to check for each element in the matrix, for following conditions:

1. The number should not be in the same row
2. The number should not be in the same column
3. The number should not be in the 3 by 3 sub matrix

Checking row and column is simple enough as we just need to check all the other items with the same row number or the column number.

The challenge is to check for item in the same sub-matrix, hence to itentity the sub-matrix we can use some calculation to see what other items form part of the same sub-matrix.

One way to do this is to derive a submatrix name for each item in the matrix. To do this for each element at (i,j) → submatrix (i/3 — j/3).

Eg:

item at (1,1) → (1/3–1/3) → (0–0)

item at (2,2) → (2/3–2/3) → (0–0)

item at (5,4) → (5/3–4/3) → (1–1)

so item at (1,1) and (2,2) are part of same submatrix 0–0 whereas item at (5,4) belogs to submatrix 1–1

Now second improvement that we can do for comparing item with all other items is to create a set of item and it’s location that we have already encountered and return false the moment we are unable to insert any item with it location in the set.

To do this, for every item we encounter we try to insert three records for in in the set. These there records are:

1. item and it’s row
2. item and it’s column
3. item and it’s sub-matrix name

If we are unable to insert any of these data for an item then we can be sure that item is at an invalid location for the Sudoku.

class Solution {
    public boolean isValidSudoku(char[][] board) {
        Set seen = new HashSet();
        for (int i=0; i<9; ++i) {
            for (int j=0; j<9; ++j) {
                char number = board[i][j];
                if (number != '.')
                    if (!seen.add(number + " in row " + i) ||
                        !seen.add(number + " in column " + j) ||
                        !seen.add(number + " in submatrix " + i/3 + "-" + j/3))
                        return false;
            }
        }
        return true;
    }
}

For code solution and other leetcode solution fork me at :

https://github.com/ankitech/practice_sites_code#LeetCode

GitHub - ankitech/practice_sites_code: codes that are used on coding sites