Resolução do Sudoku

De GNU Octave
Ir para: navegação, pesquisa

Resolução do sudoku

Os problemas do sudoku podem ser fáceis ou difíceis de resolver.

A função resolve aqui apresentada resolve os problemas fáceis de resolver. Isto é, resolver os problemas em que, olhando para a linha, para a coluna, e para a submatriz, conseguimos descobrir que número está em falta. Vamos percorrendo o tabuleiro várias vezes, preenchendo as casas que formos capazes de preencher.

Se não conseguirmos preencher nenhuma casa percorrendo todo o tabuleiro, então não adianta continuar a tentar. É porque o problema é mais complicado e exige outro algoritmo de resolução (mais complicado).

function res = resolve(m)
  res = m;
  do
    emfalta = length(res(res == 0));
    # printf('Faltam %d casas\n', emfalta);
    res = percorre(res);
    sofaltam = length(res(res == 0));
    # printf('Faltam %d casas\n', sofaltam);
  until (sofaltam == 0 | emfalta == sofaltam);
  if (emfalta == sofaltam)
    printf('Desisto! Demasiado complicado para mim.\n');
  endif
endfunction
 
function res = percorre (m)
  preenchidos = 0;
  res = m;
  for linha = 1:9,
    for coluna = 1:9,
      if (m(linha, coluna) == 0)
        % por preencher
        valor = calculaPossiveis(res, linha, coluna);
        if (valor > 0)
          res(linha, coluna) = valor;
        endif
      endif
    endfor
  endfor
endfunction
 
function numero = calculaPossiveis(tabuleiro, linha, coluna)
  faltanalinha = setdiff(1:9, tabuleiro(linha,:));
  faltanacoluna = setdiff(1:9, tabuleiro(:,coluna));
  faltanamatriz = setdiff(1:9, submatriz(tabuleiro, linha, coluna));
  falta = intersect(intersect(faltanalinha, faltanacoluna),faltanamatriz);
  if length(falta) == 1
    numero = falta(1);
  else
    numero = 0;
  endif
endfunction
 
function res = submatriz(m, linha, coluna)
  x = fix((linha-1)/3)*3+1;
  y = fix((coluna-1)/3)*3+1;
  res = m([x:x+2], [y:y+2]);
endfunction

Para usar esta função, guarda-se o conteúdo anterior num documento resolve.m. Alternativamente pode descarregar o documento resolve.m. Depois, aplica-se o mesmo a uma matriz, da seguinte forma:

facil = [
0 7 2  0 0 1  8 0 5;
0 5 1  0 3 7  0 9 0;
4 0 0  2 0 8  1 0 7;
 
0 4 7  5 2 0  3 0 0;
0 2 6  7 0 0  5 0 1;
5 0 0  1 0 6  0 2 9;
 
2 9 0  3 7 0  0 1 0;
7 0 0  0 6 2  0 5 3;
3 0 8  0 1 0  2 7 0 
];
>> resolve(facil)
ans =
 
           6           7           2           4           9           1           8           3           5
           8           5           1           6           3           7           4           9           2
           4           3           9           2           5           8           1           6           7
           1           4           7           5           2           9           3           8           6
           9           2           6           7           8           3           5           4           1
           5           8           3           1           4           6           7           2           9
           2           9           5           3           7           4           6           1           8
           7           1           4           8           6           2           9           5           3
           3           6           8           9           1           5           2           7           4