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!