36. Valid Sudoku

MediumArrayHash TableMatrix
Leetcode Link

Problem Description

In this problem, we are given a partially filled 9 x 9 Sudoku board. Our task is to determine whether the board is valid according to the rules of Sudoku. We do not need to solve the Sudoku; we just need to validate the existing filled-in cells. The rules are that each filled cell must meet three constraints:

  1. Every row must have the digits 1-9 without any repetition.
  2. Every column must have the digits 1-9 without any repetition.
  3. Each of the nine 3 x 3 subgrids or boxes that compose the grid must have the digits 1-9 without any repetition.

A key point to note is that a valid Sudoku board does not necessarily mean that it can be successfully solved to completion. The question only asks for validation of the current state of the board, not solvability.

Intuition

To solve this problem effectively, we can follow an approach that checks all three Sudoku rules for validity as we traverse the board once. The intuition here is to keep track of the constraints to prevent any repetitions of the digits in rows, columns, and sub-boxes.

How we arrive at the solution approach:

  • We initialize three lists to record the presence of each digit in rows, columns, and sub-grids (row, col, sub). Each of these lists will have 9 elements, with each element representing a row, column, or sub-grid, and each element is a 9 elements list to keep track of digits 1-9.
  • We then iterate over each cell in the board. Whenever we encounter a filled cell (not a '.'), we check for the digit's presence in the corresponding row, column, and sub-grid.
  • The sub-grid (also called a box) can be identified by using index arithmetic. We use i // 3 * 3 + j // 3 to obtain the index of the sub-grid where (i, j) is the cell's row and column indices.
  • If the digit is already present in its corresponding row, column, or sub-grid, we return False since it breaks the Sudoku rule of no repetition.
  • If the digit passes all checks, we mark it as present in the row, column, and sub-grid.
  • After checking all cells, if no rule is broken, we return True, confirming that the board state is valid.

Solution Approach

The solution follows a straightforward approach to validate a Sudoku board. It utilizes data storage patterns with auxiliary space, specifically lists within lists to track the digits that have been seen in the rows, columns, and sub-grids. The algorithm implemented can be broken down into the following steps:

  1. Initialization: We set up three lists of lists:

    • row to keep track of which numbers have been seen in each of the 9 rows.
    • col to keep track of which numbers have been seen in each of the 9 columns.
    • sub for the numbers seen in each of the 9 sub-grids. Each [[False] * 9 for _ in range(9)] represents a list of 9 elements initialized to False, indicating that no numbers have been encountered yet.
  2. Iteration over the board: We traverse the board with two nested loops, one iterating over the rows (i) and the other over the columns (j).

  3. Skip empty cells: We continue to the next iteration if the current cell (identified by board[i][j]) contains ".", which stands for an empty cell in Sudoku.

  4. Calculations:

    • Ascertain the digit (converted to a zero-based index by int(board[i][j]) - 1) present in the cell to update the tracking lists.
    • Determine the correct sub-grid using the formula k = i // 3 * 3 + j // 3, which works by dividing the board into 3-row and 3-column segments.
  5. Validation Checks:

    • If the number has already been seen in the current row[i], col[j], or sub[k], return False since it violates the rules of Sudoku.
  6. Updating Structures:

    • If the number hasn't been seen, we update row[i][num], col[j][num], and sub[k][num] to True to indicate that the digit is now accounted for in the respective row, column, and sub-grid.
  7. Final verdict: If no repetitions are found throughout the entire board, we finish iterating with no issues and return True, confirming the board's validity.

By using these data structures, the solution achieves an efficient way to keep track of which numbers have appeared in different parts of the board without having to re-scan portions of the board multiple times. This results in a time complexity of O(1) for each cell check (since accessing and updating the elements in a list by index is O(1)), and a total time complexity of O(n^2) for the entire board, where n is the number of cells in a row or column.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the two traversal algorithms (BFS and DFS) can be used to find whether two nodes are connected?

Example Walkthrough

Let's illustrate the solution approach with a small example of a 9x9 Sudoku board section. The section we will walk through is a typical scenario with three cells filled:

15 . .
2. 1 .
3. . 2

Here, we have filled digits '5', '1', and '2'. We need to validate if this section of the board is valid without considering the other cells of the entire board.

Step 1: Initialization

We create three lists, row, col, and sub, each initialized to [[False] * 9 for _ in range(9)]. This means we have a matrix for rows, columns, and sub-grids with False values, indicating that no numbers have been seen yet.

Step 2: Iteration over the board

We start traversing the board. In this case, we have:

1Iteration 1:
2i = 0, j = 0 -> cell (0,0) contains '5'
3
4Iteration 2:
5i = 0, j = 1 -> cell (0,1) contains '.'
6
7Iteration 3:
8i = 0, j = 2 -> cell (0,2) contains '.'
9
10Iteration 4:
11i = 1, j = 0 -> cell (1,0) contains '.'
12
13Iteration 5:
14i = 1, j = 1 -> cell (1,1) contains '1'
15
16Iteration 6:
17i = 1, j = 2 -> cell (1,2) contains '.'
18
19Iteration 7:
20i = 2, j = 0 -> cell (2,0) contains '.'
21
22Iteration 8:
23i = 2, j = 1 -> cell (2,1) contains '.'
24
25Iteration 9:
26i = 2, j = 2 -> cell (2,2) contains '2'

Step 3: Skip empty cells

As we encounter empty cells, indicated by '.', we continue to the next iteration and do not perform any operations for these cells.

Step 4: Calculations

  • In the first iteration (i = 0, j = 0), we encounter the number '5'. We translate this to a zero-based index, which gives us 4.
  • We identify the sub-grid using the formula k = i // 3 * 3 + j // 3. Here, k is 0 since both i // 3 and j // 3 are 0.

Step 5: Validation Checks

  • We check if the number '5' has been seen in row[0][4], col[0][4], or sub[0][4]. Since all are False, we proceed.

Step 6: Updating Structures

  • We mark row[0][4], col[0][4], and sub[0][4] as True, indicating that the number '5' has been accounted for in its row, column, and sub-grid.

  • Similarly, for the cell (1,1) containing '1', we mark row[1][0], col[1][0], and sub[0][0] as True.

  • For the cell (2,2) containing '2', we mark row[2][1], col[2][1], and sub[0][1] as True.

Step 7: Final Verdict

  • Since none of the validation checks returned False, we conclude that no rules of Sudoku were violated, and thus the board section is considered valid.

In this small walkthrough, we can see that by maintaining tracking lists and updating them, we can efficiently validate the Sudoku board state without re-checking any cell. Once all cells are processed in this manner, if no issues arise, we can confidently return True.

Solution Implementation

1class Solution:
2    def isValidSudoku(self, board: List[List[str]]) -> bool:
3        # Create tracking structures for rows, columns, and 3x3 sub-boxes.
4        rows = [[False] * 9 for _ in range(9)]
5        cols = [[False] * 9 for _ in range(9)]
6        boxes = [[False] * 9 for _ in range(9)]
7
8        # Iterate over each cell in the 9x9 board.
9        for i in range(9):
10            for j in range(9):
11                cell_value = board[i][j]
12                # Skip checking if the cell is empty.
13                if cell_value == '.':
14                    continue
15              
16                # Convert str digit to int and adjust index to zero-based.
17                num = int(cell_value) - 1
18              
19                # Calculate box index for 3x3 sub-boxes using integer division.
20                box_index = (i // 3) * 3 + j // 3
21              
22                # If the number has already been encountered in current
23                # row, column or box, sudoku condition is violated.
24                if rows[i][num] or cols[j][num] or boxes[box_index][num]:
25                    return False
26              
27                # Mark current num as encountered in current row, column and box.
28                rows[i][num] = True
29                cols[j][num] = True
30                boxes[box_index][num] = True
31
32        # If no conditions are violated, then the board is a valid sudoku.
33        return True
34
1class Solution {
2    // Function to check if a given Sudoku board is valid.
3    public boolean isValidSudoku(char[][] board) {
4        // Arrays to check the validity of rows, columns, and sub-grids.
5        boolean[][] rows = new boolean[9][9];
6        boolean[][] columns = new boolean[9][9];
7        boolean[][] subgrids = new boolean[9][9];
8
9        // Iterate over the board by rows and columns.
10        for (int i = 0; i < 9; ++i) {
11            for (int j = 0; j < 9; ++j) {
12                char currentChar = board[i][j];
13
14                // If the current character is a dot, ignore and continue to the next iteration.
15                if (currentChar == '.') {
16                    continue;
17                }
18
19                // Convert char to its corresponding number (1-9).
20                int number = currentChar - '0' - 1;
21
22                // Calculate index for the subgrids.
23                int subgridIndex = (i / 3) * 3 + j / 3;
24
25                // Check if the number has already been recorded in the current row, column, or subgrid.
26                if (rows[i][number] || columns[j][number] || subgrids[subgridIndex][number]) {
27                    // If any is true, then the board is not valid.
28                    return false;
29                }
30
31                // Mark the presence of the number in the current row, column, and subgrid.
32                rows[i][number] = true;
33                columns[j][number] = true;
34                subgrids[subgridIndex][number] = true;
35            }
36        }
37
38        // If no conflicts are found, the board is valid.
39        return true;
40    }
41}
42
1#include<vector>
2
3class Solution {
4public:
5    // Function to check if a Sudoku board is valid.
6    bool isValidSudoku(std::vector<std::vector<char>>& board) {
7        // Create three 9x9 matrices for rows, columns, and sub-boxes respectively.
8        std::vector<std::vector<bool>> rowCheck(9, std::vector<bool>(9, false));
9        std::vector<std::vector<bool>> colCheck(9, std::vector<bool>(9, false));
10        std::vector<std::vector<bool>> subBoxCheck(9, std::vector<bool>(9, false));
11
12        // Traverse the entire board to check each element.
13        for (int row = 0; row < 9; ++row) {
14            for (int col = 0; col < 9; ++col) {
15                // Read the current character.
16                char currentChar = board[row][col];
17              
18                // Skip if the cell is empty (denoted by '.').
19                if (currentChar == '.') continue;
20
21                // Convert char digit to integer index (0 to 8).
22                int num = currentChar - '0' - 1;
23
24                // Calculate sub-box index based on row and column.
25                int subBoxIndex = (row / 3) * 3 + (col / 3);
26
27                // Check if the number has already been used in the current row, column, or sub-box.
28                // If it has, then the Sudoku board is invalid.
29                if (rowCheck[row][num] || colCheck[col][num] || subBoxCheck[subBoxIndex][num]) {
30                    return false;
31                }
32
33                // Mark the number as used in the current row, column, and sub-box.
34                rowCheck[row][num] = true;
35                colCheck[col][num] = true;
36                subBoxCheck[subBoxIndex][num] = true;
37            }
38        }
39
40        // If all checks pass, then the board is valid.
41        return true;
42    }
43};
44
1function isValidSudoku(board: string[][]): boolean {
2    // Initialize boolean arrays to track the presence of digits in rows, columns, and sub-boxes.
3    const rowsTracker: boolean[][] = Array.from({ length: 9 }, () => new Array(9).fill(false));
4    const colsTracker: boolean[][] = Array.from({ length: 9 }, () => new Array(9).fill(false));
5    const subsTracker: boolean[][] = Array.from({ length: 9 }, () => new Array(9).fill(false));
6
7    // Loop through each cell of the board.
8    for (let i = 0; i < 9; i++) {
9        for (let j = 0; j < 9; j++) {
10            // Get the numeric value of the cell, if it's a number.
11            const num = board[i][j].charCodeAt(0) - '0'.charCodeAt(0) - 1; // Adjust ASCII '1' to index 0
12
13            // Skip the cell if it's not a valid number (i.e., '.').
14            if (num < 0 || num > 8) {
15                continue;
16            }
17
18            // Calculate the index for the sub-boxes.
19            const subBoxIndex = Math.floor(i / 3) * 3 + Math.floor(j / 3);
20
21            // Check whether the number has already appeared in the current row, column, or sub-box.
22            if (rowsTracker[i][num] || colsTracker[j][num] || subsTracker[subBoxIndex][num]) {
23                return false; // If the number has appeared, the board is not valid.
24            }
25
26            // Mark the number as seen in the current row, column, and sub-box.
27            rowsTracker[i][num] = true;
28            colsTracker[j][num] = true;
29            subsTracker[subBoxIndex][num] = true;
30        }
31    }
32
33    // If no duplicates were found, the board is valid.
34    return true;
35}
36

Time and Space Complexity

The time complexity of the provided code is O(n^2) where n is the length of one side of the Sudoku board. Since the board is always 9x9, the complexity can be considered O(1) because it does not scale with input size.

The space complexity of the code is also O(n^2) for similar reasons. We initialize three 2D arrays (row, col, and sub) to keep track of the numbers present in each row, column, and 3x3 subgrid. Again, since n = 9, the space complexity is essentially O(1).

Learn more about how to find time and space complexity quickly using problem constraints.


Fast Track Your Learning with Our Quick Skills Quiz:

What are the most two important steps in writing a depth first search function? (Select 2)


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Tired of the LeetCode Grind?

Our structured approach teaches you the patterns behind problems, so you can confidently solve any challenge. Get started now to land your dream tech job.

Get Started

🪄