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;

}