Welcome to another exciting tutorial from AlgoCademy! Today, we’re diving into the world of Sudoku and exploring how to create an efficient Sudoku solver using programming. This project is not only fun but also an excellent exercise in algorithmic thinking and problem-solving skills – key attributes that top tech companies like FAANG (Facebook, Amazon, Apple, Netflix, and Google) look for in their candidates.
Sudoku, a popular number-placement puzzle, presents a perfect opportunity to apply various programming concepts and algorithms. By the end of this tutorial, you’ll have a deeper understanding of backtracking algorithms, constraint satisfaction problems, and how to approach complex logical challenges programmatically.
What is Sudoku?
Before we jump into the code, let’s briefly review what Sudoku is. 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.
A typical Sudoku puzzle provides a partially completed grid, and the solver must fill in the rest while adhering to the rules. The challenge lies in figuring out which numbers can be placed where, based on the given clues and the game’s constraints.
Approaching the Sudoku Solver
To create a Sudoku solver, we’ll use a technique called backtracking. Backtracking is a general algorithm for finding all (or some) solutions to computational problems, particularly constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate (“backtracks”) as soon as it determines that the candidate cannot possibly be completed to a valid solution.
Here’s a high-level overview of our approach:
- Find an empty cell in the Sudoku grid.
- Try placing a number (1-9) in that cell.
- Check if the placed number is valid according to Sudoku rules.
- If valid, recursively try to fill the rest of the grid.
- If not valid or if the recursive call fails, backtrack and try the next number.
- If all numbers (1-9) have been tried and none work, return false to trigger backtracking.
Implementing the Sudoku Solver in Python
Let’s start by implementing our Sudoku solver in Python. We’ll break down the solution into several functions to make it more manageable and easier to understand.
1. The Main Solver Function
First, let’s create our main solver function that will use backtracking to solve the Sudoku puzzle:
def solve_sudoku(board):
empty = find_empty(board)
if not empty:
return True
row, col = empty
for num in range(1, 10):
if is_valid(board, num, (row, col)):
board[row][col] = num
if solve_sudoku(board):
return True
board[row][col] = 0
return False
This function does the following:
- Finds an empty cell in the board.
- If there are no empty cells, the puzzle is solved, so it returns True.
- For each number from 1 to 9, it:
- Checks if the number is valid in the current cell.
- If valid, it places the number and recursively tries to solve the rest of the puzzle.
- If the recursive call returns True, the puzzle is solved.
- If not, it backtracks by setting the cell back to 0 and tries the next number.
- If no number works, it returns False to trigger backtracking.
2. Finding Empty Cells
Next, let’s implement the function to find empty cells in the Sudoku board:
def find_empty(board):
for i in range(len(board)):
for j in range(len(board[0])):
if board[i][j] == 0:
return (i, j) # row, col
return None
This function scans the board and returns the position (row, col) of the first empty cell it finds. If there are no empty cells, it returns None.
3. Validating Number Placement
Now, let’s create a function to check if a number is valid in a given position:
def is_valid(board, num, pos):
# Check row
for j in range(len(board[0])):
if board[pos[0]][j] == num and pos[1] != j:
return False
# Check column
for i in range(len(board)):
if board[i][pos[1]] == num and pos[0] != i:
return False
# Check 3x3 box
box_x = pos[1] // 3
box_y = pos[0] // 3
for i in range(box_y * 3, box_y * 3 + 3):
for j in range(box_x * 3, box_x * 3 + 3):
if board[i][j] == num and (i, j) != pos:
return False
return True
This function checks if a number is valid in a given position by:
- Checking the row for any duplicate numbers.
- Checking the column for any duplicate numbers.
- Checking the 3×3 box containing the position for any duplicate numbers.
4. Printing the Sudoku Board
To visualize our Sudoku board, let’s create a function to print it:
def print_board(board):
for i in range(len(board)):
if i % 3 == 0 and i != 0:
print("- - - - - - - - - - - - - ")
for j in range(len(board[0])):
if j % 3 == 0 and j != 0:
print(" | ", end="")
if j == 8:
print(board[i][j])
else:
print(str(board[i][j]) + " ", end="")
This function prints the Sudoku board with lines separating the 3×3 boxes for better visibility.
5. Putting It All Together
Now that we have all our functions, let’s use them to solve a Sudoku puzzle:
board = [
[5, 3, 0, 0, 7, 0, 0, 0, 0],
[6, 0, 0, 1, 9, 5, 0, 0, 0],
[0, 9, 8, 0, 0, 0, 0, 6, 0],
[8, 0, 0, 0, 6, 0, 0, 0, 3],
[4, 0, 0, 8, 0, 3, 0, 0, 1],
[7, 0, 0, 0, 2, 0, 0, 0, 6],
[0, 6, 0, 0, 0, 0, 2, 8, 0],
[0, 0, 0, 4, 1, 9, 0, 0, 5],
[0, 0, 0, 0, 8, 0, 0, 7, 9]
]
print("Sudoku Puzzle:")
print_board(board)
print("\nSolving...\n")
if solve_sudoku(board):
print("Sudoku Solution:")
print_board(board)
else:
print("No solution exists")
This code creates a Sudoku board, prints the initial state, solves the puzzle, and then prints the solution if one exists.
Understanding the Algorithm
The backtracking algorithm we’ve implemented is a form of depth-first search. It works by making a series of choices and exploring their consequences. If a choice leads to an invalid state, the algorithm “backtracks” by undoing the last choice and trying a different one.
In the context of our Sudoku solver:
- We start with an empty cell and try placing a number (1-9) in it.
- We then move to the next empty cell and repeat the process.
- If at any point we can’t place a valid number in a cell, we backtrack to the previous cell and try the next number.
- This process continues until we either find a solution or exhaust all possibilities.
This approach ensures that we explore all possible combinations until we find a valid solution or determine that no solution exists.
Time Complexity Analysis
The time complexity of this Sudoku solver is O(9^(n*n)), where n is the size of the board (9 in a standard Sudoku). This is because for each empty cell, we have 9 possible numbers to try, and in the worst case, we might need to try all possibilities for every cell.
While this exponential time complexity might seem alarming, in practice, the solver is usually much faster. This is because:
- Many Sudoku puzzles have multiple solutions, and we stop at the first one we find.
- The constraints of Sudoku (numbers must be unique in rows, columns, and 3×3 boxes) significantly reduce the number of possibilities we need to explore.
- Well-designed Sudoku puzzles typically have a unique solution that can be found relatively quickly.
Optimizations and Variations
While our current implementation works well, there are several ways we could optimize it or create variations:
1. Use a Set for Faster Checking
Instead of checking rows, columns, and boxes each time, we could maintain sets for each row, column, and box. This would allow for O(1) checking of number validity:
def initialize_sets(board):
rows = [set() for _ in range(9)]
cols = [set() for _ in range(9)]
boxes = [set() for _ in range(9)]
for i in range(9):
for j in range(9):
num = board[i][j]
if num != 0:
rows[i].add(num)
cols[j].add(num)
box_id = (i // 3) * 3 + j // 3
boxes[box_id].add(num)
return rows, cols, boxes
def is_valid_fast(num, row, col, rows, cols, boxes):
box_id = (row // 3) * 3 + col // 3
return num not in rows[row] and num not in cols[col] and num not in boxes[box_id]
2. Implement a Constraint Propagation Algorithm
We could implement a more advanced algorithm that uses constraint propagation to reduce the number of possibilities for each cell before resorting to backtracking. This is how many advanced Sudoku solvers work:
def eliminate(values):
solved_values = [box for box in values.keys() if len(values[box]) == 1]
for box in solved_values:
digit = values[box][0]
for peer in peers[box]:
values[peer] = values[peer].replace(digit,'')
return values
def only_choice(values):
for unit in unitlist:
for digit in '123456789':
dplaces = [box for box in unit if digit in values[box]]
if len(dplaces) == 1:
values[dplaces[0]] = digit
return values
def reduce_puzzle(values):
stalled = False
while not stalled:
solved_values_before = len([box for box in values.keys() if len(values[box]) == 1])
values = eliminate(values)
values = only_choice(values)
solved_values_after = len([box for box in values.keys() if len(values[box]) == 1])
stalled = solved_values_before == solved_values_after
if len([box for box in values.keys() if len(values[box]) == 0]):
return False
return values
3. Implement a Dancing Links Algorithm
For extremely fast Sudoku solving, we could implement Donald Knuth’s Dancing Links algorithm, which is particularly efficient for exact cover problems like Sudoku:
class DancingLinks:
def __init__(self):
self.header = ColumnNode('header')
self.solution = []
self.search_count = 0
def solve(self, matrix):
self.build_links(matrix)
self.search(0)
def build_links(self, matrix):
column_nodes = [self.header]
for j in range(len(matrix[0])):
n = ColumnNode(str(j))
column_nodes.append(n)
self.header.left.right = n
n.left = self.header.left
n.right = self.header
self.header.left = n
for i in range(len(matrix)):
previous = None
for j in range(len(matrix[0])):
if matrix[i][j]:
col = column_nodes[j+1]
node = Node(col, i)
if previous:
node.left = previous
node.right = previous.right
node.left.right = node
node.right.left = node
else:
node.left = node
node.right = node
previous = node
col.up.down = node
node.up = col.up
col.up = node
node.down = col
col.size += 1
def search(self, k):
if self.header.right == self.header:
self.print_solution()
return
col = self.choose_column()
col.cover()
r = col.down
while r != col:
self.solution.append(r)
j = r.right
while j != r:
j.column.cover()
j = j.right
self.search(k + 1)
r = self.solution.pop()
col = r.column
j = r.left
while j != r:
j.column.uncover()
j = j.left
r = r.down
col.uncover()
def choose_column(self):
min_size = float('inf')
chosen_col = None
col = self.header.right
while col != self.header:
if col.size < min_size:
min_size = col.size
chosen_col = col
col = col.right
return chosen_col
def print_solution(self):
for row in self.solution:
print(row.row_num, end=' ')
print()
class Node:
def __init__(self, column, row_num):
self.column = column
self.row_num = row_num
self.up = None
self.down = None
self.left = None
self.right = None
class ColumnNode(Node):
def __init__(self, name):
super().__init__(self, name)
self.size = 0
def cover(self):
self.right.left = self.left
self.left.right = self.right
i = self.down
while i != self:
j = i.right
while j != i:
j.down.up = j.up
j.up.down = j.down
j.column.size -= 1
j = j.right
i = i.down
def uncover(self):
i = self.up
while i != self:
j = i.left
while j != i:
j.column.size += 1
j.down.up = j
j.up.down = j
j = j.left
i = i.up
self.right.left = self
self.left.right = self
Conclusion
Congratulations! You’ve successfully implemented a Sudoku solver using the backtracking algorithm. This project demonstrates several important concepts in computer science and programming:
- Backtracking: A powerful algorithmic technique for solving problems incrementally by trying to build a solution step by step and abandoning solutions that fail to meet the problem’s constraints.
- Recursion: The solve_sudoku function calls itself, showcasing how complex problems can be broken down into smaller, similar subproblems.
- 2D Array Manipulation: The Sudoku grid is represented as a 2D array, and we’ve practiced accessing and modifying its elements.
- Problem Decomposition: We broke down the problem into smaller functions (find_empty, is_valid, print_board), making the code more readable and maintainable.
This Sudoku solver is not just a fun project; it’s an excellent example of the type of algorithmic thinking and problem-solving skills that top tech companies value. The ability to break down complex problems, implement efficient solutions, and understand algorithmic complexity are crucial skills for coding interviews and real-world software development.
As you continue your journey with AlgoCademy, consider exploring more advanced topics like dynamic programming, graph algorithms, and system design. These areas will further enhance your problem-solving skills and prepare you for technical interviews at leading tech companies.
Remember, the key to mastering these concepts is practice. Try modifying the Sudoku solver to handle different board sizes, implement some of the optimizations we discussed, or even create a Sudoku puzzle generator. Happy coding, and keep pushing your boundaries in the exciting world of algorithms and data structures!