Day 50: Sudoku Solver#

Welcome to Day 50 of our 60 Days of Coding Algorithm Challenge! Today, we’ll tackle the Sudoku Solver problem, another classic application of backtracking algorithms.

What is Sudoku?#

Sudoku is a logic-based number-placement puzzle. The objective is to fill a 9×9 grid with digits so that each column, row, and 3×3 sub-grid contains all digits from 1 to 9 without repetition.

Understanding the Problem#

• We have a 9×9 grid, partially filled with digits from 1 to 9.
• Empty cells are represented by 0 or ‘.’.
• We need to fill all empty cells following Sudoku rules.
• A valid Sudoku solution must satisfy:
  1. Each row contains digits 1-9 without repetition.
  2. Each column contains digits 1-9 without repetition.
  3. Each of the nine 3×3 sub-grids contains digits 1-9 without repetition.

Backtracking Approach#

We’ll use a backtracking approach to solve this problem:

1. Find an empty cell.
2. Try placing digits 1-9 in this cell.
3. Check if the digit is valid in the current cell.
4. If valid, recursively try to fill the rest of the grid.
5. If the recursive call is successful, return true.
6. If not successful, backtrack and try the next number.
7. If all numbers (1-9) have been tried and nothing worked, return false to trigger backtracking.

Implementation#

Here’s a Python implementation of the Sudoku Solver:

 1def solve_sudoku(board):
 2    def is_valid(num, pos):
 3        # Check row
 4        for i in range(9):
 5            if board[pos[0]][i] == num and pos[1] != i:
 6                return False
 7
 8        # Check column
 9        for i in range(9):
10            if board[i][pos[1]] == num and pos[0] != i:
11                return False
12
13        # Check 3x3 box
14        box_x = pos[1] // 3
15        box_y = pos[0] // 3
16
17        for i in range(box_y * 3, box_y * 3 + 3):
18            for j in range(box_x * 3, box_x * 3 + 3):
19                if board[i][j] == num and (i, j) != pos:
20                    return False
21
22        return True
23
24    def find_empty():
25        for i in range(9):
26            for j in range(9):
27                if board[i][j] == 0:
28                    return (i, j)
29        return None
30
31    def solve():
32        find = find_empty()
33        if not find:
34            return True
35        else:
36            row, col = find
37
38        for i in range(1, 10):
39            if is_valid(i, (row, col)):
40                board[row][col] = i
41
42                if solve():
43                    return True
44
45                board[row][col] = 0
46
47        return False
48
49    solve()
50    return board
51
52# Example usage
53board = [
54    [5, 3, 0, 0, 7, 0, 0, 0, 0],
55    [6, 0, 0, 1, 9, 5, 0, 0, 0],
56    [0, 9, 8, 0, 0, 0, 0, 6, 0],
57    [8, 0, 0, 0, 6, 0, 0, 0, 3],
58    [4, 0, 0, 8, 0, 3, 0, 0, 1],
59    [7, 0, 0, 0, 2, 0, 0, 0, 6],
60    [0, 6, 0, 0, 0, 0, 2, 8, 0],
61    [0, 0, 0, 4, 1, 9, 0, 0, 5],
62    [0, 0, 0, 0, 8, 0, 0, 7, 9]
63]
64
65solved_board = solve_sudoku(board)
66for row in solved_board:
67    print(row)

Time Complexity#

The time complexity of the Sudoku solver is O(9^(nn)), where n is the size of the board (9 in standard Sudoku). This is because for each empty cell, we try up to 9 numbers, and there are nn cells.

Space Complexity#

The space complexity is O(nn) to store the board, plus the space used by the recursion stack, which can go up to O(nn) in the worst case.

Optimizations#

1. Constraint Propagation: Reduce the number of possibilities for each cell based on the current state of the board.
2. Minimum Remaining Values (MRV): Choose the cell with the fewest possible values to fill next.
3. Bitmasking: Use bitwise operations to efficiently check and update valid numbers for each cell.

Variations of the Problem#

1. Solve different Sudoku variants: Like 16×16 Sudoku, Killer Sudoku, or Jigsaw Sudoku.
2. Sudoku Generator: Create a program that generates valid Sudoku puzzles.
3. Optimize for Minimal Clues: Find the minimum number of filled cells needed to ensure a unique solution.

Real-world Applications#

While Sudoku solving itself is primarily a puzzle, the techniques used have applications in:

1. Constraint satisfaction problems
2. Timetable scheduling
3. Resource allocation problems
4. Configuration problems in artificial intelligence

Exercise#

1. Modify the solver to work with different sized Sudoku grids (e.g., 4x4, 16x16).
2. Implement a Sudoku generator that creates valid, solvable Sudoku puzzles.
3. Extend the solver to handle Killer Sudoku, where cells are grouped and must sum to a given value.

Summary#

Today, we explored the Sudoku Solver problem, another classic application of backtracking algorithms. We implemented a solution, discussed its time and space complexity, and looked at possible optimizations and variations of the problem.

The Sudoku Solver demonstrates the power of backtracking in solving complex constraint satisfaction problems. The techniques we’ve learned here can be applied to a wide range of problems in computer science and beyond.

Tomorrow, we’ll dive into dynamic programming with the “Longest Common Subsequence” problem. Stay tuned!

Solution#

 1# Exercise 1: A generic Sudoku solver that works for any perfect-square grid
 2# (4x4, 9x9, 16x16). box_size is the square root of the side length.
 3def solve_generic_sudoku(board):
 4    n = len(board)
 5    box = int(n ** 0.5)  # 3 for a 9x9 grid, 2 for a 4x4 grid.
 6
 7    def is_valid(r, c, val):
 8        for i in range(n):
 9            if board[r][i] == val or board[i][c] == val:
10                return False
11        br, bc = (r // box) * box, (c // box) * box
12        for i in range(br, br + box):
13            for j in range(bc, bc + box):
14                if board[i][j] == val:
15                    return False
16        return True
17
18    def solve():
19        for r in range(n):
20            for c in range(n):
21                if board[r][c] == 0:              # Empty cell.
22                    for val in range(1, n + 1):
23                        if is_valid(r, c, val):
24                            board[r][c] = val       # Choose.
25                            if solve():             # Explore.
26                                return True
27                            board[r][c] = 0         # Backtrack.
28                    return False                    # No digit fit here.
29        return True                                 # No empty cells left.
30
31    solve()
32    return board
33
34grid = [
35    [1, 0, 0, 0],
36    [0, 0, 0, 2],
37    [0, 3, 0, 0],
38    [0, 0, 0, 4],
39]
40for row in solve_generic_sudoku(grid):
41    print(row)