36. Valid Sudoku
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:
- Every row must have the digits
1-9
without any repetition. - Every column must have the digits
1-9
without any repetition. - Each of the nine
3 x 3
subgrids or boxes that compose the grid must have the digits1-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 have9
elements, with each element representing a row, column, or sub-grid, and each element is a9
elements list to keep track of digits1-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:
-
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 toFalse
, indicating that no numbers have been encountered yet.
-
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
). -
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. -
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.
- Ascertain the digit (converted to a zero-based index by
-
Validation Checks:
- If the number has already been seen in the current
row[i]
,col[j]
, orsub[k]
, returnFalse
since it violates the rules of Sudoku.
- If the number has already been seen in the current
-
Updating Structures:
- If the number hasn't been seen, we update
row[i][num]
,col[j][num]
, andsub[k][num]
toTrue
to indicate that the digit is now accounted for in the respective row, column, and sub-grid.
- If the number hasn't been seen, we update
-
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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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:
5 . . . 1 . . . 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:
Iteration 1: i = 0, j = 0 -> cell (0,0) contains '5' Iteration 2: i = 0, j = 1 -> cell (0,1) contains '.' Iteration 3: i = 0, j = 2 -> cell (0,2) contains '.' Iteration 4: i = 1, j = 0 -> cell (1,0) contains '.' Iteration 5: i = 1, j = 1 -> cell (1,1) contains '1' Iteration 6: i = 1, j = 2 -> cell (1,2) contains '.' Iteration 7: i = 2, j = 0 -> cell (2,0) contains '.' Iteration 8: i = 2, j = 1 -> cell (2,1) contains '.' Iteration 9: i = 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 us4
. - We identify the sub-grid using the formula
k = i // 3 * 3 + j // 3
. Here,k
is0
since bothi // 3
andj // 3
are0
.
Step 5: Validation Checks
- We check if the number '5' has been seen in
row[0][4]
,col[0][4]
, orsub[0][4]
. Since all areFalse
, we proceed.
Step 6: Updating Structures
-
We mark
row[0][4]
,col[0][4]
, andsub[0][4]
asTrue
, 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]
, andsub[0][0]
asTrue
. -
For the cell (2,2) containing '2', we mark
row[2][1]
,col[2][1]
, andsub[0][1]
asTrue
.
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.
Which data structure is used to implement recursion?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Donāt Miss This!