Hard Sudoku Solver Algorithm – Part 1

Hard Sudoku Solver Algorithm – Part 1

By | | Comments 0 Comment

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:

  1. Sudoku Solver
  2. Hard Sudoku Solver
  3. Hard Sudoku Solver 1

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 puzzle

Our 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:
Use r and c for iteration variables instead from i and j will 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.

Leave a Reply

Your email address will not be published. Required fields are marked *