Using Probabilistic Graphic Models to Solve NP-Complete Puzzle Problems

Background: Probabilistic Graphic 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. The objective of this work is to study how PGMs can be applied to find solutions to two puzzle problems, Sudoku and the jigsaw puzzle. In the Jigsaw puzzle problem we aim to reconstruct an image from a bag of square image patches. The Sudoku and the jigsaw puzzle problems are known to be NP-complete. Several algorithms have been used to solve these problems with moderate success. In this work, we show that PGMs are quite successful in tackling these two NP-complete problems. Methods: Since Sudoku has are 9x9 nodes and 27 constrains, we map each node to 3 constraints, and each constraint to 9 nodes. First, a probability is assigned to an empty (unassigned) node based on messages obtained from that node’s three constraints. This is followed by updating the probabilities of the related nodes (same row, column, and sub-grid). This step, labeled “Elimination”, mimics the human brain. When no elimination is possible, the algorithm performs message passing from node to constraint. This is followed by message passing from constraint to node, which consists in sending the combined message of the node’s 8 neighbors. This process is repeated as many times as required. Finally, the algorithm performs a solution check and quantifies the solution. The jigsaw puzzle problem consists in reconstructing an image that is partitioned into squares, known as patches. The placing of patches is guided by an apriori computed low-resolution (that acts as local evidence) and belief propagation, (also known as message passing). As was the case with Sudoku, this problem is NP-complete and we cast the problem as a Markov Random Field. Our algorithm uses message passing to and from potential neighbors with the guidance of “Patch Compatibility” and “Patch Dissimilarity”. The quality of the run is determined by counting the number of patches which end up in their original position. Results: Both algorithms were tested by considering well known problem instances from the literature. We chose 40 hard Sudoku puzzles from the literature. Our algorithm is able to solve 36 out of 40 hard Sudoku puzzles. As for the jigsaw problem, we use testing images with different grid cut: 100x100 pixels image partitioned into 25 patches and 100 patches, and a second 200x200 pixel image partitioned into 100 patches and 400 patches. We experiment with different numbers of message passing and report our results in a table. We note that the number of correct patches is correlated with the number of message passing. Conclusion; Sudoku and the jigsaw puzzle are both NP-complete problems and be cast as Random Markov Fields. We successfully used methods drawn from the field of Probabilistic Graphic Model to tackle these problems. In our work, we show how message passing can be used between neighboring nodes to converge to good solutions.