This paper makes a brief historical and conceptual introduction about Graph Theory and Graph Coloring, we introduce the problem of the Sudoku puzzle and show how to solve it through Graph Coloring. For this, we have molded the problem in a Graph, using an adjacency matrix, and from a small art state review of the algorithms responsible for solving this problem, we also introduce a solution using two exact algorithms, one using Backtracking and other using the Degree Saturation for choosing the visitation order of the vertex. In the end, we show the results of the algorithms after applying them to resolutions of instances of the Sudoku and Graphs from the library of benchmarks for Graph Coloring. Resumo. Este artigo faz uma breve introdução histórica e conceitual sobre a teoria de Grafos e coloração de Grafos, introduzimos o problema do jogo Sudoku e mostramos como resolvê-lo através da coloração de grafos. Para isso, modelamos o problema em Grafo, usando matriz de adjacências, e a partir de uma pequena revisão do estado da arte dos algoritmos responsáveis por resolver esse problema, introduzimos uma solução usando dois algoritmos exatos, um usando backtracking e outro usando o Degree Saturation para escolha da ordem de visitação dos vértices. Ao final, exibimos os resultados dos algoritmos após aplicá-los a resolução de instâncias de Sudoku e Grafos de uma biblioteca de benchmarks para Coloração de Grafos.
A teoria de grafos teve início com o problema das pontes de Königsberg, resolvido por Euler [Euler 1736], já a coloração de grafos surge apenas em 1853 quando Francis Guthrie tentou colorir o mapa da Inglaterra de tal maneira que regiões com fronteiras em comum não recebessem a mesma cor, Guthrie percebeu que seriam necessárias quatro cores para isso, dando origem a conjectura das quatro cores, ele estende essa questão para toda a comunidade científica com o objetivo de saber se isso era possível a qualquer mapa ou grafo planar. O problema de confirmar a conjectura das quatro cores passou por Appel & Haken [Appel e Haken 1997] e Arthur Cayley [Cayley 1879], mas a sua demonstração só foi aceita por toda a comunidade científica quando Gonthier [Gonthier 2001] a realizou. A [Figura 1] mostra um exemplo de coloração de um mapa.
Neste artigo abordaremos a coloração de grafos aplicado ao problema do Sudoku. Este trabalho está dividido em blocos, inicialmente introduziremos alguns conceitos preliminares referentes ao Sudoku, os quais serão importantes para um melhor acompanhamento deste texto. Posteriormente modelamos o jogo Sudoku em um problema de coloração de grafos, em seguida apresentaremos os algoritmos implementados para a resolução do referido problema, após introduzir os algoritmos usados apresentaremos os testes que realizamos e traremos os resultados obtidos nesses testes, por fim concluiremos o trabalho.
O Sudoku é um jogo do gênero puzzle (quebra-cabeça), projetado por Howard Garns [Wikipédia], um arquiteto e construtor independente de puzzles. O jogo aparece pela primeira vez na edição de maio de 1979 da revista Dell Pencil Puzzles and Word Games [Wikipédia]. Sendo o Sudoku um caso particular do quadrado latino, uma construção matemática criada pelo suíço Leonhard Euler no século XVIII [Wikipédia]. O jogo consiste em uma grade de tamanho e blocos de tamanho , onde e . A grade vem com alguns quadrados já preenchidos, e o objetivo é preencher os demais com números de a sem repetir números nas linhas, colunas ou blocos. A [Figura 2] ilustra um jogo não resolvido e uma solução.
Para modelar o Sudoku em um grafo podemos pensar em cada quadrado da grade como um vértice, onde dois vértices e são adjacentes se e pertencem a mesma linha, e pertencem a mesma coluna ou e pertencem ao mesmo bloco. Portanto, como os vértices são adjacentes, existe uma aresta ligando cada vértice aos demais contidos no bloco, na coluna e na linha. Veja que aplicamos a coloração de vértices, ou seja, dois vértices adjacentes não possuem a mesma cor, porém agora as cores serão representadas por números, assim chegamos no problema da própria. A [Figura 3] ilustra um exemplo de uma modelagem em grafo para um Sudoku .
Note que podemos modelar através de grafos simples ou hipergrafos, neste trabalho optamos pela modelagem através de grafos simples. Por exemplo, considere um Sudoku , cada vértice está ligado a outros vértices, pois cada vértice precisa ter cor diferente dos vértices ligados a ele (vértices adjacentes). Nessa modelagem teremos no total arestas, como podemos ver na [Figura 4], temos a representação em grafos simples de um vértice ligado a todos os seus adjacentes em um Sudoku .
Algoritmo heurístico The [Galinier e Hao 1998];
Apresentado e modelado o problema, introduziremos algoritmos presentes na literatura para o referido problema, sendo estes:
Coloração em Largura [
Hybrid Evolutionary Algorithm (HEA)
Algoritmo que implementa o DSATUR em
usando o algoritmo de
Algoritmos de coloração de vértices usando enumeração implícita segundo modificação do algoritmo de Sewell (1996) [Segundo 2011]; [Turner 1988]
Para este trabalho implementamos um algoritmo usando a técnica de backtracking e o
algoritmo de DSatur com backtracking [
Os códigos a seguir exibem os algoritmos desenvolvidos para solucionar o
problema de Coloração de grafos, eles foram desenvolvidos baseados em estudos dos
algoritmos encontrados na literatura e descritos anteriormente nesta seção. Note que os
códigos nessa seção podem ser obtidos a partir do github [
O primeiro código, exibido no arquivo GerarMatriz.cpp [
O segundo, Colorir.cpp [
Por último, temos o ColorirInteligente.cpp [
void Grafo::geraMatrizAdjacencia(){ for (unsigned int i = 0; i <_numeroVertices; i++){ for(unsigned int j = 0; j < _numeroVertices; j++){ if(j >= (i/_ordem)*_ordem && j < (i/_ordem)*_ordem + _ordem) else _matrizAdjacencia[i][j] = true; if(j%_ordem == i%_ordem) _matrizAdjacencia[i][j] = true; 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. true; 19. 20. 21. 22. 23. 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20.
} else
_matrizAdjacencia[i][j] = false;
GerarMatriz.cpp bool Grafo::grafoColorindoAuxiliar(unsigned int color[], unsigned int contador){ if(contador == _numeroVertices)
return true; if(color[contador]) { if(grafoColorindoAuxiliar(color, contador +1))
return true; else
Colorir.cpp 1. bool Grafo::grafoColorindoAuxiliar(unsigned int color[], unsigned int contador, int saturacao[]){ 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27.
if(grafoColorindoAuxiliar(color, contador +1, saturacao)) if(!saturacaoCheia(saturacao))
return true; int cor = getSaturacaoMaior(saturacao, color); if(color[cor]){ } saturacao[cor] = -1; else return true;
Realizamos vários experimentos com os algoritmos implementados, todos os exemplares foram executados no mesmo computador possuindo como especificação técnica 8 GB de memória RAM e processador i5 4420 x64. Inicialmente vamos mostrar os resultados referentes aos algoritmos aplicados em exemplos de Sudoku, posteriormente em problemas de coloração de grafos em geral. Vale notar que Algoritmo 1 corresponde ao Colorindo.cpp e o Algoritmo2 corresponde ao
O experimento com exemplos do jogo foi realizado para diversos níveis do puzzle: , e . Todos os exemplares de Sudokus foram retirados do [sudoku download].
Para o Sudoku , realizamos experimentos para 4 (quatro) níveis de dificuldades, sendo eles fácil, médio, difícil e muito difícil. Para cada nível de dificuldade realizamos experimentos com 5 (cinco) Sudokus diferentes, sendo sempre as cinco primeiras configurações obtidas a partir do [sudoku download(fácil 9x9)] para o fácil, [sudoku download(médio 9x9)] para o médio , [sudoku download(difícil 9x9)] para o difícil e [sudoku download(muito difícil 9x9)] para o muito difícil.
Dificuldade Muito difícil Difícil Médio Fácil
Para o Sudoku 16 × 16, realizamos experimentos para dois níveis de dificuldades, sendo eles fácil e médio. Em cada nível de dificuldade realizamos experimentos com 5 (cinco) Sudokus diferentes, sendo sempre as cinco primeiras configurações obtidas à partir de [sudoku-download (fácil 16x16) ] para o fácil e de [sudoku-download (médio 16x16) ] para o médio.
Dificuldade Algoritmo 1 - Tempo médio(s) Algoritmo 2 - Tempo médio(s) Médio 0,2715000 0,1072125 Fácil 0,0618132 1,3481394
Para o nível de dificuldade 25 × 25, realizamos um experimento com 5 (cinco) configurações diferentes do jogo, sendo sempre as cinco primeiras configurações obtidas à partir de [sudoku-download (25x25) ].
Algoritmo 1 - Tempo médio(s) 9702
Algoritmo 2 - Tempo médio(s) 46,3352
Realizamos 24 testes com a biblioteca de benchmark [d’Angers a] [Harrisburg a] [Trick’s a], cada arquivo de testes seguiu o padrão do DIMACS [library]. Todos os resultados obtidos estão representados na Tabela 4 e cada caso de teste pode ser obtido
Teste N° Vértices Algoritmo1: Tempo - N° Cores Algoritmo2: Tempo - N° Cores Arestas 812 755 2940 1276 986 2360 21695 9757 16680 16750 17343 43081 43571 49629 245000 245830 246708 249826 449449 7844 9695 103368 12506 212400 0,00004800 - 12 cores 0,00004200 - 7 cores 0,00012000 - 16 cores 0,00009780 - 9 cores 0,00008721 - 12 cores 0,00013100 - 8 cores 0,00258300 - 46 cores 0,00157900 - 18 cores 0,00264300 - 30 cores 0,00256700 - 31 cores 0,00321900 - 37 cores 0,02045700 - 64 cores 0,02097800 - 64 cores 0,01199100 - 31 cores 0,09307500 - 126 cores 0,09129700 - 125 cores 0,09105600 - 125 cores 0,09766900 - 127 cores 0,13832000 - 321 cores 0,00620100 - 9 cores 0,00577200 - 6 cores 0,06986000 - 71 cores 0,01480600 - 10 cores 0,34072400 - 64 cores 0,001083 - 11 cores 0,001544 - 7 cores 0,002385 - 18 cores 0,002918 - 9 cores 0,003521 - 11 cores 0,011264 - 8 cores 0,126372 - 47 cores 0,157006 - 14 cores 0,194018 - 26 cores 0,193605 - 27 cores 0,191473 - 31 cores 1,236080 - 51 cores 1.361720 - 52 cores 1,751020 - 30 cores 4,596730 - 124 cores 4,633350 - 124 cores 4,662440 - 127 cores 4,611470 - 125 cores 2,952710 - 322 cores 2,116580 - 8 cores 3,255740 - 6 cores 8,548540 - 49 cores 8,121110 - 10 cores 56,42770 - 64 cores nas referências.
Neste trabalho, introduzimos de forma simples o conceito e história dos grafos e coloração de grafos, abordamos o problema do jogo Sudoku, fizemos uma sucinta revisão da literatura e exibimos algoritmos que resolvem o problema, tornando esse trabalho uma boa fonte de estudo para quem deseja iniciar o estudo de grafos voltado para o Sudoku, reproduzir experimentos já realizados e comparar resultados.
Além disso, realizamos vários testes de verificação para os algoritmos
apresentados, resultando em análises desses códigos com relação aos tempos de
resolução do problema. A partir dos dados coletados podemos concluir que, ao
comparar o Algoritmo1 ao Algoritmo2 eles apresentaram resultados diferentes em
alguns casos. Note que, o Algoritmo2 apresentou melhores resultados para resolução de
Sudokus mais complexos, enquanto o Algoritmo1 acabou sendo mais rápido para
problemas de coloração em Grafos Simples os quais não foram modelados a partir de
Sudokus e para Sudokus mais simples.
Figura 1.http://conteudo.icmc.usp.br/pessoas/sandra/2/MapaEUA.jpg. Accesse
Figura 2. http://jogadamais.blogspot.com.br/2013_11_01_archive.html. Accesse
Figura 3. http://www.rhydlewis.eu/images/su
Cayley, A. (1879). On the colourings of maps. da Costa e Thiago de Melo, P. P. (2008). Dissertação: Teoria de grafos e suas aplicações. d’Angers, D. I. U. Benchmark graph coloring.
angers.fr/pub/porumbel/graphs/. Accesse
Euler, L. (1736). Solutio problematis ad geometriam situs pertinentis.
Galinier, P. e Hao, J.-K. (1998). Hybrid evolutionary algorithms for graph coloring. Goldbarg, M. e Goldbarg, E. (2011). Grafos Conceitos, algoritmos e aplicações. Elsevier.
Gonthier, G. (2011). Formal proof—the four-color theorem.
Harrisburg, P. S. Benchmark graph coloring. https://turing.cs.hbg.psu.edu/txn131/
file_instances/coloring/graph_color/. Accesse
Lewis, R. M. R. (2016). A Guide to Graph Colouring, algorithms and aplications.
Sprinlibrary, B. https://sites.google.com/site/graphcoloring/. Accesse