Programação: Sudoku & I.A.

O famoso jogo Sudoku consiste em preencher uma matriz numérica, geralmente de ordem 9x9, sem que haja repetição de números nas linhas, colunas e quadrantes (subconjuntos de 3x3 da matriz inteira), dados valores iniciais fixados em células aleatórias.

Como objetivo então, o algoritmo implementado deve prover ao usuário um jogo preenchido e válido, sem que haja alteração dos valores fixos iniciais:

Jogo inicial à esq. e resolução à dir.

Meta-Heurística
Para resolução de problemas de grande escala, de otimização e complexos, como este, o uso das meta-heurísticas pode ser ideal, desde que implementada devidamente. Para encontrar a melhor solução do problema, foi utilizada uma combinação de duas meta-heurísticas: Simulated Annealing (SA) e Tabu Search (TS).

O algoritmo SA consiste numa técnica de busca local probabilística, e se fundamenta numa analogia com a termodinâmica. Este algoritmo representa uma evolução do algoritmo Hill Climbing, de mesma natureza e, assim como no HC, podemos trabalhar sua eficiência diretamente com seus coeficientes. Como complemento, o algoritmo TS consiste em guardar as soluções de cada iteração, de acordo com o tamanho do vetor tabu, para evitar redundância nas comparações da otimização, podendo assim aumentar bastante a performance e a velocidade de convergência.

Aspectos da Solução
Sobre a meta-heurística, algumas das definições fundamentais são:

• Forma da Solução
• como estrutura de dados foi utilizada uma matriz 9x9 predefinida;

• Solução Inicial
• alocar uma matriz “inicial” com uma solução válida qualquer;
• alocar uma matriz “solução”, que receberá o cruzamento da matriz inicial com a de entrada (denominada “espelho”);
• assim, teremos dados concretos (quantidade válida dos números para o jogo) para aplicar as trocas necessárias;

• Função Objetivo
• como a solução inicial já contempla validade das linhas (sem repetição), o custo por iteração se dará pelas colunas e quadrantes, sendo o custo a quantidade de números repetidos dentro destas estruturas, separadamente;

• Função Incremento
• consiste em trocar aleatoriamente valores de colunas diferentes, respeitando a regra da matriz espelho (não pode haver alteração dos índices preenchidos na matriz espelho);
• à medida que se resolve a questão do custo das colunas, “transforma-se” a matriz para o formato quadrante (quadrantes viram colunas), para se fazer o mesmo: calcular custo dos quadrantes, e o mesmo é feito com a matriz espelho (apenas a fim de verificação), contemplando assim os dois casos da otimização do problema na mesma solução;

Algoritmo

/* ------------------

 * main.cpp 
 * ------------------ */
matrizEspelho <- leMatrizEntrada();

Sudoku sudoku(matrizEspelho, tamVetorTabu, tempoMaxProcess, temperaturaInicial);

sudoku.executa();

sudoku.imprimeResultado();

/* ------------------
 * Sudoku.cpp
 * ------------------ */

Mat atual, vizinho;

atual <- inicializaMatrizSolucao();

enquanto(!fim) {

  custoAtual <- calculaCusto(atual);

  vizinho <- funcaoIncremento(atual);

  se ( insereTabu(vizinho) &&

    funcaoObjetivo(vizinho) > funcaoObjetivo(atual) &&

    random(1) < calculaSimmAnnealing(vizinho, atual)

  )

  atual <- vizinho;

  objetivo <- funcaoObjetivo(atual);

  se (objetivo < melhor)

    melhor <- objetivo;

  se ( objetivo == 0 ||

    tempo < tempoMaxProcess ||

    temperatura < congelamento

  )

  matrizSolucao <- atual;

  fim <- true;

  tempo++;

  temperatura *= CTE_TEMP;

}

Parâmetros

Foram utilizados nas execuções os seguintes parâmetros:

• Limite Tabu: 200 (entradas no vetor; inserção cíclica)
• Limite Tempo: 1.000.000 (iterações)
• Temperatura: 1.000.000.000 (inicial, até chegar abaixo de “1 / temperatura”)

Observações

A otimização do problema pode variar muito dependendo da forma com que são utilizadas as variáveis de controle do SA e do TS, assim de como é implementada as funções da heurística, em especial a função de incremento. Pode-se ajustar a temperatura inicial da solução, por exemplo, ou o tempo máximo de processamento, a fim de se obter uma solução mais precisa ou uma aproximação mais rápida.

A probabilidade de convergência desta solução foi de aprox. 97,8%, pela média das execuções, ou seja: apesar das grandes chances, nem sempre a solução vai convergir a uma solução ótima, no caso, a um jogo válido. No entanto, soluções utilizando lógica convencional, força bruta ou mesmo outras meta-heurísticas podem chegar a levar minutos - ou muito mais que isso - para prover um resultado, enquanto a solução apresentada levou um tempo médio de execução de 0.534 segundos, se saindo muito a frente das demais.