# Sudoku playing AI

An computer program that can play Sudoku at super human level is an interesting application of Artificial Intelligence. This may not a be a general example of an AI that can play games but it still forms an essential building block of game playing agents.

In this blog post I’ve build an AI that can solve any Sudoku puzzle easily with few powerful techniques that are used in almost any field of AI.

## Constraint Propagation

We begin up by setting the board and start up with a very intuitive approach or algorithm. The Sudoku board has total 81 boxes with 9 in each row and same for column. Now consider any box, say somewhere in between(you can chose anywhere), if the box is empty then what can we say about the entries of this box.

It will not contain any value that is present in its peer boxes. All the values in the same column or row or same 3x3 square of the marked box cannot be this chosen box’s value. *Now also, if the box has been assigned some value initially, then none of its peers can have same value.*

So we start with a basic algorithm saying that we go over all the boxes that do not contain any value and write a list of possible entries for each box based on its peers. We try to eliminate the possibilities of entries in every box and hence this step is also called elimination.

The next step for us is to look at each of the 3x3 square. So after previous step, for every square, the board has few single entry boxes, and few unsolved boxes with list of possible entries for each box. As we look at any single 3x3 square, we check if there is a single entry that can be filled in any one of the box that is not present in other boxes. The idea is that if there is only one box that will allow a particular entry, then that box must be allotted that entry. We may call this method as Only Choice strategy.

This is what exactly constraint propagation is all about. We used all the local constraints, in our case constraints on each square or box to significantly reduce our search space. As we solve every constraint we obtain new constraints on other parts of board which further help us to reduce the complexity of problem.

After using this strategy we may find that as we apply it, a stage is reached where further reduction of space is not possible. So we have to use another important methodology to go beyond this.

## Search

Search is a very powerful idea and strategy in solving problems using artificial intelligence. Starting from Game-Playing AI’s to optimization AI’s to efficiently planning routes, in each and every domain we can use this method to find solutions.

In our problem, consider any box and it’s possible entries. Simple strategy would be to take a single possible entry and explore it to solve the puzzle. Doing this for each and every box will be very expensive. But we can do better than this. We chose a box that has less number of possibilities to explore. We will chose an box with this idea in mind.

So we pick a box with minimum number of possible entries. We then try to solve the puzzle using each of these entries recursively.

A variety of method exist for implementing this strategy. For our problem we look at depth first search. I have an article named Classical Search Algorithms that describes a variety of search algorithms that are used in different problems. To read about more check this, and for an in-depth read look at this article.

DFS is a smart strategy to find a solution by traversing possibilities. We create a tree of possibilities and traverse it using DFS until we reach a solution for the puzzle.

I have implemented all of the strategies that I have discussed using python in the GitHub repo below. The code is for solving a special type of Sudoku called diagonal Sudoku puzzle.

I have implemented a new strategy Naked Twins using naked_twins() function. The naked twins strategy says that if you have two or more unallocated boxes in a unit and there are only two digits that can go in those two boxes, then those two digits can be eliminated from the possible assignments of all other boxes in the same unit.

So what happens is that this function identifies pairs of boxes with same two elements to get naked twins. Once we have the naked twins, we remove the corresponding entries from their peers.

In conclusion, reduce_puzzle calls eliminate, only_choice, and naked_twins methods to reduce the search space significantly. While search function is applied recursively to find out the solution to the puzzle.

*This blog post is related to first project of Udacity Nanodegree of Artificial Intelligence.*