Uma introdução à computação algébrica: resolvendo algebricamente um Shidoku

Abstract

Nesse trabalho apresentamos como as Bases de Gröbner juntamente com o sistema de com putação algébrica CoCoA podem ser usados para resolver algebricamente um quebra-cabeça Shidoku (uma versão reduzida do conhecido Sudoku). Apresentamos os pré-requisitos necessá rios da Álgebra como o Algoritmo da Pseudodivisão até a Teoria das Bases de Gröbner com os S-polinômios e o Algoritmo de Buchberger. Fazemos uma breve introdução ao CoCoA e por fim apresentamos uma implementação da resolução algébrica do Shidoku neste software. A dissertação tem o objetivo de ser uma base para um projeto de iniciação científica com estudantes do Ensino Médio e também como fonte de aprofundamento para professores e graduandos de Matemática.

In this work, we present how Gröbner Bases coupled with CoCoA computer algebra system can be used to algebraically solve the Shidoku puzzle (a small variant of the well-known Sudoku). We show Algebra requirements covering the Pseudo-Divison Algorithm to the Gröbner Bases theory including S-polynomials and Buchberger’s Algorithm. We also make a brief introduction to the CoCoA system and propose an algebraic implementation for solving a Shidoku in this software. The dissertation aims to be a scientific project for high school students and also stand as a study source for mathematics teachers and undergraduates.