Introduction

In part 1, we have solved some hard sudoku puzzles using the backtracking approach. While the algorithm did the job, it couln’t beat the time limit in the more advanced challenge: Hard Sudoku Solver 1.

This time, we are going to find a better solution so that we can pass the tests in the new challenge within the 10-second time limit.

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 1:

There are several difficulty of sudoku games, we can estimate the difficulty of a sudoku game based on how many cells are given of the 81 cells of the game.

• Easy sudoku generally have over 32 givens
• Medium sudoku have around 30–32 givens
• Hard sudoku have around 28–30 givens
• Very Hard sudoku have less than 28 givens

Note: The minimum of givens required to create a unique (with no multiple solutions) sudoku game is 17.

A hard sudoku game means that at start no cell will have a single candidates and thus require guessing and trial and error. A very hard will have several layers of multiple candidates for any empty cell.

Your Task

Write a function that solves sudoku puzzles of any difficulty. The function will take a sudoku grid and it should return a 9×9 array with the proper answer for the puzzle.

Or it should raise an error in cases of: invalid grid (not 9×9, cell with values not in the range 1~9); multiple solutions for the same puzzle or the puzzle is unsolvable.

Analysis

Compared to the problem in part 1, this problem requires us to raise an error if there are more than one solution to the sudoku. Therefore, instead of return the first solution we found, we have to keep testing other possibilities to make sure that there are no other solution to the sudoku. The good news is, we can return an error early immediately when we found the second solution.

The hardest test that we are going to solve is the puzzle below, which has only 17 given numbers:

#### Should solve very hard puzzle
puzzle = \
    [[8, 0, 0, 0, 0, 0, 0, 0, 0],
     [0, 0, 3, 6, 0, 0, 0, 0, 0],
     [0, 7, 0, 0, 9, 0, 2, 0, 0],
     [0, 5, 0, 0, 0, 7, 0, 0, 0],
     [0, 0, 0, 0, 4, 5, 7, 0, 0],
     [0, 0, 0, 1, 0, 0, 0, 3, 0],
     [0, 0, 1, 0, 0, 0, 0, 6, 8],
     [0, 0, 8, 5, 0, 0, 0, 1, 0],
     [0, 9, 0, 0, 0, 0, 4, 0, 0]]
solution = \
    [[8, 1, 2, 7, 5, 3, 6, 4, 9],
     [9, 4, 3, 6, 8, 2, 1, 7, 5],
     [6, 7, 5, 4, 9, 1, 2, 8, 3],
     [1, 5, 4, 2, 3, 7, 8, 9, 6],
     [3, 6, 9, 8, 4, 5, 7, 2, 1],
     [2, 8, 7, 1, 6, 9, 5, 3, 4],
     [5, 2, 1, 9, 7, 4, 3, 6, 8],
     [4, 3, 8, 5, 2, 6, 9, 1, 7],
     [7, 9, 6, 3, 1, 8, 4, 5, 2]]
assert(sudoku_solver(puzzle) == solution)

The backtracking approach

The first thing that we want to try is of course reusing the solution from the last challenge, with some modifications to fit the new additional requirements.

The sample code goes as below:

import copy

def sudoku_solver(puzzle):
    sudoku = Sudoku(puzzle)
    if not sudoku.valid:
        raise ValueError

    sudoku.solve()

    if len(sudoku.solutions) != 1:
        raise ValueError

    return sudoku.solutions[0]

class Sudoku:

    def __init__(self, board):
        # the 9x9 sudoku board
        self.board = []
        # list of solutions to this sudoku
        self.solutions = []
        # is the board valid
        self.valid = True


        # init a blank board with all cells filled with zero
        for i in range(9):
            r = [0] * 9
            self.board.append(r)

        # check the input board dimensions
        if not self.validate(board):
            self.valid = False

        # copy the input board to self.board
        for r in range(len(board)):
            for c in range(len(board[r])):
                if board[r][c]:
                    if not self.set(r, c, board[r][c]):
                        self.valid = False


    # validate board dimensions
    def validate(self, board):
        if len(board) != 9:
            return False
        for r in range(len(board)):
            if len(board[r]) != 9:
                return False
        return True

    # the main function to solve the sudoku
    def solve(self):
        # recursively solve the sudoku, starting from cell 0
        self.solve_helper(0)
        return self.solutions

    # 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):
            self.solutions.append(copy.deepcopy(self.board))
            return

        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,
                self.solve_helper(k+1)
                if len(self.solutions) >= 2:
                    # the problem requires us raise error if there are more than one solution,
                    # so we can skip further processing if 2 solutions have been found
                    return
                # 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

    # 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):
        if not isinstance(x, int):
            return False
        if x < 1 or x > 9:
            return False
        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

    # check if x can be put in cell [r][c]
    # if yes, put x in cell [r][c] and return True
    # if no, return False
    def set(self, r, c, x):
        if not self.check(r, c, x):
            return False

        self.board[r][c] = x
        return True

Test results

This code takes 45 seconds on my computer to solve the very hard puzzle above. Obviously, it didn’t make it through the Codewars’ hidden tests within the time limit.

Algorithm Optimizations

In the backtracking approach, we pick the first vacant cell and try every value at it. For each value, we then recursively pick the next vacant cell and try every value at the new cell. Although we do skip the values that will violates the existing values within the same row, column, and box, the number of branches that the program must try are still overwhelming.

The whole idea to optimize this algorithm is about reducing the branches that we have to test as much as possible.

Algorithm Optimization #1: Try to infer the values for the vacant cells from the existing values

The values can be inferred in two ways:

• Rule 1: If cell [r][c] can only be filled with one value d (because other values already exists in the same row, column, or box), we can fill d in [r][c].
• Rule 2: Because a value d must be filled exactly once in each unit (a unit means a row, a column, or a box), if all cells in a unit cannot be filled with d except for one cell, we can fill d in that cell.

Algorithm Optimization #2: Try to fail as early as possible

If we can detect that the current board status cannot be completed in any way, stop further processing on that case and return immediately.

We can detect this condition with the following checks:

• Rule 3: If cell [r][c] cannot be filled with any value (because all values already exists in the same row, column, or box), the board is unsolvable.
• Rule 4: If value d cannot be filled in any cell within a unit, the board is unsolvable.

Algorithm Optimization #3: Try to branch starting from the cell with fewest possible values

When no more cells can be inferred from the board, we have to go back to testing values at a vacant cell and recursively solve the board with the newly filled test value, similar to what we have been doing in the backtracking approach.

However, we can significantly reduce the number of cases to test by picking the cell with the minimum number of possible values, instead of picking the first vacant cell as usual. It’s like reducing the cases from 9*9*9*9*... to 2*3*2*2*....

Not only that this reduces the number of cases on each recursion, it also significantly reduces the depth of recursion, thanks to the inference process in Algorithm Optimization #1. In practice, this approach can reduces the number of recursive calls from hundreds of thousands calls to only several hundred calls.

Effectiveness

Believe it or not, using the above optimizations, most puzzles on Codewars’ tests, including hard ones, can be solved using only one or two recursive calls. By one recursive call, I mean we can inferred the whole board and don’t even need to test any value at any cell. In fact, except for the “very hard puzzle” mention at the beginning of this topic, all other puzzles can be solved with 6 recursive calls at most.

Implementation Optimizations

Although the algorithm optmizations seem promising, a bad implementation can ruin everything. Next, we are going to look at some implementation optimizations.

Implementation Optimization #1: Use a bit mask to mark allowed values at a cell

To efficiently check the possibilities at a cell, we can use a bit mask for each cell. The bit mask will be initialized as 0x1ff in hex or 111111111 in binary.

• If value d is still allowed to be filled in a cell without conflicting with any other cells in the same row, column, or box, the dth bit of the cell’s mask is turned on.
• If value d cannot be filled in a cell, the dth bit of the cell’s mask is turned off

More facts can be inferred from the above mask rule:

• The initial value of the cell’s mask contains 9 set bits, indicating that all 9 values are still allowed in that cell.
• If a mask has only 1 set bit at dth position, we can consider that d is filled in that cell (Rule 1).
• If a mask is 0, we can consider the puzzle status is unsolvable (Rule 3).
• Everytime a value d is set at cell [r][c], we also clear the dth bit in every cells in the same row, column, or box.

Some useful functions:
Check if a mask has only one bit (which means that cell has been set with a value):

def is_single_bit(m):
    return (m & (m - 1)) == 0

where m is the mask.

Check if a value d is allowed in cell [r][c]:

def is_allowed(m, d):
    return m & (1<<(d-1))

where m is the mask, d is the value we want to check.

Get the corresponding value from the mask, given we already know that the mask has only one set bit:

def get_value(m):
    return int(math.log2(m)) + 1

where m is the mask.

Count number of set bits in a mask:

def count_bits(m):
    count = 0
    while m:
        m &= (m - 1)
        count += 1
    return count

where m is the mask.

I have also tried using a precalculated bits_set table for fast lookup when counting number of set bits in a mask, however I cannot notice a performance increase in term of running time. The function goes as follow:

# precalculate the bits_set index table
bits_set = [0] * 256
for i in range(256):
    for d in range(1,10):
        if i & (1 << d-1):
            bits_set[i] += 1
def count_bits(m):
    return bits_set[m & 255] + bits_set[(m >> 8) & 255] \
        + bits_set[(m >> 16) & 255] + bits_set[(m >> 24) & 255]

Implementation Optimization #2: Use single dimension array instead of two-dimension array

At least, in Python. In my case, use single dimension array to store the mask instead of a two-dimension array speed the code up by two times.

Implementation Optimization #3: Set a value d to a cell by clearing all other bits instead of directly setting the dth bit

By doing this, everytime we clear an eth bit, we have a chance to count the number of remaining cells that still allow e in the related units (row, column, or box). If that number is 1, we can infer the place to fill e (Rule 2). If the number is 0, we can fail early (Rule 4).

Solution

Sample code

The following sample code is written in Python.

import copy
import math

def sudoku_solver(puzzle):
    # init a blank sudoku
    sudoku = Sudoku()
    
    # set the input board to our sudoku
    sudoku.setboard(puzzle)
    
    # if the input is invalid, raise an error
    if not sudoku.valid:
        raise ValueError

    # solve the sudoku, the results (if any) will be stored in sudoku.result_boards
    sudoku.solve()

    # if there are no solution, or there are more than 1 solution
    if len(sudoku.result_boards) != 1:
        raise ValueError

    # return the only solution
    return sudoku.result_boards[0]


class Sudoku:
    ### Notes:
    # cells will be indexed from 0 to 80


    ### init static constants:

    # list of the digits that will be filled in the sudoku
    digits = [1, 2, 3, 4, 5, 6, 7, 8, 9]

    # List of block/units that each cell stays in.
    # For example, cell[9] (row 1, col 0) has 3 units:
    # units[9][0] == [9, 10, 11, 12, 13, 14, 15, 16, 17] (all cells in the same row)
    # units[9][1] == [0,  9, 18, 27, 36, 45, 54, 63, 72] (all cells in the same column)
    # units[9][2] == [0,  1,  2,  9, 10, 11, 18, 19, 20] (all cells in the same box)
    units = []

    # list of all peers of each cell, which are all the unique cells in the same row, column and box.
    # For example, cell[9] (row 1, col 0) has the following peers:
    # peers[9] == [9, 10, 11, 12, 13, 14, 15, 16, 17, 0, 18, 27, 36, 45, 54, 63, 72, 0, 1, 2, 19, 20]
    peers = []

    # init units and peers table
    for i in range(81):
        units.append([])
        # add cells in same row
        units[i].append([])
        r = int(i / 9)
        for c in range(9):
            units[i][0].append(r * 9 + c)
        # add cells in same col
        units[i].append([])
        c = int(i % 9)
        for r in range(9):
            units[i][1].append(r * 9 + c)
        # add cells in same box
        units[i].append([])
        br = int(int(i / 9) / 3)
        cr = int(int(i % 9) / 3)
        for r in range(br * 3, br * 3 + 3):
            for c in range(cr * 3, cr * 3 + 3):
                units[i][2].append(r * 9 + c)
        # collect all neighbor cells of each cell
        peers.append([])
        for unit in units[i]:
            for cell in unit:
                if cell not in peers[i]:
                    peers[i].append(cell)
        peers[i].remove(i)

    # init a blank sudoku
    def __init__(self):
        self.mask = []
        self.valid = True
        self.solutions = []
        self.result_boards = []

    # set the input board to our sudoku
    def setboard(self, board):
        # the mask array of the 80 cells
        self.mask = []

        # whether the sudoku is valid
        self.valid = True

        # the list of solutions (if any) in mask format
        self.solutions = []

        # the list of solutions (if any) in human readable array format
        self.result_boards = []

        # check the input board dimensions
        if not self.validate(board):
            self.valid = False

        # init mask matrix with all cells set to 0x1ff, indicating that all 9 digits are still allowed in that cell
        self.mask = [0x1ff] * 81

        # set the input board to this sudoku matrix, and also update the peers' masks for each cell along the way
        for r in range(len(board)):
            for c in range(len(board[r])):
                if board[r][c]:
                    # if the digit cannot be set at a cell, we mark that the input board is invalid (unsolvable)
                    if not self.set(r*9+c, board[r][c]):
                        self.valid = False
                        return


    # validate board dimensions
    def validate(self, board):
        if len(board) != 9:
            return False
        for r in range(len(board)):
            if len(board[r]) != 9:
                return False
        return True

    # convert mask to human readable two-dimensional array
    def mask_to_board(self, mask):
        board = []
        for r in range(9):
            board.append([0] * 9)
        for r in range(9):
            for c in range(9):
                if self.is_single_bit(mask[r*9+c]):
                    for d in self.digits:
                        if mask[r*9+c] & (1 << (d-1)):
                            board[r][c] = d
        return board

    # clone the current status of the sudoku
    def clone(self):
        sudoku = Sudoku()
        sudoku.mask = copy.copy(self.mask)
        sudoku.valid = self.valid
        return sudoku

    # the main function to solve the sudoku
    def solve(self):
        # call the recursive function solve_helper to solve
        self.solve_helper()

        # convert the solution masks into human readable two-dimensional array and stored in result_boards
        for result in self.solutions:
            self.result_boards.append(self.mask_to_board(result))

    # recursive function to solve the board
    def solve_helper(self):
        # choose the vacant cell with the fewest possibilities
        cell = self.find_vacant_with_min_possibilities()

        # if all cells have been filled (no vacant cell), we have found a solution!
        if cell is None:
            self.add_solution(self.mask)
            return

        # try the remaining possible value in this cell
        for d in self.digits:
            # skip if d is not allowed in this cell
            if not (self.mask[cell] & (1<<(d-1))):
                continue

            # clone the sudoku status...
            sudoku = self.clone()

            # ... and try digit d in the cloned one to start searching for a solution
            # if setting d in this cell leads to an unsolvable sudoku: stop further processing
            if not sudoku.set(cell, d):
                continue

            # solve the cloned sudoku with the newly filled value
            sudoku.solve_helper()

            # if we found any solutions for the cloned sudoku:
            if len(sudoku.solutions) > 0:
                # collect those solutions for our current sudoku
                for solution in sudoku.solutions:
                    self.add_solution(solution)

            # the problem requires us raise error if there are more than one solution,
            # so we can skip further processing if 2 solutions have been found
            if len(self.solutions) >= 2:
                return


    # a mask is considered as set if there's only one bit turned on.
    # m has exactly one bit turned on if (m & (m - 1)) == 0
    def is_single_bit(self, m):
        return (m & (m - 1)) == 0

    # count number of turned on bits in a mask
    def count_bits(self, m):
        count = 0
        while m:
            m &= (m - 1)
            count += 1
        return count

    # add a solution to our collection, skip if that solution already exists
    def add_solution(self, mask):
        for result in self.solutions:
            if result == mask:
                return
        self.solutions.append(copy.deepcopy(mask))


    # find the vacant cell with fewest allowed value
    def find_vacant_with_min_possibilities(self):
        vacant_cnt = 0
        best_vacant_possibilities = 10
        best_vacant_i = 0
        for i in range(81):
            if best_vacant_possibilities == 2:
                break;
            if not self.is_single_bit(self.mask[i]):
                vacant_cnt += 1
                choices = self.count_bits(self.mask[i])

                if choices < best_vacant_possibilities:
                    best_vacant_possibilities = choices
                    best_vacant_i = i

        if (vacant_cnt == 0):
            # no more vacant cell:
            return None

        return best_vacant_i

    # set digit d at cell by clearing all the other bits (except for dth bit) in mask[cell]
    # return False if a contradiction is detected.
    # return True otherwise
    def set(self, cell, d):
        other_values = [ d2 for d2 in self.digits if d2 != d and self.mask[cell] & (1<<(d2-1)) ]
        for d2 in other_values:
            if not self.clear(cell, d2):
                return False
        return True

    # removing a digit d from being allowed at cell by clearing the dth bit
    def clear(self, cell, d):
        # if already cleared
        if not (self.mask[cell] & (1<<(d-1))):
            return True

        # turn off bit at d to mark d is no longer allowed at this cell
        self.mask[cell] &= ~(1<<(d-1))

        # Rule 1: If this cell has only one allowed value d2,
        # then make d2 the value at cell and eliminate d2 from the peers.
        if self.mask[cell] == 0:
            return False  # error: no value is allowed at this cell (Rule 3)
        elif self.is_single_bit(self.mask[cell]):
            val = int(math.log2(self.mask[cell])) + 1
            for cell2 in self.peers[cell]:
                if not self.clear(cell2, val):
                    return False

        ## Rule 2: If all cells in the unit cannot be filled with d except for one cell2,
        # we can fill d in that cell2.
        for u in self.units[cell]:
            dplaces = [cell2 for cell2 in u if self.mask[cell2] & (1<<(d-1))]
            if len(dplaces) == 0:
                return False  # error: no place for this value (Rule 4)
            elif len(dplaces) == 1:
                # d can only be in one place in unit; assign it there
                if not self.set(dplaces[0], d):
                    return False
        return True

Test the code

puzzle = \
    [[8, 0, 0, 0, 0, 0, 0, 0, 0],
     [0, 0, 3, 6, 0, 0, 0, 0, 0],
     [0, 7, 0, 0, 9, 0, 2, 0, 0],
     [0, 5, 0, 0, 0, 7, 0, 0, 0],
     [0, 0, 0, 0, 4, 5, 7, 0, 0],
     [0, 0, 0, 1, 0, 0, 0, 3, 0],
     [0, 0, 1, 0, 0, 0, 0, 6, 8],
     [0, 0, 8, 5, 0, 0, 0, 1, 0],
     [0, 9, 0, 0, 0, 0, 4, 0, 0]]
solution = \
    [[8, 1, 2, 7, 5, 3, 6, 4, 9],
     [9, 4, 3, 6, 8, 2, 1, 7, 5],
     [6, 7, 5, 4, 9, 1, 2, 8, 3],
     [1, 5, 4, 2, 3, 7, 8, 9, 6],
     [3, 6, 9, 8, 4, 5, 7, 2, 1],
     [2, 8, 7, 1, 6, 9, 5, 3, 4],
     [5, 2, 1, 9, 7, 4, 3, 6, 8],
     [4, 3, 8, 5, 2, 6, 9, 1, 7],
     [7, 9, 6, 3, 1, 8, 4, 5, 2]]
assert(sudoku_solver(puzzle) == solution)

Result

The new code solve the "very hard puzzle" above in about 0.1s. Compared to 40s in the backtracking approach, this is a 400 times increase in performance.

Try to submit the code on Codewars, and we pass all the tests in less then 300ms. Yay!

Conclusion

By applying some optimizations on both the algorithm and the implementation, we can see a significant increase in performance of our sudoku solver program.

Notice that the rules added to the algorithm are copied from the way that "human" uses to solve sudokus. Does that mean human brains have always been implemented with the most advanced algorithms?

There are still places for improvements, to solve even harder puzzles like the one below:

# 17 cells with thousands of solution
puzzle = \
    [[0, 0, 0, 0, 0, 6, 0, 0, 0],
     [0, 5, 9, 0, 0, 0, 0, 0, 8],
     [2, 0, 0, 0, 0, 8, 0, 0, 0],
     [0, 4, 5, 0, 0, 0, 0, 0, 0],
     [0, 0, 3, 0, 0, 0, 0, 0, 0],
     [0, 0, 6, 0, 0, 3, 0, 5, 4],
     [0, 0, 0, 3, 2, 5, 0, 0, 6],
     [0, 0, 0, 0, 0, 0, 0, 0, 0],
     [0, 0, 0, 0, 0, 0, 0, 0, 0]]

or this one:

# 16 cells with no solution
puzzle = \
    [[0, 0, 0, 0, 0, 5, 0, 8, 0],
     [0, 0, 0, 6, 0, 1, 0, 4, 3],
     [0, 0, 0, 0, 0, 0, 0, 0, 0],
     [0, 1, 0, 5, 0, 0, 0, 0, 0],
     [0, 0, 0, 1, 0, 6, 0, 0, 0],
     [3, 0, 0, 0, 0, 0, 0, 0, 5],
     [5, 3, 0, 0, 0, 0, 0, 6, 1],
     [0, 0, 0, 0, 0, 0, 0, 0, 4],
     [0, 0, 0, 0, 0, 0, 0, 0, 0]]

For these two puzzles, the algorithm in this topic still takes too long to complete. Hope we can find better algorithms to solve these puzzle faster in the future. On the other hand, solving sudoku in parallel (e.g. multithread or MapReduce) is also an interesting topic to discuss.

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

• Hidden Candidates
• Naked-pairs/triples/quads
• Intersection removal
• Backtracking
• Brute Force

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.