segunda-feira, 25 de janeiro de 2010

Algoritmo para resolução do Sudoku

Os programas de computador podem empregar diferentes métodos de resolução para o quebra-cabeça Sudoku, o método mais comum é o de retorno à um estado anterior já analisado, uma forma sistematizada de tentativa e erro pela qual soluções parciais são propostas e à medida que se revelam erradas o algoritmo retorna e as corrige.

O algoritmo básico funciona com o programa inserindo o número 1 na primeira casa vazia. Se a escolha é compatível com os números já presentes no Sudoku, o programa segue para a próxima casa vazia e insere outro 1. Quando há um conflito, o algoritmo apaga o 1 que acabou de inserir e escreve 2 ou, se essa opção for inválida, 3 ou o próximo algarismo possível. Depois de chegar ao algarismo possível, passa para a próxima casa e recomeça com o número 1. Se o número que precisa ser alterado é o 9, que é o valor máximo no Sudoku padrão, o programa retorna e aumenta o número na casa anterior em uma unidade, que é onde está o penúltimo número inserido. A seguir, avança novamente até haver novo conflito. É comum o programa retroceder várias vezes antes de avançar.

Em um programa bem escrito, esse método explora amplamente todas as hipóteses e termina por encontrar uma solução, se ela existir. Caso haja múltiplas soluções, o que ocorreria para um Sudoku não-válido, o programa encontra todas.

Esta técnica de recuo pode ser codificada em algoritmos bastante pequenos. Abaixo é apresentado um algoritmo em linguagem C que utiliza essa técnica. A função "resolve" percorre todas as células da matriz tentando inserir os números de 1 a 9 em cada. Cada número é testado pela função "verifica" antes que seja inserido na célula atual. O teste é simples, verifica se já não existe o número na linha, coluna e região. A função "resolve" é chamada recursivamente para as células seguintes a fim de confirmar o número tentado na célula atual. Isso tudo é feito para cada célula da matriz. Quando terminado, o programa imprime a solução na tela.

#include <stdio.h>

int grade[9][9] = {{8,3,0,0,0,5,6,9,0},
                   {0,0,6,0,8,0,0,0,2},
                   {0,0,0,6,0,0,0,0,5},
                   {6,0,0,0,0,3,0,0,0},
                   {3,0,5,0,0,0,9,0,6},
                   {0,0,0,9,0,0,0,0,7},
                   {4,0,0,0,0,2,0,0,0},
                   {5,0,0,0,4,0,1,0,0},
                   {0,8,7,1,0,0,0,4,9}};

void imprime() {

  static int solucoes = 0;
  int l, c;

  printf("      Solucao: %d\n", ++solucoes);
  for (l = 0; l < 9; l++) {
    for (c = 0; c < 9; c++) {
      printf(" %d", grade[l][c]);
      if (c % 3 == 2) printf("  ");
    }
    printf("\n");
    if (l % 3 == 2) printf("\n");
  }

}

int verifica(int lin, int col, int n) {

  int l, c, lr, cr;

  if (grade[lin][col] == n) return 1;
  if (grade[lin][col] != 0) return 0;
  for (c = 0; c < 9; c++)
    if (grade[lin][c] == n) return 0;
  for (l = 0; l < 9; l++)
    if (grade[l][col] == n) return 0;
  lr = lin / 3;
  cr = col / 3;
  for (l = lr * 3; l < (lr + 1) * 3; l++)
    for (c = cr * 3; c < (cr + 1) * 3; c++)
      if (grade[l][c] == n) return 0;

  return 1;

}

void resolve(int lin, int col) {

  int n, t;

  if (lin == 9)
    imprime();
  else
    for (n = 1; n <= 9; n++)
      if (verifica(lin, col, n)) {
        t = grade[lin][col];
        grade[lin][col] = n;
        if (col == 8)
          resolve(lin + 1, 0);
        else
          resolve(lin, col + 1);
        grade[lin][col] = t;
      }

}

int main() {

  resolve(0,0);
  return 0;

}

6 comentários:

  1. Desculpe-me, mas no primeiro for da função resolve(), não seria n <= 9 no lugar de n = 9?
    Do jeito que está no exemplo, ele não testaria o número 9, pois sairia do looping antes disso.

    Um grande abraço do fundo do meu coração vermelho de outubro de 1917,
    Atenágoras Souza Silva.

    ResponderExcluir
  2. Muito bem observado, obrigado!
    Foi um erro na edição deste código aqui no blog. Confirmei com a fonte original.
    Obrigado pela visita.

    ResponderExcluir
  3. ola.. podias me indicar um programa onde possa fazer o debug do programa acima indicado?.. obrigado..continuaçao com o grande trabalho =)

    ResponderExcluir
  4. Existe o GDB:

    http://www.thegeekstuff.com/2010/03/debug-c-program-using-gdb/

    http://www.gnu.org/software/gdb/

    ResponderExcluir
  5. Ola Daniel :)
    Estou fazendo um sudoku em C
    e o meu professor me pediu para fazer
    um Algoritmo para resolver os sudokus
    e vi esse que voçe que eu achei muito legal
    como eu sou principiante com isso de programaçao
    tem muitas coisas que eu nao entendo rs
    e queria saber se voçe nao podia colocar esse
    codigo com algumas explicaçoes para facilitar na hora de entender
    ele... assim eu ja ia ter uma idea para fazer o meu XD
    Abraços =)

    ResponderExcluir
  6. AI esta o Algoritmo mais cade a explicação do Código ?? como vou aprender ??

    ResponderExcluir