Expecto Patronum - writing a sudoku solver (Part 1)

Writing a sudoku solver is not a dark art. It appears so. And appearances can be deceptive.

So this post is about how to write a sudoku solver. And I will show you how to write it in Python - though choice of programming language really does not matter.

This post is about writing a sudoku solver for a 9 X 9 sudoku puzzle. At this point, I assume you all know what a sudoku puzzle is and what are its rules - if you do not, stop reading and go back to sleep (sigh! yawn!)

Input
First of all, how do we represent the input. The answer comes naturally - read from a file. Cool! And what would be the file format to represent a 9 X 9 sudoku puzzle? Thats your choice. Not being too much fancy in file format, I will keep it simple: there will be 9 lines in the file, with each line having 9 numbers, from  0 - 9 , separated by single space. An example for the content of the input file is:

#############

0 0 3 0 7 5 0 0 0
0 0 0 0 2 0 0 8 6
9 0 2 0 0 1 0 0 3
0 4 0 1 8 0 0 0 0
0 0 7 0 0 0 0 0 0
2 0 0 0 0 0 6 0 0
0 0 0 7 0 0 3 0 1
0 0 4 0 0 0 0 0 7
0 3 0 4 5 0 2 0 0

#############

**0 represents the unfilled entries in the sudoku which we have to find out.

Representing Sudoku in the program

2D Array? Grid? Well, well, well, hold your horses. I am writing this in Python and Python gives me list as a awesome data structure. Since the natural way to represent the sudoku puzzle in the program would be a 2D sort of matrix, I will have to use a collection of lists. Now wait! What I want is to be able to glide down any row or column or a 3 X 3 square and with a collection of lists, its a bit tedious. So I am going to use Python's hero of all times - a dictionary to represent the sudoku. 

What about the keys in the dictionary? Easy one mate! Lets churn a key out of (row, column) for each sudoku cell. Well, you can make any key, it does not matter as long as you could manufacture 81 different keys with the same hash function. (It might vary in efficiency but that would not be a bottleneck unless the extent of one's stupidity is proportional to the size of the universe)

I would use the first function that came to my mind:

                                                   f(row, column) -> 10 * row + column

Now using this hash function, just read from the file and construct this sudoku map (sudoku hash, sudoku dictionary - anything is fine as long as you understand it to be the same thing I am talking about).

Checking if sudoku is solved

This post is getting too long and I'd like to continue onto another. But before that, lets add one real function to our code which checks whether a currently filled sudoku map has solved the sudoku or not. The algorithm is pretty easy - check all rows and each row should have all numbers from 1 - 9 (no repetitions), and do this for all columns too. So here is the first real function code in this blog:

def check_sudoku(s):

  '''Checks if sudoku is solved

     Args: 

       s: sudoku map

    Returns:

      True if sudoku is solved

  '''

  l = 9

  # Check each row and column

  for i in range(1, l+1):

    r = []

    c = []

    for j in range(1, l+1):

      r_ele = s[10*i + j]

      c_ele = s[10*j + i]

      if r_ele in r or c_ele in c:

        return False

      r.append(r_ele)

      c.append(c_ele)

  return True

I got really bored now(Yaaaawn!). So more on this in part 2.