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.