# 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

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.

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