# AI Nano degree update: Project One

First project required to write an AI agent capable of solving a Sudoku puzzle. The key goals of the exercise: familiarize students with concepts of constraint propagation and search for solving problems.

I would summarize constraint propagation as follows. In abstract, when you have a function that needs to pick a solution given multiple of choices, it can narrow down the answers by coming up with strategies that eliminate the subset of given solutions until a single solution remains or the number of potential solutions is smaller than the input solution space.

In Sudoku project, the three strategies for eliminating the solutions employed were as follows:

• straight up elimination – find boxes that are solved, and then remove that box’s value from its peers (rows, cols, squares)

• only-choice – given a box with multiple possible digits, for each of those digits, see if it is not present in other unit’s of that box thus making that number the only viable choice for the box

• Naked twins – sometimes you have units that have two boxes with the same possible solutions, so that means those two squares will have either one of those digits. Thus those digits can be eliminated from other units of the box. There are variations of this called naked triplets, and so on. Twins seemed to be the most effective.

Now you can imagine that one can run through the solution elimination sequence in a loop, with each pass applying all the elimination techniques. You stop looping if none of the techniques are reducing the solution space further. You are stalled.

What now? Well, brute force search. Pick un unsolved box, and iterate through its solutions, in each pass applying the constraint elimination sequence until you either solve the problem or you stall. If you stall – the initially picked solution is not a good choice, move on to the next until solution is found.

The project was a very fun exercise. I never was much into Sudoku before so at the very least it gave me an excuse to try the puzzles out. It quickly became a fun exercise of finding patterns. And once you mix in writing Python code to solve the problem automatically, it was nothing but a delight.

Here is a screenshot of AI agent in action: