Analisando a solução para um Sudoku

Em algum momento da sua vida, já ouviu falar sobre o quebra-cabeça, mas se por acaso não sabe o que é, tome cuidado nas suas pesquisas, existe um grande risco em se tornar um viciado (assim como eu). Aqui, vamos analisar e discutir maneiras que podemos resolve-lo, obviamente utilizaremos o auxilio da tecnologia.

Nosso problema consiste em uma grid 9 x 9, o principal objetivo é preencher as linhas, as colunas e os sub quadrados 3 x 3 com números não repetidos de 1 a 9 da nossa matriz.

Resolvendo o problema

Esse é um problema como qualquer outro, primeiramente devemos analisar o que ele vai impactar e qual a melhor forma de resolve-lo. Minha primeira solução, você poderia escrever um algoritmo com backtracking. Basicamente teríamos que percorrer nossa matriz e dessa forma dizer se um determinado número é possível em determinada posição.

Backtracking

Um algoritmo de força bruta visita todas as células vazias, preenchendo os números quando foram válidos. Caso o algoritmo encontre alguma inconformidade, ele pode descartar todos os casos testados anteriormente.

A animação facilita nosso entendimento:

As vantagens

Uma solução é garantida
Esse algoritmo não é tão complexo, quanto os outros que fazem o mesmo

A desvantagem

O tempo de resolução pode ser relativamente lento, estatisticamente esse algoritmo pode requerer 15 000 à 90 000 ciclos, sendo cada ciclo uma mudança na posição de um ponteiro, conforme move-se entre as células.

Afinal, backtracking é IA?

O conceito de inteligência artificial é muito amplo, e pode ser definido de várias formas. Mas podemos pensar em algumas características básicas, tais como, capacidade de raciocínio (aplicar regras lógicas para chegar a uma conclusão) e aprendizagem (aprender com os erros e acertos, para que no futuro consiga executar de forma mais eficaz).

Os famosos algoritmos de procura que conhecemos hoje (aqui entra a técnica de backtracking), no inicio, um programa inteligente tentaria por força bruta encontrar uma solução através de todas as possibilidades possíveis.

Repensando a nossa solução

Podemos utilizar outra forma para resolver nosso problema, aliás, existem várias outras, mas vamos focar em apenas outra. Começamos analisando onde temos menos possibilidades para colocar um único número.

No exemplo acima, escolhemos uma célula que possui duas possibilidades, dessa forma temos uma nova matriz com os valores 8 e 9, da qual podemos aplicar a propagação de restrição (pode ser usada para reduzir o espaço de pesquisa e tornar o problema mais fácil para ser resolvido). Aqui temos o famoso caso de recursividade.

Programação recursiva

Indo direto ao ponto, um programa recursivo tenta resolver algo chamando a si próprio. O grande detalhe é que na segunda chamada seu valor foi influenciado pelo valor original, assim, resolvendo problema menores e no final lhe entregando uma única solução. Não é algo tão simples em entender, talvez com um exemplo vai facilitar.

Exemplo em Python:

def sumR (n):
    if n == 1:
        return 1
    else:
        return n + sumR(n-1)

Esta forma acima garante a solução de qualquer sudoku.

Algoritmos gulosos

Em cada iteração que esse algoritmo faz, ele escolhe qual a opção mais “apetitosa” que vê pela frente. Ele toma decisões com base nas informações disponíveis na própria iteração. O algoritmo guloso jamais volta atras, as suas escolhas são definitivas. Apesar do pouco uso dessa solução, pode se dizer que são muito rápidos e eficientes.

Alguns problemas que podem ser resolvidos com algoritmos gulosos:

Programação dinâmica

Essa técnica consiste em dividir o problema geral em subproblemas mais simples e ir resolvendo-os de forma iterativa, armazenando os resultados em uma tabela para serem usados quando quiser. Sendo mais especifico, a ideia é construir por etapas uma resposta já obtidas por partes menores.

Alguns algoritmos que usam programação dinâmica:

As diferenças entre algoritmo guloso e programação dinâmica

Muitas vezes é difícil diferenciar esses algoritmos, mas eles possuem algumas características especificas:

Guloso:

Pega a alternativa mais promissora;
É muito rápido;
Uma decisão tomada é definitiva.

PD:

Explora todas as alternativas de maneira eficiente;
Um pouco lento;
A cada iteração pode se arrepender de decisões tomadas.

Além desses algoritmos citados, existem vários outros. Alguns mais complexos, outros nem tanto. Espero que tenha gostado :D

Agradecimento: Esse texto foi revisado por Allan Sene

Referências: