Solución del Sudoku: Utilizando Bases de Gröbner

Abstract

El Sudoku es un rompecabezas de colocación lógica. En esta tesis se resolverá el Sudoku usando la teoría de las Bases de Gröbner, para esto se modelará el Sudoku mediante un sistema de ecuaciones polinomiales, luego se asociará al Sudoku un ideal en el anillo de polinomios de varias variables. Este ideal será el ideal generado por los polinomios que describen el sistema de ecuaciones, se calculará la Base de Gröbner reducida para este ideal, los generadores de la Base de Gröbner reducida forman un sistema de ecuaciones que es equivalente al sistema original, resolviendo este nuevo sistema se obtiene la solución al Sudoku. También se dará un método que permita decidir si dado un sistema de ecuaciones polinomiales, este admite alguna solución, y de admitir solución, se determinara explícitamente la solución. Esto será importante para resolver el Sudoku usando las Bases de Gröbner. Se definirá un orden sobre el conjunto de monomios del anillo en varias variables, para poder obtener el algoritmo de la división entre polinomios de varias variables, luego definiremos una Base de Gröbner para un ideal polinomial, con esto, se dará condiciones para decidir cuando un elemento pertenece a un ideal polinomial.