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:
To generalize the idea: when you have a function which has a set of possible solutions to choose from – go ahead and think through how you could constrain possible solutions to reduce the search space. Then brute force search through each until the answer is discovered.
Besides a great warm up into search, the first project also gave me a great intro into Anaconda, “Leading Open Data Science Platform Powered by Python.” Think of it as a Python environment that is loaded with data science libraries and tools. If that is not enough, it can “containerize” your Python environments that are entirely isolated and across machines/platforms. You can setup a Python 2 environment and Python 3 environments, load it on the same machine, and neither will impact each other. And again, not to mention that it comes pre-installed with a variety of data/ml related packages.
On to the second project, which goes much deeper into general AI ideas around search and advanced game-playing techniques. I am done with that project two and should have a write up for it shortly.