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

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.

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

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.

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

- if
`possibility_space`

is empty, calculate possibility space - initiate number of matches counter
`nMatches`

to zero - 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`

- 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)
- 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!