Multiple constraint satisfaction by belief propagation: An example using Sudoku

被引：16

作者：

Moon, Todd K. ^{[1
]}

Gunther, Jacob H. ^{[1
]}

机构：

[1] Utah State Univ, Logan, UT 84322 USA

来源：

PROCEEDINGS OF THE 2006 IEEE MOUNTAIN WORKSHOP ON ADAPTIVE AND LEARNING SYSTEMS | 2006年

关键词：

D O I：

10.1109/SMCALS.2006.250702

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

The popular Sudoku puzzle bears structural resemblance to the problem of decoding linear error correction codes: solution is over a discrete set, and several constraints apply. We express the constraint satisfaction using a Tanner graph. The belief propagation algorithm is applied to this graph. Unlike conventional computer-based solvers, which rely on humanly specified tricks for solution, belief propagation is generally applicable, and requires no human insight to solve a problem. The presence of short cycles in the graph creates biases so that not every puzzle is solved by this method. However, all puzzles are at least partly solved by this method. The Sudoku application thus demonstrates the potential effectiveness of BP algorithms on a general class of constraint satisfaction problems.

引用

页码：122 / +

页数：2