吴方法在求解数独问题中的应用

The Application of Wu’s Method of Characteristic Set in Solving Sudoku Problem

吴方法是计算机代数中的一种重要方法,主要通过求解吴特征列来达到对多项式方程组进行消元求解的目的,多项式的不可约特征序列则是在吴特征列的基础上进行因子分解得到的三角列集合,从而得到相应的零点分解,进而达到求解多项式零点的目的。本文以四宫数独为例,类比图论染色问题对数独问题进行建模,给出了一种用多项式组表示数独问题的方法,用数学软件Singular求解了该多项式组的不可约特征序列,并得到了一些相关的结论。

Wu’s method is a crucial method in computer algebra.It achieves the elimination purpose by cal-culating the Wu’s characteristic sets.The irreducible characteristic series is a set of triangular sets obtained by factoring the Wu’s characteristic sets,which can provide the zero decomposition of the polynomial equations.In this paper,the Sudoku is modeled by analogy with graph coloring problem,and a method to express Sudoku with polynomial equations is given.Taking Shidoku as an example,we compute the irreducible characteristic series of its polynomial equations and some conclusions are listed.