Resolução do Sudoku
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