An Automated Sudoku Player

I never played Sudoku. And now, it's even more unlikely that I will ever play it again.

I built a cute little program, all of it probably less than 40 lines, that will solve any damn Sudoku puzzle for me (I think), however hard, while I pay attention to my morning tea and other less brain wracking articles in the newspaper.

The program isn't a trivial piece though. Let me also confess that the algorithm isn't mine. I saw it first in a Python course I sat through which Dr. Vinay was teaching. After teasing the students in his characteristic style for a couple of hours, he popped out his implementation of it. A 16 line Python code!

The one I present here is pretty much the same algorithm, albeit implemented by a mortal. :)

The algorithm...hm. Well, it's a brute force one, in the same way as the solution to the eight queen puzzle that I presented here. However, it's OK. Sudoku puzzles don't grow larger than 9 by 9. So, a decent implementation comes back with a solution (if it exists) within a second or so on an average. One way to look at it is to treat the puzzle instance as an array of 81 numbers. And you could use that decision cleverly to crunch your program into an ever smaller number of lines). But I am somewhat old fashioned. I have no taste for anything size zero. I decided to represent it in a way similar to how it appears to the eyes: a 9 by 9 matrix. That added some flab to my program. But I like it that way!

Again, a small bit of notation will help understand the algorithm.

satisfy(x, Env) =
    if permitted(x, Env) = {} then []
    else
        if x = end then let val be any value from permitted(x, Env) in
             Env U Env[x] = val

        else
            if there exists val in permitted(x, Env) such that
                satisfy(x + 1, Env U Env[x] = val) != [] then
                    satisfy(x + 1, Env U Env[x] = val)

            else  []

I know, I know. It hasn't remained that simple, this notation. But the attempt underneath to present the same thing in plain English will show you why people (like me) unwillingly resort to mathematical notations (I would agree with you that people who are eager to resort to mathematical notations for no good reason should be sent to the firing squad).

satisfy is recursive. It returns a partially filled sudoku grid (on success) or an empty grid (on failure). For any cell in the grid, if the grid is the last cell in the grid, then, if the set of permitted values for this cell under the given sudoku grid is empty, then it returns an empty grid. Otherwise, it picks any value from that permitted list, sticks that into the cell of the sudoku grid and returns that. In case the cell isn't the last one in the grid, if satisfy receives back a non-empty grid from the subsequent call, it returns the same. Else if it has any untried permitted value left, it uses the same to call satisfy on the next grid cell. If it gets back an empty grid for all permitted values, it returns an empty grid itself, indicating failure in finding a satisfying assignment for the sudoku grid that was passed to it.

Makes sense? No? To me neither! Let me not therefore belabour the point that math is sometimes not to be avoided for your own benefit.

One more point. Important one. The above mathematical expression is also a fairly loaded (programmers use the term generic) specification of a depth first backtracking state space search algorithm. The above structure will pop up in various places if your programming assignments ever take you in the neighbourhood of trees (as in, the data-structures). For example, our eight-queen solver algorithm could also be written very much in the same manner. Only the bells and whistles would be different. More on this sometime later.

OK. Now take a look back at the expression. Let's try to understand it bit by bit.
satisfy(x, Env) =
Here, we are defining a function satisfy that takes two arguments: x, the grid cell that we are considering currently and Env, which stands for the environment. Environment is again a jazzy word for a set of bindings to things which could be bound. In our case, all the cells in our sudoku grid can be bound to certain values (in the range [1..9]). Env contains one such set of valuations. In it some of the cells have been bound to some values, while some other mayn't yet have been bound to any value. The '=' in the end is the wall between the RHS and LHS. Note that the expression above is actually an equation. So, it's supposed to have an LHS and an RHS separated by an '='. Just to make things further clear, if you have been a lot into programming with C-like languages, the '=' isn't an assignment; it's an equality. Note that the function above is a declarative statement, not an imperative one. Therefore, you don't assign anything to anything; you just declare the condition of equality.

if permitted(x, Env) = {} then []

The above means that the set of permitted values for the cell x with the given (partially filled) sudoku grid is empty (i.e. we have no permitted values), then satisfy evaluates to an empty list. This means that with the given inputs this call to the satisfy has failed to come up with satisfying valuations to the empty cells of the sudoku grid.

But what is a permitted set? The universal set of numbers that can go into a cell is [1..9]. A cell can't have the numbers in this set which have already been taken by the cells with which it conflicts. And which are the cells with which a cell conflicts? The cells in the same row, and those in the same column and those in the same subgrid or region.

conflict(x, y) =
    row(x) = row(y) or column(x) = column(y) or region(x) = region(y)

unpermitted = set of values in all y such that conflict(x, y)
permitted = [1..9] \ unpermitted

One more question. How to determine the region of a cell? Here's how:
region(x) = (row(x) / 3, column(x) / 3)

That is, it's a pair obtained by dividing both the row and column of x by 3. And remember, this is an integer divide. So, the value computed as the quotient is also an integer, which is the floor of the actual quotient (possibly a rational number). I leave it up to you to convince yourself that this will give you the region indeed.

Phew! So much for a couple of lines! Are we going to have read a whole book to understand the complete expression? No. I think, we have dealt with most of the complicated stuff by now. Hereon, things ought to be straightforward.

    else
        if x = end then let val be any value from permitted(x, Env) in
             Env U Env[x] = val


So, we have dealt with the case when there are no permitted values. That corresponds to a failure, and the expression evaluates to an empty set {}. Now, if there are some permitted values, i.e. permitted is not {}, then we check if we are dealing with the last cell in the grid (x = end). If yes, then we have found a solution, and we return the grid as we received it. Else, we continue our journey to the next element in the grid:

        else
            if there exists val in permitted(x, Env) such that
                satisfy(x + 1, Env U Env[x] = val) != [] then
                    satisfy(x + 1, Env U Env[x] = val)

            else  []

which says that for a given value val in the permitted set, we must get a non-empty set from the call to satisfy on the next cell. If we get an empty set, this val is dud and we have to consider another one. If we aren't left with any before having found success in satisfying the next cell, the val being considered in the previous cell is a dud, and we need to tell it to the caller of this satisfy. How? Of course, by returning an empty set.

Also note that in computing the permitted set, we do another clever thing. If it turns out to be an empty set, we have no reason left to proceed further in the same direction, and we backtrack. This saves us from exploring potentially large portions of the state space where searching for a solution would be futile. This clever trick is called pruning. And the family of algorithms which use this technique are called branch and bound algorithms.

Understood? No! Well, I can't make any easier than this. Blame it on my bad writing skills. But as of now, if you haven't yet made it through the above explanation, and you are still keen to, the only way I can think of is to go through it again. Stare at it for a while. And you'll soon see light. It's not very difficult, I can tell you that!

And if understanding the above isn't your cup of tea, well, all is not lost. Here, below, I give out the whole code.

#!/usr/bin/python
def conflict((r1, c1), (r2, c2)):
 if(r1 == r2):         return True
 if(c1 == c2):         return True
 if(r1 / 3 == r2 / 3 and c1 / 3 == c2 / 3 and (not (r1 == r2 and c1 == c2))): return True
 return False

def setminus(lst1, lst2):
 return [x for x in lst1 if x not in lst2]

def nextcell((i, j)):
 if(j == 8):
  if(i == 8): return (0, 0)
  return (i + 1, 0)
 return (i, j + 1)

def solve(input):
 empty = [[0] * 9] * 9
 def satisfy(pos, sudoku):
  def getAllowedValues():
   conflicts = set([ (r, c) for r in range(9) for c in range(9) if((r, c) != pos and conflict(pos, (r, c)))])
   notallowed = set([sudoku[r][c] for (r, c) in conflicts if sudoku[r][c] != 0])
   return setminus(range(1, 10), notallowed)
  if(sudoku[pos[0]][pos[1]] != 0):
   if(pos != (8, 8)): return satisfy(nextcell(pos), sudoku)
   else:   return sudoku

  values = getAllowedValues()
  new = [r[:] for r in sudoku]
  for value in values:
   new[pos[0]][pos[1]] = value
   filled = satisfy(nextcell(pos), new)
   if(filled != empty): return filled
  return empty
 return satisfy((1, 0), input)

def printSudoku(sudoku):
 print '-------------------------'
 for i in range(9):
  for j in range(9):
   if(j == 8): print sudoku[i][j]
   elif(j%3 == 2): print str(sudoku[i][j]) + '|',
   else:  print str(sudoku[i][j]) + ' ',
  if(i%3 == 2):
   print '-------------------------'
 print

The downloadable algorithm is here:
sudoku.py

The driver is here:
sudoku driver

An couple of examples:
example input 1
example input 2

Just store the above files someplace (the same place) in your machine and run as follows:
sudoku_driver input_file