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:

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.

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

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.