Solucionador de Sudoku com Teoria dos Grafos

O objetivo desse trabalho é desenvolver um algoritmo que soluciona problemas de Sudoku com o auxílio do conhecimento adquirido na disciplina de Teoria dos Grafos. Se você leu os outros artigos publicados deve já imaginar que as ferramentas utilizadas é a linguagem Python com o auxílio da biblioteca networkx. Estarei partindo do principio que o leitor sabe o que é um grafo e o que é Python, as informações sobre ambos estarão disponíveis no final deste artigo. Vamos direto ao ponto!

Sudoku

Sudoku é um jogo de lógica que apareceu nos jornais da França por volta do século 19. O objetivo do jogo é colocar uma sequência de números em um quadrado dividido em 9 regiões que são divido em outros quadrados 3x3. No total pode-se ver como uma matriz 9x9. O objetivo do jogo é completar todos os espaços vazios sem repetir nenhum número dentro das regiões, na linha e coluna global.

Fig 1: Exemplo de Sudoku inicial | Fig 2: Exemplo do Sudoku resolvido

Sudoku como um Grafo

Podemos ver um Sudoku como um tabuleiro com 81 células. O grafo pode ser associado ao Sudoku se enumerarmos as células com 81 números e imaginar que cada um é um vértice. Dois vértices estão conectados se: eles estão na mesma coluna, fileira ou caixa (quadrado). Assim temos o Sudoku como um grafo. Agora temos um mapa com 81 vértices e uma imensidão de arestas, não me preocuparei com sua representação pois mesmo que um desenho fosse plotado teríamos um emaranhado que só atrapalharia na elaboração da solução e explicação do problema.

Temos então um grafo com seus vértices e arestas porém como representamos os números? Podemos interpretar cada número de 1 a 9 como uma cor diferente, faz com que possamos aplicar a teoria de coloração de vizinhos para a elaboração desse algoritmo. Então podemos facilmente enxergar que a solução de um Sudoku esta em garantir que dois vértices de mesma cor não sejam vizinhos.

O algoritmo

Fig 3: Gerando um tabuleiro

A sacada do algoritmo esta em atribuir a todos os nós vazios (ou casas sem numeros )todas as cores possíveis (1–9), assim nós iremos ir verificando a cor de seus vizinhos e retirando de sua lista de possíveis cores. Assim no final podemos atribuir as cores possíveis aos nós e ir completando o tabuleiro dessa forma.

Esta parte do algoritmo se trata apenas da criação do tabuleiro e dos quadrados, podemos interpreta-los como essa matriz ou um vetor de vetores.

Fig 4: Algoritmo Welsh-Powell

O Welsh-Powel é um algoritmo que serve para decidir como pintar os nós. Ele verifica o status de um nó para saber se ele já foi pintado ou pode ser pintado. Caso ele precise ser pintado ele verifica os vizinhos para decidir qual a cor.

Fig 5: Update e Clear

A função update verifica se um nó possui apenas uma cor em sua lista de cores, se ele só tiver uma cor o algoritmo pinta aquele nó e efetiva como já pintado. Caso contrário ele não faz nada.

A função clear apenas limpa a lista dos nós não necessários.

Fig 6: Função que acelera o processo

A função engage considera o nó falso como verdadeiro e tenta retirar dos vizinhos uma lista. Então ele roda o powell e o update novamente para receber o resultado mais “limpo” desse processo.

A função main possui as inicializações e transformações necessárias, a chamada das funções de coloração e limpeza e a exposição do resultado final, você pode achar o código fonte e o resultado em txt no seguinte link:

https://www.dropbox.com/s/bpit05h2mjpurlc/t4.zip?dl=0

Links de Referência

Grafo -> https://en.wikipedia.org/wiki/Graph_theory

Coloração de Grafos -> https://en.wikipedia.org/wiki/Graph_coloring

Python -> https://www.python.org/