Model-based machine learning and the probabilistic programming paradigm is coming to the .NET world. If, by any chance, you are unfamiliar with these topics, please feel free to check the links provided above 🙂
Given this happy situation, I figured that it would be nice to build a probabilistic sudoku solver / generator using the model-based machine learning principles and Infer.NET.
I’ve done it! but trust me, it was a trip worth sharing. I have decided to share this journey with everybody in a series of articles / talks / gatherings.
First, does it make sense to have a probabilistic approach for the sudoku puzzle ? Well, yes it does. It is an NP-complete – proven back in 2003 -problem, so it makes sense to optimize the solution as much as possible.
Second, building the probabilistic model for the generic sudoku puzzle turned out to be a significant challenge. This small article is dedicated to just a fraction of the “probabilistic model for the sudoku puzzke” problem, namely the reason for choosing a Probabilistical Graphical Model – a probabilistical model based on graphs. I hope I will be able to write an entire series of articles that will take you through the entire journey I took. Doing this in just one article is impossible, and, let me tell you, extenuating to read and understand. So let’s begin.
Imagine a simple 4×4 sudoku puzzle
Trying to drill down the components of a sudoku puzzle, we can come up with the following:
- The Solution elements. The elements of the solution (numbers inside). Let’s call such an element Sn, In a row-scan order, for the sample above: (1,2,4,3,4,3,1,2,2,1,3,4,3,4,2,1)
- The constraints. You know the rules of sudoku, right? Then, constraints are the groups in which solution elements live. For the 4×4 sudoku puzzle, there are 12 of them. Please see the Fig 2. bellow.
The first constraint (C1) is the first row. You get the idea. (C9) is the first subgrid constraint.
Now the relationship between the constraint and solution nodes (Cm and Sn) can be a bipartite graph as follows
Again, you get the idea. The information held by the bipartite graph is: what constraint applies to what set of values.
That’s enough for now. Trust me! In the next article I will try to show you how probabilities can fit into this model.
If, by any chance you want to skip-forward to the Infer.NET solution, make sure you read and understand the following paper that I used to create the probabilistic model for the sudoku puzzle, and snip out some pictures for this article.
Until the next article in the series, remember: the world is beautiful! Probably.