Generalised Belief Propagation

Documents and Papers

• A worksheet that steps you through the application of GBP to Sudoku
• Constructing Free Energy Approximations and Generalised Belief Propagation Algorithms, Yedidia, Freeman, and Weiss, 2004
• Solving Sudoku Using Combined Message Passing Algorithms, Goldberger, 2007
• Variational Message Passing, Winn, 2004
• Fractional Belief Propogation, Wiegerinck and Heskes, 2002

Code

• A selection of 4*4 and 9*9 puzzles of varying difficulty - some of which stump vanila BP
• More Boards: All known 9*9 puzzles with a minimal number of starting elements (17) - vanila BP solves 70% of these puzzles
• Determines whether a (partially filled) Sodoku grid is valid (satisfies the constraints)
• Give this function a variable node and it returns the connected factor nodes.
• Give this function a factor node and it returns the connected variable nodes.
• Returns a sub-square from a (N^2*N^2) square input. Sub-routine for some of the above algorithms.
• Returns the factor and variable nodes in a large region for Generalised Belief Propagation.
• Returns the parents of a child region in Generalised Belief Propagation.
• Required to make the above work: Gets subsquare variables.
• A recursive Sudoku solver. Note that it takes rather a long time on the difficult puzzles.