Probabilistic sudoku using Infer.NET #2

Probably hello again! We started covering the probabilistic solution to the sudoku puzzle, and I have promised a series of articles that will guide you through the journey I took to tackle this topic. Ultimately, we’ll also have a little working example.

Firsts things first. In the previous article I have promised you that I will show you how probabilities are to be included in the graphical model. In order to tacke this please consider the following questions:
What problems does a probabilistic model solve for the sudoku puzzle? How do you imagine a probabilistic sudoku model? When is it appropriate to use a probabilistic model? Now, before going on to read the rest of the content, please spend some time to formulate your own answers to these questions. Anyway, I will provide some useful answers below, because, as you figured, these are key questions in understanding this topic 😊

(Anoying pause … )

Let’s go:
When would probabilities be apropriate for tackling sudoku ? If any sudoku puzzle has one single solution (well-formed sudoku puzzle), then the usage of probabilities can be usefull, but without too much of a benefit. If, however, multiple solutions are possible for a sudoku puzzle, then, using probabilities to solve a puzzle can bring alot of benefits. If you want to find out more about the interesting math behind sudoku, feel free to check this out:
http://pi.math.cornell.edu/~mec/Summer2009/Mahmood/More.html

How do you imagine a probabilistic model for the sudoku game ? Would it be cool to haave, given a sudoku puzzle, and a certain random value (say, 3) a probability distribution for each cell and 3 as a possible value? Check out the image bellow:

Now, I used a 4×4 sudoku as an example. It is pretty dificult to come with a non well-formed 4×4 sudoku, but I made an effort 🙂

white means 0 probability (easy), light shade is low (whatever that means) probability, darker means higher. Same shade means same probability. If you imagine a non well-formed 12×12 puzzle you can see where this probability game comes in handy 🙂

Good, now, remember, in the last article we have established that we are going to use a graphical model (using graph theory) for tackling the probabilistic sudoku challenge. I promised I will show you how probabilities can fit into this model, so here it is:

Each solution/value node in the graph will hold a vector describing probability distribution for each possible value. e.g. for cell number 2 (r1,c2) the probability vector is (0, 50%, 0, 50%). Indexes the vector are 1 through N (4). 4 Because we have a 4×4 puzzle for this example :). Yes, they are not zero based 🙂 This is it. That’s all I wanted to tell you for now.

In order for me give you content that is as engaging as possible, I will do my best to write the next article so that it involves as little as possible in regard to the rest of the mathematics involved in this solution, and go directly to the Inver.NET implementation. Belive me, trying to formulate an article that omits a hard definition of marginal distribution and Belief Propagation (sum-product message passing) and goes directly to using these concepts in code will be dificult.

But I trust that we can do it next time! Probably!

Probabilistic sudoku using Infer.NET #1

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

Fig 1. 4×4 sudoku puzzle

Trying to drill down the components of a sudoku puzzle, we can come up with the following:

  1. 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)
  2. 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.
Fig 2. Constraints for the sudoku puzzle

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

Fig 3. The graphical model

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.