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.

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

satisfyis 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, ifsatisfyreceives 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

*conflict*s. And which are the cells with which a cell

*conflict*s? 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

*satisfy*ing 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**

## 1 comment:

Now all you need to do is to write a sudoku puzzle generator, and plug it into a closed loop with the solver; sit back and enjoy!

Post a Comment