Algorithm Homework Weekly - 5

Write a program to solve a Sudoku puzzle by filling the empty cells.

Empty cells are indicated by the character ‘.’.

You may assume that there will be only one unique solution.

My accepted code can be found here

Only one problem for this week, solving sudoku. My accepted code beats 87% on leetcode, but the concept of it is, errrrr, not very complicated. But it’s quite cheerful to achieve that.

Basically we have two phases. In the preprocessing phase we read the initial sudoku and construct the relation between cells and initialize candidate numbers in every empty cells. And in the searching phase, we do depth first search on empty cell and try all possible candidate until we fill the whole board.

The problem of solving sudoku is usually how to make updating candidate state and backtracking efficient. And here’s how I did.

There’re two data structures initialized in the preprocessing phase and maintained in searching phase.The related set and disabled set.

related is a matrix that contains a set of coordinates, (a, b) in related[x][y] means board[x][y] and board[a][b] can’t be the same number.

disabled is a matrix that contains the set of “disabled” number in an empty cell. n in disabled[x][y] means board[x][y] currently cannot be filled with n.

So maintaining the data structure is quite simple. When filling (x, y) with n, we look at all coordinates (a, b) that in related[x][y]

delete (x, y) in related[a][b] since now (x, y) is no longer empty
if n not in disabled[a][b], store (a, b) into backtracking memory and add n to diabled[a][b].

When backtracking, we do following things

for all (a, b) in related[x][y] (we didn’t clear related[x][y] previously), add (x, y) back to related[a][b]
delete n in disable[a][b]

And we retore the state to the time when we didn’t fill n into (x, y).

The second part is searching, where I didn’t do much tricks. I simply find the coordinate with the most amount of disabled number, if all numbers of the cell are disabled, this branch of searching fails.

So the overall structure of algorithm is

SolveSudoku(board):
    Preprocess()
    Search()

Preprocess:
    let related = Set[9][9], disabled[9][9]
    for each coordinate (x, y)
        related[x][y] = coordinates that shouldn't have same number with (x, y)
    for each non-empty coordinate (x, y)
        for all (a, b) in related (x, y)
            delete (x, y) from related[a][b]
            add board[x][y] to disabled[a][b]
        clear related[x][y]
        add 1 - 9 to diabled[x][y]

Search:
    Find (x, y) where size(disabled[x][y]) is the max among all coordinates
    if no such (x, y) then return true
    else if size(disabled[x][y]) == 9 then return false
    else for all n not in disabled[x][y]:
        if Try(x, y, n) return true
    return false

Try(x, y, n):
    let backtrack = []
    for all (a, b) in related[x][y]:
        delete (x, y) from related[a][b]
        if n not in disabled[a][b]
            add n to disable[a][b]
            add (a, b) to backtrack

    board[x][y] = n

    if Search() then return true

    board[x][y] = empty

    for all (a, b) in related[x][y]:
        add (x, y) to related[a][b]
    for all (a, b) in backtrack:
        delete n from disabled[a][b]

    return false

Last

I didn’t ever implement a sudoku solver before, and I came across this problem today and say “hey let’s do this”. I didn’t expect I did so well on the problem and it did raise my confidence somehow :P

Happy Chinese Holiday.

Last

Share on: