Expecto Patronum - writing a sudoku solver (Part 2)

Qn: So how much have we progressed in writing a Sudoku solver?
Ans: 33.33 %

Lets finish the other two parts as well. I'll start with the easy one first, getting all valid choices for a cell in the sudoku map.

Getting valid choices for a cell in sudoku map
The sudoku is partially filled and I am analysing a cell (x, y). What I'd want is to get a list of all possible valid choices for (x, y). Simple! Eliminate all numbers (between 1-9) from row x, column y and the 3 X 3 square containing (x, y). Whatever remains, however improbable, are the valid choices, my friend. Here is the swash-buckling code:


def get_choices(s, x, y):
  '''Get possible choices for cell [x,y]
     Args:
       s: sudoku map
       x: row
       y: column
    Returns:
      list of possible choices
  '''
  l = 9
  all_choices = set(range(1, l+1))
  invalid_choices = set([])
  for i in range(1, l+1):
    r_ele = s[10*x + i]
    if r_ele:
      invalid_choices.add(r_ele)
    c_ele = s[10*i + y]
    if c_ele:
      invalid_choices.add(c_ele)

  #Use your own discretion to find out the top left cell of 3X3 square containing (x, y)
  sq_x, sq_y = find_3X3_top-left-cell(x, y)

  for i in range(3):
    for j in range(3):
      key = 10 * (sq_x + i) + (sq_y + j)
      if s[key]:
        invalid_choices.add(s[key])
    
  return list(all_choices - invalid_choices)  

And now comes the grand finale!!!

Main Algorithm

                                      "To iterate is human, to recurse divine"

And since we all want to write divine code, we would use recursion to solve this problem. How exactly? 

# Termination condition

If all cells in sudoku map are filled:

  if sudoku is solved:

     return the sudoku map

# Main recursion 

As long as there are unfilled cells in sudoku map:

1. Go to a unfilled cell 

2. Iterate over all possible valid values for that cell.

3. Fill that cell with each iterating valid value (thus modifying the sudoku map)

4. Recursively solve this new modified sudoku map.

5. If recursion returns because we found a solution (recursion will return sudoku map object):

      return the currently filled sudoku map as it is

    else (recursion returned None because no solution is found along the iterated value we filled):

      restore the sudoku map before recursion

      repeat from step 2 by moving on to the next value in the iteration

  Heuristic

   I also included a heuristic in the actual program for the order of visiting the unfilled cells. You could  visit them sequentially but turns out that it is not a good strategy. A simple heuristic is to start from the cell which has least number of possible valid choices. Using this simple heuristic, you cut your search space exponentially. (Think, think!)

All this algorithm (including the heuristic) translates to the following code:

def solve_sudoku(s):

  '''Solves sudoku

     Args: 

       s: sudoku map

    Returns:

      Solved sudoku map

  '''

  l = 9

  if all(val for val in s.values()): 

    if check_sudoku(s):

      return s

  min_choices = range(1, 10) 

  min_choice_key = None

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

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

      key = 10*i + j

      if s[key]:

        continue

      choices = get_choices(s, i, j)

      if len(min_choices) > len(choices):

        min_choices = choices

        min_choice_key = key

  for k in min_choices:

    s[min_choice_key] = k

    if solve_sudoku(s):

      return s

    s[min_choice_key] = 0

So this is the end, beautiful friend! 

Here was a simple, recursive sudoku solver. And it solved the world's hardest sudoku in around 3-4 sec. (http://www.usatoday.com/news/offbeat/2006-11-06-sudoku_x.htm)

There are more optimal implementations out there than the one I have given. But my aim was just to explain the process of writing a simple sudoku solver, and hopefully, you would have got a feeling of it now!

Acknowledgement:
I figured out the logic myself, except for the heuristic taken from http://norvig.com/sudoku.html which created a real big performance difference.

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.