Using Probabilistic Graphical Models to Solve NP-complete Puzzle Problems

Probabilistic Graphical Models (PGMs) are commonly used in machine learning to solve problems stemming from medicine, meteorology, speech recognition, image processing, intelligent tutoring, gambling, games, and biology. PGMs are applicable for both directed graph and undirected graph. In this work, I focus on the undirected graphical model. The objective of this work is to study how PGMs can be applied to find solutions to two puzzle problems, sudoku and jigsaw puzzles. First, both puzzle problems are represented as undirected graphs, and then I map the relations of nodes to PGMs and Belief Propagation (BP). This work represents the puzzle grid as a bipartite graph, which contains disjoint sets S and C such that the graph’s edges connect vertices in S only with vertices in C, and vice versa. S contains all the cells. C contains all constraint groups. Then, I apply the well-known sum-product message passing (MP) algorithm, which is also known as BP. In the jigsaw puzzle problem, I aim to reconstruct an image from a collection of square image patches. I use the neighborhood pairwise compatibility and local evidence similarity to evaluate the correctness of a reconstruction. The sudoku and the jigsaw puzzle problems are known to be NP-complete [16, 6]. In this work, I implement the algorithms mentioned above, and show that PGMs are quite successful in rapidly tackling these two problems. I am able to solve 90% of hard sudoku puzzles within 17 rounds of MP. The jigsaw images that are reconstructed by the chosen algorithm are reasonable