How to write a simple sudoku solving algorithm (no backtracking) in 10 minutes

Tech Daily Feb 18, 2020

Ever since I was a child, I was intrigued by Sudokus (typical Asian kid I guess). At first, it looked like a crossword puzzle, but diving deeper into them, it looked a lot more intriguing.

A simple game of combinatorics in core, there was times, It would get so intense when I have nearly filled up the entire board and a few tiles are missing, and nothing works!

Approach for Solving Sudokus algorithmically

NOTE: All of the files discussed in this article can be found here: https://github.com/ronniebasak/sudoku-solver/blob/master/sudoku.py

Initially, I was a bit intimidated by the thought that I might write a working sudoku solving algorithm. I started with trying all the possibilities, and assuming a 71 blank sudoku, that comes out to be more than the number of stars in the observable universe. 56392087339601733413306017749077372989860250021295987473736382457209 to be exact.

After Googling a bit, I came across this video by computerphile explaining how to solve this using backtracking.

Python Sudoku Solver

With no offense to backtracking, I didn't like a brute force approach. We have clear rules defined, and instead of using the rules to create an algorithm, finding cases to narrow down our search, we use the rules to move on.

I wanted to write something different. Some great help came from wikipedia including the image.

Setting up a sudoku in Python and basic functions

In order to solve sudoku, you need to have a data structure for a sudoku. And a 2D Array is the one I went for.

puzzle = [
    [6,0,0,9,5,0,4,0,0],
    [0,2,0,0,0,0,0,0,8],
    [1,8,5,0,0,4,0,0,7],
    [9,0,0,7,2,0,0,0,0],
    [0,4,2,8,0,3,7,6,0],
    [0,0,0,0,4,9,0,0,3],
    [8,0,0,3,0,0,1,7,5],
    [3,0,0,0,0,0,0,2,0],
    [0,0,1,0,6,7,0,0,4]
]

An equivalent of this would be

puzzle = """
720090008
050380004
090000001
070806410
002004500
001730960
807000036
010463000
960000200
"""

def listify(v):
    sam = list(v)
    return map(int, sam)

puzzle = puzzle.strip()
puzzle = puzzle.split("\n")
puzzle = map(listify, puzzle)

Both of these represent a sudoku in the same 9x9 2D Array, the latter being a lot more readable with zeroes representing blanks.

Basic functions

With a puzzle set up for us we need basic utility/helper functions related to sudokus. Let's write them.

def get_num_at(x,y):
    return puzzle[y][x]

def get_col_at(x):
    return list(row[x] for row in puzzle)

def get_row_at(y):
    return puzzle[y]


def get_zone_boundary(v):
    zone_id = v/3
    return (zone_id*3, zone_id*3+2)

def get_zone_at(x,y):
    x0,x1 = get_zone_boundary(x)
    y0,y1 = get_zone_boundary(y)
    v = list(row[x0:x1+1] for  row in puzzle[y0:y1+1])
    return v[0]+v[1]+v[2]
    

def get_uniques(arr):
    to_return = list(set(arr))
    to_return.remove(0)
    return to_return

def get_blocked_nums(x,y):
    if get_num_at(x,y) == 0:
        row = get_row_at(y)
        col = get_col_at(x)
        zone = get_zone_at(x,y)

        consumed = list(set(row+col+zone))
        consumed.remove(0)
        return consumed
    else:
        return False

def get_possible_nums(x,y):
    all_possibles = set(range(1,10))
    _blocked = get_blocked_nums(x,y)
    if _blocked:
        blocked = set(_blocked)
        return list(all_possibles - blocked)
    else:
        return False
        

def print_board():
    for y in xrange(0,9):
        for x in xrange(0,9):
            if puzzle[y][x] == 0:
                print "_",
            else: 
                print puzzle[y][x],
            if x == 2 or x == 5:
                print "|",
        
        if y == 2 or y == 5:
            print "\n______________________",
        print "\n"

Enter possibility space

Sudoku possibilities

See, how we annotate each box with numbers that are possible for that place. From this we can see the below scenarios. We definitely need a data structure that holds this information.

A sample would look something like this, with keys being a tuple that contains the x,y coordinates and values being an array representing the possibilities.

Tuples are immutable in python, so they can be used as keys of dictionaries.
{
(7, 8): [8, 4, 5, 7],
(6, 6): [1],
(3, 0): [1, 5, 6],
....
....
....
(5, 2): [2, 5, 7],
(0, 2): [3, 4, 6],
(8, 4): [3, 7]
}
The data structure to represent possibility space

Now, to generate that structure, we would need the below function

def calculate_possibilities():
    possibility_space = {}
    for y in range(0,9):
        for x in range(0,9):
            poss = get_possible_nums(x,y)
            if poss:
                possibility_space[(x,y)] = poss
    
    return possibility_space

Certain cases in the possibility space

By initially looking at the possibility space, the easiest case stands out.

  • A Cell with only one possible number.
    If we come across such a cell, we put that number into the cell, and remove that number from all of the cells from it's row, column and zone.

    This makes some more cells, with only 1 possible number, this continues on till either
    1. the sudoku is solved
    2. we have no places where there is only 1 possible case.
  • A row, column or zone whose possibility space contain a unique value
    In that case, let's say three cells in a row contain the possibilities, [2,4,3], [2,4] and [1,2,3] we can see that 1 is unique to that row, and therefore, that cell must contain 1.

    Now, as we put 1 in the cell, again, 1 is removed from the row, column and zone.

We'll implement the second case later, let's implement the first case for now.

Let's implement the first case

For this, first, we'll need a function that removes a value from the cell and updates the possibility space.

def same_rows(c1, c2): # inputs two tuples, output boolean
    x0, _ = c1
    x1, _ = c2
    return x0 == x1

def same_cols(c1, c2): # inputs two tuples, output boolean
    _, y0 = c1
    _, y1 = c2
    return y0 == y1

def same_zone(c1, c2): # inputs two tuples, output boolean
    x0,y0 = c1
    x1,y1 = c2
    return x0/3 == x1/3 and y0/3==y1/3

def set_num(x,y, v, possibility_space=None):
    puzzle[y][x] = v
    if possibility_space:
        for cell in possibility_space:
            if possibility_space[cell] and cell != (x,y):
                # check if cell in same row
                if (same_rows(cell, (x,y)) or same_cols(cell, (x,y)) or same_zone(cell, (x,y))) and v in possibility_space[cell]:
                    possibility_space[cell].remove(v)

    return True

The solve() method algorithm

Everything thus far has set us up for this.

The solve() method must calculate the possibility space in the first run, but we should be able to pass a possibility space afterwards during recursion.

Steps to perform

  1. if possibility_space is empty, calculate possibility space
  2. initiate number of matches counter nMatches to zero
  3. iterate over all cells in the possibility space
    if a cell contains a single possibility
      set the value of that cell to that number
      remove that value from the row, column and zone
      delete the entry from possibility space
      increase number of matches counter by 1 nMatches += 1
  4. if possibility space is empty or number of matches is zero, print the board at it's current status, we can't continue anymore (with this approach)
  5. else call solve() recursively with current possibility_space
def solve(possibility_space=None, counter = 0):
    # calculate initial possibility space if a state is not passed
    if not possibility_space:
        possibility_space = calculate_possibilities()
        
    # go over the possibility space to find the following constraints
    # 1. is there only one possibility for a given number? then put it there and remove from possibility space
    # 2. if in a row, col or zone, a value occurs once, it goes there
    # possi(possibility_space)

    garbage = []
    nMatches = 0

    for cell in possibility_space:
        x,y = cell


        if possibility_space[cell] and len(possibility_space[cell])==1:
            set_num(x,y, possibility_space[cell][0], possibility_space)
            garbage+= [cell]
            nMatches += 1
        
    
    # collect garbage
    for g in garbage:
        del possibility_space[g]


    if len(possibility_space.keys()) > 0 and nMatches > 0:
        solve(possibility_space, counter+1)

    else:
        print_board()

solve()

Let's see the output:

7 2 4 | 6 9 1 | 3 5 8 

1 5 6 | 3 8 2 | 7 9 4 

3 9 8 | 5 4 7 | 6 2 1 
______________________

5 7 9 | 8 2 6 | 4 1 3 

6 3 2 | 9 1 4 | 5 8 7 

4 8 1 | 7 3 5 | 9 6 2 
______________________

8 4 7 | 2 5 9 | 1 3 6 

2 1 5 | 4 6 3 | 8 7 9 

9 6 3 | 1 7 8 | 2 4 5 

SOLVED!!!

Yes. I agree, this will not solve all possible sudokus out there. I am currently working on that and will update shortly!

Sohan Basak

Hi, I am Sohan. A software engineer by profession, I am really passionate about algorithms, AI/ML, Maths and Physics. Play the guitar as a hobby, the maths behind music is fascinating.