Hard Sudoku Solver Algorithm – Part 1
Introduction
How fast is your sudoku solver algorithm? Can it beat the time limit on this Codewars challenge? If you get a timeout, welcome to my world! 😀
In this two-part blog series, I’m going to share my experience while solving the sudoku challenges on Codewars. Part 1 will try to solve easier puzzles while Part 2 will try to solve harder ones.
The challenges that I will try to solve are listed below:
Challenge 1 and challenge 2 only require us to find one solution, so the running time is not that critical. However, Challenge 3 requires us to find all solutions, so it’s more challenging to beat the running time limit.
This blog will focus on solving challenge 2 Hard Sudoku Solver, leaving challenge 3 Hard Sudoku Solver 1 for the next blog.
Note that the solution in this blog can be used to pass both challenge 1 and 2, without any modification or optimization.
It is recommended that you try to practice on your own first before going on to read the solution.
Problem description
From Codewars’ Hard Sudoku Solver:
This kata is a harder version of Sudoku Solver made by @pineappleclock
Write a function that will solve a 9×9 Sudoku puzzle. The function will take one argument consisting of the 2D puzzle array, with the value 0 representing an unknown square.
The Sudokus tested against your function will be “insane” and can have multiple solutions. The solution only need to give one valid solution in the case of the multiple solution sodoku.
It might require some sort of brute force.
Consider applying algorithm with
For Sudoku rules, see the Wikipedia article.
Used puzzle from Extreme Sudoku.
We have to write a function like this:
def solve(puzzle): """return the solved puzzle as a 2d array of 9 x 9""" return puzzleOur function should solve puzzles like this:
puzzle = \ [[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]] solve(puzzle)The function should return solution like this:
[[5,3,4,6,7,8,9,1,2], [6,7,2,1,9,5,3,4,8], [1,9,8,3,4,2,5,6,7], [8,5,9,7,6,1,4,2,3], [4,2,6,8,5,3,7,9,1], [7,1,3,9,2,4,8,5,6], [9,6,1,5,3,7,2,8,4], [2,8,7,4,1,9,6,3,5], [3,4,5,2,8,6,1,7,9]]
Solution
Although the testing puzzles to are going to be “hard”, the challenge only require us to return one solution. Therefore, we can use the simplest algorithms to beat it within the allowed time frame. I’m going to use backtracking to solve the problem.
The algorithm
For the sake of applying backtracking, we will count the cells like this.
Small tip from Professor Robert Sedgewick:
Userandcfor iteration variables instead fromiandjwill make the code less confusing and more readable.
The algorithm goes like this:
- Recursively solve the board, starting from cell k=0
- For each cell k, try to fill every possible value in cell k.
- With each value filled in cell k, try to solve the board from cell k+1 with the current board status
- If solving from cell k+1 return a solution: return True
- Otherwise, try another value in cell k
- If all values have been tried without finding a solution: return False
Note that in the above algorithm, every time we try to solve the board at cell k, we know that all cells from 0 to k-1 has already been filled with either the initial given puzzle value, or with a “test value” at a previous step.
Sample code
The following sample code is written in Python.
def solve(board):
sudoku = Sudoku(board)
result = sudoku.solve()
return result
class Sudoku:
result = []
board = []
def __init__(self, board):
self.board = board
# check if value x can be put at cell[row][col]
# return False if value x has already been used in other cells on current row, or column, or 3x3 box
# return True otherwise
def check(self, row, col, x):
for i in range(9):
if self.board[row][i] == x:
return False
if self.board[i][col] == x:
return False
box_start_row = row - row % 3
box_start_col = col - col % 3
for r in range(box_start_row, box_start_row + 3):
for c in range(box_start_col, box_start_col + 3):
if self.board[r][c] == x:
return False
return True
# solve the sudoku and return one result
def solve(self):
# init the solve_helper at cell (0, 0)
if self.solve_helper(0):
return self.board
else:
return None
# given the sudoku has been filled up to cell k-1, try to solve the sudoku from cell k
# k is the cell index, counting from left to right and top to bottom.
# k is 0, 1, 2, ..., 8 for cell (0,0), (0,1), (0,2), ..., (0,8)
# k is 9, 10, 11, ..., for cell (1,0), (1,1), (1,2), ...
# k is 80 for cell (8,8) (last cell)
def solve_helper(self, k):
# if we get pass the last cell, it means we have filled every cells with valid values.
# return True to notify that we have found a solution
if (k > 80):
return True
r = int(k / 9)
c = k % 9
# if this cell has been filled, go on to solve the next cell
if self.board[r][c] != 0:
return self.solve_helper(k+1)
# try to fill each value from 1 to 9 in this cell
for x in range(1, 10):
# fill the cell with value x only if x has not appeared on the same row or col or 3x3 box
if self.check(r, c, x):
# start backtracking:
# try x in this cell,
self.board[r][c] = x
# then try to solve from the next cell k+1,
if self.solve_helper(k+1):
# solving from k+1 did find one solution (because solve_helper(k+1) returned True)
# since we only need 1 solution, we can stop further processing and return here
# return True to notify upper recursive solve_helper that we found a solution.
return True
# then clear cell to return the board to the status before x was filled
self.board[r][c] = 0
# if we are here, it means we have tried all values in this cell without finding a solution
# return False to notify upper recursive solve_helper that
# we didn't find any solution given the current board status
return False
Test the code
problem = \
[[9, 0, 0, 0, 8, 0, 0, 0, 1],
[0, 0, 0, 4, 0, 6, 0, 0, 0],
[0, 0, 5, 0, 7, 0, 3, 0, 0],
[0, 6, 0, 0, 0, 0, 0, 4, 0],
[4, 0, 1, 0, 6, 0, 5, 0, 8],
[0, 9, 0, 0, 0, 0, 0, 2, 0],
[0, 0, 7, 0, 3, 0, 2, 0, 0],
[0, 0, 0, 7, 0, 5, 0, 0, 0],
[1, 0, 0, 0, 4, 0, 0, 0, 7]]
solution = \
[[9, 2, 6, 5, 8, 3, 4, 7, 1],
[7, 1, 3, 4, 2, 6, 9, 8, 5],
[8, 4, 5, 9, 7, 1, 3, 6, 2],
[3, 6, 2, 8, 5, 7, 1, 4, 9],
[4, 7, 1, 2, 6, 9, 5, 3, 8],
[5, 9, 8, 3, 1, 4, 7, 2, 6],
[6, 5, 7, 1, 3, 8, 2, 9, 4],
[2, 8, 4, 7, 9, 5, 6, 1, 3],
[1, 3, 9, 6, 4, 2, 8, 5, 7]]
assert(solve(problem) == solution)
Result
Try to submit this code on Codewars, we can pass all tests. Yay!
Conclusion
In this blog, we have solved the hard sudoku problem using the backtracking approach. However this algorithm cannot beat the time limit on this harder challenge.
In the next part, we are going to discuss how to optimize the algorithm to pass all the tests of the harder challenge within the time limit.