Sudoku Solver LeetCode

Solving a Sudoku puzzle involves filling empty cells with digits from 1 to 9, ensuring each row, column, and 3x3 sub-grid contains unique numbers. Sudoku Solver LeetCode problem is significant as it requires logical reasoning and algorithmic techniques to deduce the correct arrangement of numbers. We must find a solution that satisfies the Sudoku rules. Each row, column, and 3x3 sub-grid must contain unique numbers from 1 to 9.

Problem statement

We have to design an algorithm to solve Sudoku puzzles programmatically. Given a partially filled 9x9 grid representing a Sudoku puzzle, our task is to fill in the empty cells while adhering to the following constraints:

  1. Each row of the grid must contain unique digits from 1 to 9.

  2. Each column of the grid must contain unique digits from 1 to 9.

  3. Each of the 9 non-overlapping 3x3 sub-grids within the grid must contain unique digits from 1 to 9.

  4. The grid may contain some cells initially filled with digits from 1 to 9, denoted by the ‘.’ character.

Sudoku puzzle
Sudoku puzzle
1 of 2

Our solution should efficiently determine the correct arrangement of digits to complete the Sudoku puzzle.

Knowledge test

Now that we have understood the problem, let’s check our knowledge by trying to solve the question below:

What is the significance of checking rows, columns, and 3x3 sub-boxes in the Sudoku Solver algorithm?

Algorithm

The algorithm we will use to solve Sudoku puzzles is backtracking. Backtracking is a technique for systematically searching for solutions to a problem by exploring all possible candidates. In the case of Sudoku, the algorithm recursively tries different numbers in each empty cell until a valid solution is found.

Consider a partially filled Sudoku grid:

Sudoku puzzle
Sudoku puzzle
  1. The algorithm begins by initializing sets to keep track of numbers in each row, column, and 3x3 box. Then, it populates these sets with existing numbers from the board. The rows, columns, and boxes after initialization will be as follows:

Columns
Columns
1 of 3
  1. Next, it defines the backtracking function, which recursively explores possible solutions. Let’s look into the backtracking function in depth:

    1. Base case: When the function has traversed the entire board, it indicates that a solution has been found. At this point, the function stops and prints the solution.

    2. Choosing the next cell: The function iterates through each cell of the Sudoku grid, moving row by row from left to right and top to bottom. It calculates the indexes of the next cell to explore, ensuring systematic traversal of the puzzle.

    3. Validating empty cells: Before attempting to fill an empty cell, the function checks if the cell is already filled. If so, it skips to the next cell.

    4. Trying numbers: If the current cell is empty, the function iterates through numbers from 1 to 9. For each number, it validates whether placing that number in the current cell violates Sudoku rules. If the number satisfies these conditions, it proceeds to fill the cell with that number.

    5. Recursion: After placing a valid number in the current cell, the function recursively calls itself to explore the next cell. This recursive exploration continues until a solution is found or until all possibilities have been exhausted.

    6. Backtracking: If no solution is found after exploring a certain path, the function backtracks to the previous cell and tries a different number. It restores the state of the puzzle to its previous configuration before attempting the next possibility. This process of backtracking ensures that all possible configurations are systematically explored, optimizing the search for a solution.

For example, let’s look at the first empty cell in the puzzle above (0, 2): The backtracking function will try numbers from 1 to 9. Suppose placing 4 in this cell satisfies Sudoku rules. It will add 4 to row 0 and column 2. Further, the corresponding box ID will be calculated based on (0, 2), and 4 will be added to the respective box set in boxes. The board[0][2] will also be updated to 4. This process continues until a valid solution is found or all possibilities are exhausted.

Coding example

Let’s code our algorithm for creating a Sudoku solver.

def print_board(board):
"""Function to print the Sudoku board."""
for row in board:
print(" ".join(row))
def backtracking(i, j, board, rows, cols, boxes):
"""Backtracking function to solve the Sudoku puzzle."""
if i == 9:
return True # Solution found
new_i = i + (j + 1) // 9
new_j = (j + 1) % 9
if board[i][j] != '.':
return backtracking(new_i, new_j, board, rows, cols, boxes)
else:
for num in range(1, 10):
box_id = (i // 3) * 3 + (j // 3)
if num not in rows[i] and num not in cols[j] and num not in boxes[box_id]:
rows[i].add(num)
cols[j].add(num)
boxes[box_id].add(num)
board[i][j] = str(num)
if backtracking(new_i, new_j, board, rows, cols, boxes):
return True # Solution found
# Backtrack
rows[i].remove(num)
cols[j].remove(num)
boxes[box_id].remove(num)
board[i][j] = '.'
return False # No solution found
def solve_sudoku(board):
"""Function to solve the Sudoku puzzle."""
rows = [set() for _ in range(9)]
cols = [set() for _ in range(9)]
boxes = [set() for _ in range(9)]
# Populate the sets with existing numbers from the board
for i in range(9):
for j in range(9):
if board[i][j] != ".":
num = int(board[i][j])
rows[i].add(num)
cols[j].add(num)
box_id = i // 3 * 3 + j // 3
boxes[box_id].add(num)
# Start backtracking from the first cell
if backtracking(0, 0, board, rows, cols, boxes):
print_board(board) # Print the solution
else:
print("No solution exists")
# Test Sudoku board
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"],
]
# Call the function to solve the Sudoku puzzle
solve_sudoku(board)
Sudoku Solver implementation in Python

Let’s see the explanation of the Python code.

Code explanation

Here’s the explanation of Python code:

  • Lines 2–3: We define a function print_board, which takes a board as input and prints it in a readable format. Inside the function, a loop iterates through each row of the board, joining the elements with spaces before printing.

  • Lines 19–20: We define another function named backtracking, which implements the recursive backtracking algorithm to solve the Sudoku puzzle. The function checks if the current row index i equals 9, indicating that all rows have been processed. If this condition is met, it returns True, signaling that a solution has been found.

  • Lines 23–25: We calculate the indices for the next cell to be processed. The new row index (new_i) is determined by adding 1 to the current row index i when the column index j reaches the end of a row (i.e., j == 8). The new column index (new_j) is calculated using modulo to ensure it cycles back to the beginning of the row when reaching the end.

  • Lines 28–29: We check if the current cell is not empty (indicated by ‘.’). If it contains a number, the function recursively calls itself with the new indices to continue processing the next cell.

  • Lines 32–34: If the current cell is empty, the function enters a loop where it attempts to place each number from 1 to 9 into the cell. For each number, it calculates the ID of the corresponding 3x3 box based on the current cell’s indices.

  • Lines 37–39: The function checks if the current number can be placed in the cell. It verifies that the number is not already present in the same row, column, or 3x3 box, ensuring it adheres to Sudoku rules.

  • Lines 41–46: If the number can be placed, it updates the row, column, and box sets to reflect the addition of the number. It also updates the board with the current number and recursively calls the backtracking function to attempt to solve for the next cell.

  • Lines 50–54: After placing a number, if the recursive call returns True, it indicates a solution has been found. If the call does not lead to a solution, the algorithm backtracks by removing the number from the sets and resetting the cell to ‘.’ to allow for other possibilities.

  • Lines 57–59: If no numbers can be placed in the current cell that leads to a solution, the function returns False, indicating that the current path does not yield a valid Sudoku solution.

  • Lines 60–67: The solve_sudoku function initializes sets for rows, columns, and boxes to keep track of numbers already in use. It populates these sets with existing numbers from the board using a nested loop that iterates through each cell.

  • Lines 70–73: Finally, the function initiates the backtracking process from the first cell of the board. If a solution is found, it prints the solved board; otherwise, it prints a message indicating that no solution exists.

  • Lines 76–84: A predefined Sudoku board is provided to test the solve_sudoku function. The solve_sudoku function is then called with this board as input.

Time complexity

The time complexity of populating the sets with existing numbers from the board is O(1)O(1) for each cell, resulting in O(81)O(81) = O(1)O(1) in total. The backtracking algorithm explores all possible configurations, resulting in exponential time complexity. In the worst case, the algorithm explores 9(n2)9^{(n^2)} configurations, where nn is the size of the Sudoku board. Therefore, the overall time complexity of the algorithm is exponential, O(9(n2))O(9^{(n^2)}).

Space complexity

There are three sets (rows, cols, boxes) of size 9, resulting in O(9)O(9) = O(1)O(1) space complexity. Further, the backtracking algorithm utilizes recursion, which consumes additional space on the call stack proportional to the depth of recursion. In the worst case, the recursion depth can be the number of cells on the board, which is O(n2)O(n^2) for a Sudoku puzzle of size nn. Additionally, the solved flag and temporary variables (new_i, new_j, num, box_id) consume constant space. Therefore, the overall space complexity is O(1)O(1) for the sets and O(n2)O(n^2) for the recursion stack, resulting in O(n2)O(n^2) space complexity.

Copyright ©2024 Educative, Inc. All rights reserved