Problema Do Labirinto Backtrack Iterativo

Descrição da solução (qual estratégia foi utilizada?)
A fim de implementar de modo satisfatório a solução do problema apresentado, implementamos um algoritmo usando programação orientada a objetos com a linguagem JAVA, baseando-nos na técnica de backtracking. Desta forma, seguindo as restrições impostas pelo problema utilizamos o backtracking para analisar cada possível solução do problema, a partir das colunas do labirinto cujo elemento inicial seja 1.
Considerando que podemos ter movimentos em no máximo 4 direções, vamos percorrendo o labirinto tentando achar as seqüências descritas {(1),(1,2),(1,..,3),...} até que a última linha seja encontrada. Caso não consigamos prosseguir na seqüência em uma dessas 1 <= k <= 4 posições, nós abandonamos aquela posição e vamos testar outras possíveis soluções do problema.

Demonstração (intuitiva) da corretude
O algoritmo percorre a primeira linha do labirinto a procura de um ponto de entrada. Encontrando-o, procura um caminho para chegar à última linha executando um movimento para uma das posições da vizinhança que atendem às restrições do problema. Para verificar se um movimento é válido ou não, o algoritmo verifica se o movimento está dentro do limite das posições do labirinto e se a posição resultante da movimentação contém o valor esperado calculado para a seqüência.
O código simplificado do algoritmo é mostrado abaixo:

INICIALIZA () i = 0 j = 0 FAÇA SE (T[i][j] = 1) colEntr = j

SE (n <> 1) move(1, 1, i, j) SENÃO colSaida = j SE (colSaida <> -1) IMPRIMA O RESULTADO

j <- j+1;
ENQUANTO (colSaida = -1 && j < m)

MOVE (valAtual, valDest, linAtual, colAtual)

SE (valAtual == valDest) valEsp = 1 SENÃO valEsp = valAtual + 1 PARA i=0 ATÉ 3 proxLin = LinAtual + incrLin[i] proxCol = colAtual + incrCol[i] SE ((0 <= proxLin)&&(proxLin < numTotLin)&& (0 <= proxCol)&&(proxCol