Detalhes - Dissertação do PROFMAT

Aluno: ELVIS THANIEL DE SOUZA

UFOP - Universidade Federal de Ouro Preto - Ouro Preto - MG

Dissertação

Título
Explorando Sudokus Um argumento heurístico para estimar o número de puzzles.
Resumo
Sudoku é um termo abreviado da expressão japonesa “Suji wa dokushin ni kagiru”, cujo significado é “os números devem permanecer únicos”. Os precursores deste jogo são os quadrados latinos, quebra-cabeças, no qual o jogador deve preencher uma grade quadrada com um conjunto de elementos, de tal forma que cada símbolo apareça apenas uma vez em cada linha e coluna. Popular em todo o mundo, o número de Sudokus impresso em jornais e revistas de quebra-cabeças aumentou consideravelmente e o surgimento de variações com mais restrições na sua resolução tornou o jogo mais complexo. Este trabalho tem como objetivo investigar quantos quadrados de Sudoku existem fundamentados em pesquisa, em estudo do jogo, nas suas regras e nas principais técnicas utilizadas para solucionar tal quebra-cabeça. Para tal propósito, será realizada uma revisão dos conceitos de Análise Combinatória e Probabilidade que será utilizada para estimar o número de Sudokus, um estudo sobre Quadrados Latinos que mostrará o processo para sua construção e um resultado que permitirá determinar o número de quadrados latinos de ordem n. Nosso estudo mostrou que para se resolver um problema matemático complexo é necessário, previamente, resolver problemas menores e mais simples. Tal condição foi verificada quando, auxiliada pela teoria da Análise Combinatória e Probabilidade, aliada a um argumento heurístico e relaxada a condição de que as linhas e colunas do Sudoku são dependentes, apresentamos uma estimativa do número de Sudokus próximo do número real determinado pelos resultados anteriores. Assim, podemos concluir que determinar o número de quadrados latinos não é uma tarefa simples, mesmo tendo-se domínio do conhecimento de uma fórmula fechada e o auxílio de ferramentas computacionais. Este fato evidencia a dificuldade de se encontrar uma solução exata para muitos problemas, mesmo que se disponha de recursos tecnológicos avançados.
[Download TCC]

---