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 * 10^{47} 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:

### 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:

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:

- update grid_values() to return ‘123456789’ instead of ‘.’
- 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:

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:

### 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:

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:

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:

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