Problem Description

The goal of this problem is to develop a program that can solve a classic Sudoku puzzle. Sudoku is a number puzzle played on a 9x9 grid divided into 9 smaller 3x3 sub-grids (also known as blocks or boxes). The rules are simple but require some strategic thinking:

1. Each row of the grid must contain all digits from 1 to 9, with no repetition.
2. Each column must also contain all digits from 1 to 9, without repeating any numbers.
3. Similarly, each of the 9 sub-grids must contain all digits from 1 to 9.

The puzzle starts with some cells already filled with numbers, and the rest are left blank, indicated by a '.' character. The objective is to fill the empty cells with the correct digits.

Flowchart Walkthrough

Let's utilize the algorithm flowchart to analyze the problem-solving approach for LeetCode 37. Sudoku Solver:

1. Is it a graph?

   • No: While Sudoku is structured with rows, columns, and grids, it does not directly represent a graph problem involving nodes and edges.

2. Need to solve for kth smallest/largest?

   • No: The problem does not concern finding the kth smallest or largest element, but rather filling in a Sudoku board correctly.

3. Involves Linked Lists?

   • No: The problem does not involve any operations directly related to linked lists.

4. Does the problem have small constraints?

   • Yes: Sudoku is a highly constrained problem involving a 9x9 board, which is a finite and relatively small space to explore.

5. Brute force / Backtracking?

   • Yes: The standard solution for solving Sudoku involves a brute force approach to attempt filling each cell and backtracking when a violation of Sudoku rules is found.

Conclusion: Based on the deductions made using the flowchart, the suited approach for solving Sudoku involves backtracking. This is required to explore all potential arrangements till the board complies with all Sudoku rules properly. The small 9x9 board constraints justify the feasibility of this method.

Intuition

To solve the Sudoku puzzle, we can use a depth-first search (DFS) algorithm—a form of backtracking. Here's the intuition behind this approach:

1. Represent the Sudoku board as a 2D array where each empty cell is a decision point.
2. For each decision point (i.e., an empty cell), try all possible numbers from 1 to 9, subject to the Sudoku rules.
3. Before placing a number in an empty cell, check if it's a valid choice:
   • It must not already be present in the same row.
   • It must not already be present in the same column.
   • It must not already be present in the 3x3 sub-grid containing the cell.
4. If a number is valid, place it in the cell and move on to the next empty cell.
5. If at any point, a number cannot be placed in an empty cell (because all options have been exhausted and none are valid), backtrack to the previous cell and try a different number.
6. Continue this process until all cells are filled (sudoku solved), or you find that the puzzle is unsolvable with the current configuration (in which case, backtrack further).

The recursive DFS algorithm keeps track of which numbers are placed in which rows, columns, and blocks. This tracking allows the algorithm to quickly determine if a number can be placed in a cell. As soon as the solution is found, it's returned without further processing by setting a global flag, allowing the recursive calls to terminate quickly.

Learn more about Backtracking patterns.

Solution Approach

The solution uses Depth-First Search (DFS) with backtracking. Here's a breakdown of the implementation:

1. We define three lists to keep track of the numbers already used in each row, column, and block:

   • row[9][9]: Each element corresponds to a row and a digit, set to True if that digit is already used in the row.
   • col[9][9]: Similar to row, but tracks the columns.
   • block[3][3][9]: Each element corresponds to one of the nine blocks and a digit, where each block is a 3x3 grid.

2. A list t is used to store the indices (i, j) of all empty cells, which the algorithm will attempt to fill in.

3. A variable ok is used as a flag to indicate whether the solution is found. Initially, it's set to False.

4. Initialize the row, col, and block lists based on the existing digits on the board. If a cell contains a number, it updates the corresponding row, col, and block entries to True.

5. The dfs function is the core of the backtracking algorithm:

   • The base case is when the input index k is equal to the number of empty cells, meaning all cells have been successfully filled, and we set ok = True.
   • It iterates over all possible values v from 0 to 8 (which corresponds to the digits 1 to 9 on the board) for each empty cell.
   • It then checks if the value v has not been used in the row[i], col[j], and block[i // 3][j // 3]. If it hasn't, this value is placed in the cell, and the corresponding trackers are updated to True.
   • Recursively calls dfs(k + 1) to proceed to the next cell.
   • If placement of v leads to an invalid configuration later, it backtracks by resetting the trackers to False, which effectively removes the digit from the cell and tries the next digit.
   • If at any point ok becomes True, indicating all cells are filled correctly, the function returns immediately, so the recursion unwinds and the filled board is preserved.

6. To start the process, dfs(0) is called after initializing the trackers, which begins the search for the solution using the first empty cell.

7. Since we maintain a global tracker of rows, columns, and blocks, we ensure that the space complexity is kept to O(1) since the auxiliary space does not grow with the size of the input.

The solution modifies the input board in-place to represent the filled Sudoku board after the solveSudoku function completes execution. At the core, this approach is an efficient use of DFS and backtracking, which systematically explores the feasible solutions and backtracks as soon as a partial solution is determined to be invalid.

Example Walkthrough

Let's walk through an example to illustrate the solution approach. Consider a simplified 4x4 Sudoku puzzle with a single empty cell for ease of demonstration:

---------------------
| 1 | 2 | 3 | 4 |
---------------------
| 3 | 4 | 1 | 2 |
---------------------
| 2 | 1 | 4 |   |
---------------------
| 4 | 3 | 2 | 1 |
---------------------

In the above grid, the missing digit is in the third row and fourth column. According to our problem description, we have to fill this cell so that numbers 1 through 4 appear exactly once in each row, column, and 2x2 sub-grid.

Step by step, the backtracking algorithm would work as follows:

1. We represent our current state with the row, col, and block trackers. It would look something like this (simplified for the 4x4 grid):

   row = [
     [True, True, True, True],
     ...
   ]
   
   col = [
     [True, True, True, True],
     ...
   ]
   
   block = [
     [[True, True, True, True], [True, True, True, True]],
     ...
   ]

   And the list t of empty cells would hold just the index of the empty cell: [(2, 3)].

2. Next, we proceed with the depth-first search:

   The DFS function is called with k = 0, as we have only one empty cell.

3. Now, the DFS algorithm will try to fill this cell with a valid number. Starting from value v = 0 (representing digit '1'), it will check if that number has already been used in the same row, column, and block.

   For v = 0, we find that '1' is already present in the row and column, and so is '2' for v = 1, and '4' for v = 3. However, when v = 2, it represents the number '3', which satisfies our Sudoku rules:

   • '3' is not present in the same row (which already has '2', '1', '4').
   • '3' is not present in the same column (which already has '4', '1', '2').
   • '3' is not present in the same block.

4. Seeing that it's a valid number to place, the DFS function will place '3' into the grid and update the row, col, and block trackers for '3' in the corresponding indices.

5. With the value placed, the DFS algorithm checks if it has reached the base case (k equal to the number of elements in t), which it has, and it then sets the ok flag to True.

The newly filled grid would look like this:

---------------------
| 1 | 2 | 3 | 4 |
---------------------
| 3 | 4 | 1 | 2 |
---------------------
| 2 | 1 | 4 | 3 |
---------------------
| 4 | 3 | 2 | 1 |
---------------------

There is now a valid number in each row, column, and block. The ok flag being True will signal the end of the DFS call, and the backtracking will unwind having successfully filled in the puzzle.

Solution Implementation

Time and Space Complexity

Time Complexity

The given algorithm solves a Sudoku puzzle using Depth-First Search (DFS). For each empty cell, the algorithm tries out all possible numbers (1-9), and for each number, it checks whether placing it violates any Sudoku rules. If the placement is not violating the Sudoku rules, the algorithm proceeds to place the number and move onto the next empty cell.

The worst-case time complexity is difficult to determine precisely due to the nature of the problem, but a brute-force approach has an upper bound of O(9^m), where m is the number of empty spaces in the Sudoku puzzle. However, this bound is a vast overestimation, as the early pruning greatly reduces the search space. The actual time complexity is much lower, but an accurate analysis depends on the initial configuration of the Sudoku board.

Space Complexity

The space complexity of the algorithm includes the storage for the board, the hash-check arrays (row, col, block), and the call stack for recursion.

• The board itself will occupy O(9 * 9), which is constant O(1).
• The row, col, and block arrays have a space complexity of O(3 * 9 * 9) since we store boolean values representing whether a certain number is already used in the corresponding row, column, and block. This also simplifies to O(1) in the context of Sudoku, since these sizes do not scale with any variable input but are constants.

The majority of the space complexity comes from the depth of the recursion stack, which in the worst case can be as many as m function calls deep, where m is the number of empty spaces. Thus, the space complexity due to recursion is O(m).

Combining these, the total space complexity is the maximum of these two, resulting in O(m).

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