Teoria de Conjuntos e Resolução de Sudoku

Prévia do material em texto

MATEMÁTICA APLICADA IV
 ETAPA I
	
	Trabalho desenvolvido na disciplina Matemática Aplicada IV, 5º semestre do Curso de Ciência da Computação, Anhanguera Educacional – Rondonópolis/MT como parte da avaliação da disciplina, sob orientação da Prof.ª Márcia Moreno.
RONDONÓPOLIS – MT
2015
Título
Conceitos básicos de teoria de conjuntos. Álgebra de conjuntos.
 Introdução
 Neste relatório será apresentado um exercício sobre o SUDOKU, um jogo de quebra quebra-cabeça que se baseia na concordância racional de números. O SUDOKU é proveniente de um acrônimo da expressão “Os números devem ser únicos”, o jogo é composto por uma grade 9X9 constituída de sub-grades 3X3 denominadas de regiões. Certas células já contêm números, chamados de dados. A finalidade do jogo é preencher as células vazias, com um número em cada célula, de forma que cada coluna, linha e região contenham os números 1-9 apenas uma única vez.
Procedimento
	Para a resolução do sudoku, temos varias formas possíveis, O desafio proposto é usar um método que envolva conjuntos para determinar a gama de possibilidades de preenchimento de cada casa.
 Método proposto: Considerem uma casa fixa sem preencher. Ao eliminar os outros algarismos que aparecem na mesma coluna, na mesma linha ou na mesma subgrade, é possível que sobre uma única possibilidade, com a qual a casa deve ser preenchida. Para a resolução do sudoku usamos a álgebra dos conjuntos, onde atigimos, na tabela, os números não descritos em cada linha, coluna ou subgrade. Através da intersecção das linhas, colunas e subgrades não preenchidas. (¬L ∩ ¬C ∩ ¬S) retiramos as capacidades de cumprir a tabela (denominadas SDK).
 Cada linha e cada coluna foi relacionada, para que o exercício conseguisse ser determinar de um jeito mais fácil. Como um sudoku padrão possui 9 linhas e 9 colunas, intitular as linhas do seguinte forma: L1, L2, L3, L4, L5, L6, L7, L8, L9. As colunas, foram denominadas da seguinte maneira: C1, C2, C3, C4, C5, C6, C7, C8, C9. Já as subgrades também tiveram a mesma denominação (S1, S2, S3, S4, S5, S6, S7, S8, S9).
Com isso, conseguimos de maneira convincente obter as possibilidades, seguindo a sequência ¬L1, ¬C1, ¬S1; ¬L1, ¬C2, ¬S1; ¬L1, ¬C3, ¬S1;...; ¬L9, ¬C9, ¬S9.
Resultados/Cálculos
Sudoku inicial:
 
Sudoku Final:
 
 
* cada linha é um conjunto Li, i=1,2,...,9 
o Li={x |x é um inteiro e 1 ≤ x ≤ 9} 
o Li= Lj, ou seja, x (x  Li  x  Lj)  (x  Lj  x  Li) 
* cada coluna é um conjunto Ci, i=1,2,...,9 
o Ci={x |x é um inteiro e 1 ≤ x ≤ 9} 
o Ci= Cj, i,j=1,2,...,9, ou seja, x [(x Ci x  Cj)  (x Cj x  Ci) 
* cada subgrade é um conjunto Si, i=1,2,...,9 
o Si={x |x é um inteiro e 1 ≤ x ≤ 9} 
o Si= Sj, i,j=1,2,...,9, ou seja, x (x  Si  x  Sj)  (x  Sj  x  Si) 
o os conjuntos Li, Ci e Si, i=1,2,...,9, são iguais, isto é, x (x  Li  x  Ci)  (x  Ci  x  Li)  (x  Li  x  Si)  (x  Si  x  Li)  (x  Ci  x  Si)  (x  Si  x  Ci) 
1
2
3
4
5
6
7
8
9
SDK={1,3,4,5,7}
SDK={2,3,4,5,7}
SDK={1,2,3,4,7}
SDK={3,5,7,9}
SDK={1,5,7,9}
SDK={1,3,5,7}
 
SDK={1,3,4,5,7,8}
 
 
SDK={2,3,4,5,6,7}
 
SDK={3,5,6,7}
SDK={1,3,5,6,7,8}
SDK={1,3,5,6,7,8}
SDK={2,3,4,5,7}
SDK={1,3,5,7}
SDK={1,2,3,4,5,7}
SDK={1,3,5,7,8}
SDK={3,5,7}
 
SDK={3,5,7,9}
 
 
SDK={3,5,7}
SDK={1,3,5,7,9}
SDK={1,3,5,7,9}
SDK={3,4,5,6,7,9}
 
SDK={2,4,7}
 
SDK={2,5,6,7}
SDK={3,4,5,6,7}
SDK={3,5,6,7}
SDK={3,5,6,7,9}
SDK={3,5,7,8,9}
SDK={3,4,5,6,7,9}
 
SDK={3,4,7}
SDK={3,4,5,6,7}
SDK={5,6,7,8}
SDK={3,4,5,6,7,8}
SDK={3,5,6,7}
 
SDK={3,5,7,8,9} 
Conclusão
Por tanto, com o preparo desse trabalho, constatamos que, mesmo com diversas possibilidades, há somente uma maneira de preenchermos o sudoku, pois este requer bastante atenção e análise para obter uma solução satisfatória.
Bibliográfia
Solucionador Sudoku. Disponível em: <http://www.sudoku.name/sudoku-solver/pt>. Acesso em: 01 abr. 2015.
BUENO, Silveira. Dicionário GLOBAL escolar 2007. 766 p.
Solucionador Sudoku. Disponível em: <http://www.sudoku.name/sudoku-solver/pt>. Acesso em: 01 abr. 2015.
Jean-Paul Delahaye