turkmath.org

After recalling some fundamental definitions from commutative algebra, we introduce the notion of Gröbner bases. After that we investigate the Euclidean division algorithm for uni-variate and multi-variate systems. Then we develop the theory of Gröbner bases and explain the critical role of Buchberger’s algorithm. We also demonstrate how it works with an example to find a Gröber basis.

Next, we explain how Gröbner bases algorithm works with Shidoku board. We first turn the empty Shidoku board into a system of polynomials which in turn defines an ideal. Every board, partially or fully filled, defines a similar ideal. However, all such ideals contain the ideal we generate for the empty board. The Gröber bases and the Buchberger Algorithm help us to translate the constraints given by partially filled boards into an algorithm to find all possible solutions. Finally, as an application, we solve Shidoku and Sudoku puzzles.