Programming #10: AI Sudoku

Sudoku is one of those NP-Complete problems that brute force solutions have a problem with. Consider a board with a single blank space, we would have to work through 9 possibilities to find the right answer. For two blank spaces, we would work through 9 possibilities for the first space, and then for each of those possibilities, 9 for the second.

This simplifies to a time complexity of O(n^m) where n is the number of possibilities for each square (9 in normal Sudoku) and m is the number of blank spaces. A hard Sudoku problem with 50 blank spaces would take about 5.15 * 1047 computations, which would take longer than the age of the universe to solve with a decent computer.

This is where artificial intelligence (AI) comes into play. Think of AI less as a Skynet robot and more as a set of hacks to solve exponential problems like Sudoku. Code for this post can be found here.

Overview

Our goal is to build an intelligent agent that can solve every Sudoku puzzle. For those who don’t know, Sudoku consists of a 9×9 grid, and the objective is to fill the grid with digits in such a way that each row, each column, and each of the 9 principal 3×3 subsquares contains all of the digits from 1 to 9. The detailed rules can be found here. An example board:

https://camo.githubusercontent.com/fc52bbce19cd95b467315af113ad6c7e7aa9f87c/68747470733a2f2f64313768323774366835313561352e636c6f756466726f6e742e6e65742f746f706865722f323031372f4a616e756172792f35383638353163645f7375646f6b752d656173792f7375646f6b752d656173792e706e67

Getting started

Before doing anything else we will need to set some common terminology. First, we need to label our rows and columns.

  • The rows will be labeled by the letters A, B, C, D, E, F, G, H, I.
  • The columns will be labeled by the numbers 1, 2, 3, 4, 5, 6, 7, 8, 9.

For example, B1 in the above picture contains the value 9 (second row, first column). Now we need to label the main elements created by the rows and columns. Namely boxes, units, and peers.

  • The individual squares are called boxes. These boxes will have labels ‘A1’, ‘A2’, etc.
  • The complete rows, columns, and 3×3 squares will be called units. Each unit is a set of 9 boxes, and there are 27 units in total. If we are playing Diagonal Sudoku, there are 29 units (adding the two diagonals).
  • For a particular box (such as ‘A1’), its peers will be all other boxes that belong to a common unit (row, column, 3×3).

Encoding the board

We have some options when it comes to encoding the board, but for our purposes, we will imput puzzles as a string and convert them to a dictionary. For example, we can store the above-pictured puzzle as a string by reading from top to bottom and left to right and using a “.” as a placeholder for an empty box. For example:

..3.2.6..9..3.5..1..18.64....81.29..7.......8..67.82....26.95..8..2.3..9..5.1.3..

For the dictionary, the keys will be strings corresponding to the boxes and the values will either be the digit or the “.” placeholder. For example:

{'A1': '.'
 'A2': '.',
 'A3': '3',
 'A4': '.',
 'A5': '2',
 ...
 'I9': '.'}

Let’s code up the board state in Python. We want to first include our labels for boxes, units, and peers.

# Rows and column labels
rows = 'ABCDEFGHI'
cols = '123456789'

# Box labels (A1, A2 ...)
def cross(a, b):
    """ (str, str) -> list
    
    Helper function to combine rows and columns.
    Cross product of elements in A and elements in B.
    
    >>> cross('ab', '12')
    [a1, a2, b1, b2]
    """
    return [s+t for s in a for t in b]

boxes = cross(rows, cols)

# All row units
row_units = [cross(r, cols) for r in rows]

# All column units
column_units = [cross(rows, c) for c in cols]

# All 3x3 square units
square_units = [cross(rs, cs) for rs in ('ABC','DEF','GHI') for cs in ('123','456','789')]

# Create unitlist and convert to dictionary
unitlist = row_units + column_units + square_units
units = dict((s, [u for u in unitlist if s in u]) for s in boxes)

# Create peers dictionary
peers = dict((s, set(sum(units[s],[]))-set([s])) for s in boxes)

# Test our labels
def test():
    """
    A set of unit tests.
    """
    assert len(boxes) == 81
    assert len(unitlist) == 27
    assert all(len(units[s]) == 3 for s in boxes)
    assert all(len(peers[s]) == 20 for s in boxes)
    assert units['C2'] == [['C1', 'C2', 'C3', 'C4', 'C5', 'C6', 'C7', 'C8', 'C9'],
                           ['A2', 'B2', 'C2', 'D2', 'E2', 'F2', 'G2', 'H2', 'I2'],
                           ['A1', 'A2', 'A3', 'B1', 'B2', 'B3', 'C1', 'C2', 'C3']]
    assert peers['C2'] == set(['A2', 'B2', 'D2', 'E2', 'F2', 'G2', 'H2', 'I2',
                               'C1', 'C3', 'C4', 'C5', 'C6', 'C7', 'C8', 'C9',
                               'A1', 'A3', 'B1', 'B3'])
    print('All tests pass.')

test()

Then for every box, we want to have a dictionary that stores all the units and peers that it belongs too. We will add a display function to visualize the final board.

def display(values):
    """ (dict) -> None
    
    Display the sudoku in dictionary form as a 2-D grid.
    """
    width = 1 + max(len(values[s]) for s in boxes)
    line = '+'.join(['-'*(width*3)]*3)
    for r in rows:
        print(''.join(values[r+c].center(width)+('|' if c in '36' else '')
                      for c in cols))
        if r in 'CF': print(line)
            
    return

def grid_values(grid):
    """ (str) -> dict
    
    Convert grid string into {<box>: <value>} dict with '.' value for empties.
        - keys: Box labels, e.g. 'A1'
        - values: Value in corresponding box, e.g. '8', or '.' if it is empty.
    """
    assert len(grid) == 81, "Input grid must be a string of length 81 (9x9)"
    return dict(zip(boxes, grid))

We get a board that looks something like:

. . 3 |. 2 . |6 . . 
9 . . |3 . 5 |. . 1 
. . 1 |8 . 6 |4 . . 
------+------+------
. . 8 |1 . 2 |9 . . 
7 . . |. . . |. . 8 
. . 6 |7 . 8 |2 . . 
------+------+------
. . 2 |6 . 9 |5 . . 
8 . . |2 . 3 |. . 9 
. . 5 |. 1 . |3 . . 

Now with our board fully encoded, we can begin to solve the problem. How do we make an AI agent that will solve the puzzle?

Strategy 1: Elimination

Remember that AI can be thought of as finding useful hacks or shortcuts to a problem. It tries to simulate how a human would go about solving the puzzle. As humans, the first insight we might come upon is that we can eliminate possible values for a box by looking at its peers. If a box has a value assigned to it, then none of the peers of that box can have that value. Let’s code the board with this insight, instead of having a “.” on the board as a placeholder we will have a string with all the possible values the box can take, excluding the values of its peers.

This will require two steps:

  1. update grid_values() to return ‘123456789’ instead of ‘.’
  2. create eliminate() function that iterates over all the boxes in the puzzle that only have one value, and remove that value from every one of its peers.
def grid_values(grid):
    """ (str) -> dict
    
    Convert grid string into {<box>: <value>} dict with '123456789' value for empties.
        - keys: Box labels, e.g. 'A1'
        - values: Value in corresponding box, e.g. '8', or '123456789' if it is empty.
    """
    values = []
    all_digits = '123456789'
    
    # Iterate through characters in our grid string
    for c in grid:
        # Add '123456789' where placeholders are
        if c == '.':
            values.append(all_digits)
        # Add value if value present
        elif c in all_digits:
            values.append(c)
    
    # Check length and create dictionary
    assert len(values) == 81
    return dict(zip(boxes, values))

def eliminate(values):
    """ (dict) -> dict
    
    Eliminate values from peers of each box with a single value.

    Go through all the boxes, and whenever there is a box with a single value,
    eliminate this value from the set of values of all its peers.
    """
    # Find values that are already given
    solved_values = [box for box in values.keys() if len(values[box]) == 1]
    
    # Interate through boxes with solutions
    for box in solved_values:
        digit = values[box]
        # Remove value from peers
        for peer in peers[box]:
            values[peer] = values[peer].replace(digit,'')
            
    return values

Now our board looks like:

   45    4578    3   |   49     2     147  |   6     5789    57  
   9    24678    47  |   3      47     5   |   78    278     1   
   25    257     1   |   8      79     6   |   4    23579   2357 
---------------------+---------------------+---------------------
  345    345     8   |   1     3456    2   |   9    34567  34567 
   7    123459   49  |  459   34569    4   |   1    13456    8   
  1345  13459    6   |   7     3459    8   |   2     1345   345  
---------------------+---------------------+---------------------
  134    1347    2   |   6     478     9   |   5     1478    47  
   8     1467    47  |   2     457     3   |   17    1467    9   
   46    4679    5   |   4      1      47  |   3    24678   2467 

We can see all the possible values that each empty box can take, considering the restraint that its peers impose. We are getting closer to a solution.

Strategy 2: Only Choice

As humans, our next insight will probably be that every unit must contain exactly one occurrence of every number. Recall a unit is just a column, or row, or 3×3 box. For example, looking at the top row in our example after elimination, we see that there is only one possible location where a 1 can fit (A6). This is because no other box in the row has the option of being a 1, it’s our only choice.

In other words, if there is only one box in a unit which would allow a certain value, then that box must be assigned that value. To code this up we will take the puzzle as a dictionary, go through all the units, and if there is a unit with a value that only fits in one possible box, assign that value to that box.

def only_choice(values):
    """ (dict) -> dict
    
    Finalize all values that are the only choice for a unit.

    Go through all the units, and whenever there is a unit with a value
    that only fits in one box, assign the value to this box.
    """
    # Interate through units
    for unit in unitlist:
        for digit in '123456789':
            # Create a list of boxes where a digit appears
            dplaces = [box for box in unit if digit in values[box]]
            # If digit only appears in one box, replace value with digit
            if len(dplaces) == 1:
                values[dplaces[0]] = digit
                
    return values

After implementing this strategy, our board looks like:

  45    8     3   |  9     2     1   |  6    5789   57  
  9     6     47  |  3     4     5   |  8    278    1   
  2    257    1   |  8     7     6   |  4   23579  2357 
------------------+------------------+------------------
 345   345    8   |  1    3456   2   |  9   34567 34567 
  7     2     9   |  5   34569   4   |  1   13456   8   
 1345 13459   6   |  7    3459   8   |  2    1345  345  
------------------+------------------+------------------
 134   1347   2   |  6     8     9   |  5    1478   47  
  8    1467   47  |  2     5     3   |  17    6     9   
  6     9     5   |  4     1     7   |  3     8     2   

Constraint Propagation

So far we have just been eliminating possibilities based on the rules of Sudoku. There is a term for this – Constraint Propagation. Constraint Propagation is all about using local constraints in a space (in the case of Sudoku, the constraints of each square) to dramatically reduce the search space. As we enforce each constraint, we see how it introduces new constraints for other parts of the board that can help us further reduce the number of possibilities.

Now that we reduced our search space by using elimination() and only_choice(), we can use both functions again on our results in order to find new things to eliminate and new solutions. Let’s code this up in a function called reduce_puzzle(). We will need to make sure the function stops when the puzzle is solved and also stops when the strategies fail to make any progress.

def reduce_puzzle(values):
    """ (dict) -> dict
    
    Iterate eliminate() and only_choice(). If at some point, there is a box with no available values, return False.
    If the sudoku is solved, return the sudoku.
    If after an iteration of both functions, the sudoku remains the same, return the sudoku.
    """
    # Initialize stalled
    stalled = False
    
    # Check if stalled, if not proceed
    while not stalled:
        # Check how many boxes have a determined value
        solved_values_before = len([box for box in values.keys() if len(values[box]) == 1])
        # Use the Eliminate Strategy
        values = eliminate(values)
        # Use the Only Choice Strategy
        values = only_choice(values)
        # Check how many boxes have a determined value, to compare
        solved_values_after = len([box for box in values.keys() if len(values[box]) == 1])
        # If no new values were added, stop the loop.
        stalled = solved_values_before == solved_values_after
        # Sanity check, return False if there is a box with zero available values:
        if len([box for box in values.keys() if len(values[box]) == 0]):
            return False
        
    return values

After reducing the puzzle, we finally have the solution:

4 8 3 |9 2 1 |6 5 7 
9 6 7 |3 4 5 |8 2 1 
2 5 1 |8 7 6 |4 9 3 
------+------+------
5 4 8 |1 3 2 |9 7 6 
7 2 9 |5 6 4 |1 3 8 
1 3 6 |7 9 8 |2 4 5 
------+------+------
3 7 2 |6 8 9 |5 1 4 
8 1 4 |2 5 3 |7 6 9 
6 9 5 |4 1 7 |3 8 2 

But what happens if our two strategies aren’t enough? Consider the harder problem of:

'4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......'

Running reduce_puzzle() on this grid would not reach a solution. We will need a new strategy.

Strategy 3: Search

Along with Constraint propagation, another fundamental AI technique is simple search. If we don’t know the answer, try plugging in values and see what happens. However, this can be costly if not implemented with some tricks.

Here we’ll apply search by starting with the box that has the fewest values. For example, if there is a box with only two possible values, say 1 and 6, we will just fill the box in with 1 and try to solve the puzzle from there, if we can’t, then we will try with 6 instead.

We can create a search() function that starts at the box with the fewest possibilities and works through them.

def search(values):
    """ (dict) -> dict
    
    Using depth-first search and propagation, try all possible values.
    """
    # First, reduce the puzzle using the previous function
    values = reduce_puzzle(values)
    
    # Check if failed
    if values is False:
        return False ## Failed earlier
    
    # Check if solved
    if all(len(values[s]) == 1 for s in boxes): 
        return values ## Solved!
    
    # Choose one of the unfilled squares with the fewest possibilities
    n,s = min((len(values[s]), s) for s in boxes if len(values[s]) > 1)
    
    # Now use recurrence to solve each one of the resulting sudokus
    for value in values[s]:
        new_sudoku = values.copy()
        new_sudoku[s] = value
        attempt = search(new_sudoku)
        if attempt:
            return attempt

We get our answer:

10 loops, best of 3: 65 ms per loop
4 1 7 |3 6 9 |8 2 5 
6 3 2 |1 5 8 |9 4 7 
9 5 8 |7 2 4 |3 1 6 
------+------+------
8 2 5 |4 3 7 |1 6 9 
7 9 1 |5 8 6 |4 3 2 
3 4 6 |9 1 2 |7 5 8 
------+------+------
2 8 9 |6 4 3 |5 7 1 
5 7 3 |2 9 1 |6 8 4 
1 6 4 |8 7 5 |2 9 3 

We now have an AI agent that can solve every Sudoku puzzle, but can we do better? Well, we can add more rules to our constraint propagation before we get to the searching step. Searching is the most costly part of this solution, so the more we can reduce the puzzle before that, the better.

Strategy 4: Naked Twins

The naked twins strategy is one such constraint in Sudoku. If we identify a pair of boxes belonging to the same set of peers that have the same 2 numbers as possibilities, we can eliminate those two numbers from all the boxes that have these two boxes as peers because:

  • No other digit can appear in those 2 boxes.
  • The 2 digits cannot appear in the other boxes of the unit.

For an example, see here. Coding this up:

assignments = []

def assign_value(values, box, value):
    """ (dict, str, int) -> dict
    
    Helper function. Assigns a value to a given box. If it updates the board record it.
    """
    # Don't waste memory appending actions that don't actually change any values
    if values[box] == value:
        return values

    values[box] = value
    if len(value) == 1:
        assignments.append(values.copy())
    return values

def naked_twins(values):
    """ (dict) -> dict
    
    Eliminate values using the naked twins strategy.
    """
    for u in unitlist:
        # Create lookup table for values in unit
        l_val = [values[s] for s in u]
        # Track the counts of duplicate values
        l_val_c = [l_val.count(s) for s in l_val]
        # Find the naked twins
        naked_twins = [u[i] for i in range(9) if l_val_c[i] == 2 and len(l_val[i]) == 2]
        # Find the non twins
        non_twins = set(u) - set(naked_twins)
        # Eliminate the naked twins as possibilities for their peers
        for box in naked_twins:
            for digit in values[box]:
                for n in non_twins:
                    if len(values[n]) > 1:
                        assign_value(values, n, values[n].replace(digit,''))

    return values

Then add this to our reduce_puzzle() function:

def reduce_puzzle(values):
    """ (dict) -> dict
    
    Iterate eliminate() and only_choice(). If at some point, there is a box with no available values, return False.
    If the sudoku is solved, return the sudoku.
    If after an iteration of both functions, the sudoku remains the same, return the sudoku.
    """
    # Initialize stalled
    stalled = False
    
    # Check if stalled, if not proceed
    while not stalled:
        # Check how many boxes have a determined value
        solved_values_before = len([box for box in values.keys() if len(values[box]) == 1])
        # Use the Eliminate Strategy
        values = eliminate(values)
        # Use the Only Choice Strategy
        values = only_choice(values)
        # Use the Naked Twins Strategy
        values = naked_twins(values)
        # Check how many boxes have a determined value, to compare
        solved_values_after = len([box for box in values.keys() if len(values[box]) == 1])
        # If no new values were added, stop the loop.
        stalled = solved_values_before == solved_values_after
        # Sanity check, return False if there is a box with zero available values:
        if len([box for box in values.keys() if len(values[box]) == 0]):
            return False
        
    return values

Finally, let’s create a one stop solve() function to take in a string and solve using everything we have done so far.

def solve(grid):
    """ (str) -> None
    
    Find the solution to a Sudoku grid.
    """
    values = grid_values(grid)
    values = search(values)
    #display(values)

    return

We get our solution:

10 loops, best of 3: 25.3 ms per loop
4 1 7 |3 6 9 |8 2 5 
6 3 2 |1 5 8 |9 4 7 
9 5 8 |7 2 4 |3 1 6 
------+------+------
8 2 5 |4 3 7 |1 6 9 
7 9 1 |5 8 6 |4 3 2 
3 4 6 |9 1 2 |7 5 8 
------+------+------
2 8 9 |6 4 3 |5 7 1 
5 7 3 |2 9 1 |6 8 4 
1 6 4 |8 7 5 |2 9 3 

We managed to cut our search time in half from 65 ms per loop to 25.3 ms per loop. We can probably do even better by adding more heuristics.

Conclusion

This post examined how using simple rules or heuristics, an exponential problem can be solved in almost no time at all. By combining constraint propagation and search, we were able to solve one such exponential problem, Sudoku.

References:
http://norvig.com/sudoku.html
https://www.udacity.com/ai

Advertisements

Author: David Shahrestani

"I have the strength of a bear, that has the strength of TWO bears."

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s