Diferenças entre edições de "Resolução do Sudoku"

De GNU Octave
Ir para: navegação, pesquisa
(Criou a página com "==== 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 res...")
 
(Sem diferenças)

Edição atual desde as 16h00min de 17 de outubro de 2017

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