Hanoi Tower´s problem using recursion

Hello i´m developping a program to solve the hanoi tower problem using a recoursive function but it doesn´t seens to work.I´m going to put the code that i have writen and going to explain the ideia and the data matrixes.

Main program:

\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\

N=5;
torre_final =1;
vec_movimentos = zeros ((power(2,N)-1),4);
for i=1:size(vec_movimentos,1)
    vec_movimentos(i,1)=i;
end
tabuleiro = zeros(N,3);
tabuleiro(:,1)=1:N;
n_jogada =1;
[vec_movimentos] = hanoi_code(N,torre_final,vec_movimentos,n_jogada,tabuleiro);

\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\

hanoi_code is my recursive function and the matrix 'tabuleiro' represents the 3 tower´s with N disk. 'vec_movimentos' is a matrix that describes the moves that the user has to do in order to resolve the problem. The first column of 'vec_movimentos' is the counter of the number of moves; the second column is what piece the user has to move; the third column is the inicial tower that the piece is located at; the forth column is the final cloumn that the piece is going to be move to;'torre_final' is a variable with 2 possible values: 1 or 2. If torre_final = 1 then the solution is going to be formed in the center tower; if torre_final=2 then the solution is going to exist in the final right tower

hanoi_code:

\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\

function [vec_movimentos] =hanoi_code(N,torre_final,vec_movimentos,n_jogada,tabuleiro)
%torre_final == 1 consiste no deslocamento para a torre 1 posição à direita
%torre_final == 2 consiste no deslocamento para a torre 2 posições à
%direita
 if N > 0;
hanoi_code(N-1,torre_final,vec_movimentos,n_jogada,tabuleiro);

shift(N,torre_final,vec_movimentos,n_jogada,tabuleiro);
hanoi_code(N-1,torre_final,vec_movimentos,n_jogada,tabuleiro);
 else
 return;
end

\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\

we have here the recursive code ,'n_jogada' indicates what the current move is.

shift:

\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\

function [vec_movimentos] =shift(N,torre_final,vec_movimentos,n_jogada,tabuleiro)
vec_movimentos(n_jogada,2)=N;
[inicio,fim]= game(N,tabuleiro,torre_final);
vec_movimentos(n_jogada,3)=inicio;
vec_movimentos(n_jogada,4)=fim;
n_jogada =n_jogada+1;
end

\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\

It´s not necessary to display the game code because the program doesn´t get there and i have already test this part of the code and it seens to work.

My main problem is that the recursion seens not to work. When i run the program the 'vec_movimentos' remains the same , and the 'tabuleiro' also remains in the original configuration. The 'n_jogadas' that should = 31 , is equal =1. 31 because the numbers of moves if 2^(N)-1 , and N=5. Any ideia what´s the problem? What´s wrong with the recursion part?

Thank you in advance

Answer 1

[Walter Roberson]

Remember that calling

hanoi_code(N-1,torre_final,vec_movimentos,n_jogada,tabuleiro);

computes a value by calling hanoi_code, and then discards the value because you did not assign it to a variable and the semi-colon says not to bother to print the result either.

[João Domingos]

Im seeing the problem. The matrix that is passed during the recursion is the 'vec_movimentos' original and not that , that is suposed to be altered from the code. How can i resolve this problem? My hanoi_code function has to return that matrix it canno´t be a void function

[Stephen23]

vec_movimentos = hanoi_code(N-1,torre_final,vec_movimentos,n_jogada,tabuleiro);

vec_movimentos = shift(N,torre_final,vec_movimentos,n_jogada,tabuleiro);

MATLAB uses pass-by-value, not pass-by-reference, so if you want the variable to change then you need to allocate it as an output.

[João Domingos]

Thank you Stephen Cobeldick , with my recent changes and your help the code already works perfectly. Ignore the second version of the code that i posted that´s not the final version. If anyone what´s to try it i will post the final version here. Thank you again for the help Stephen Cobeldick

Answer 2

[João Domingos]

\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\

%Inputs
N=5;
torre_final =1;
%Vector com os movimentos a tomar. Linhas representam a peça a mexer , e a
%coluna representa qual o destino. Por  exemplo entrada i ,j indica que
%temos de mover a peça i para a torre j. A terceira dimensão indica o
%número da jogada , por exemplo entrada i,j,k indica que a jogada k
%consiste em mover a peça i para a torre j
vec_movimentos = zeros ((power(2,N)-1),4);
for i=1:size(vec_movimentos,1)
    vec_movimentos(i,1)=i;
end
tabuleiro = zeros(N,3);
tabuleiro(:,1)=1:N;
n_jogada =1;
[vec_movimentos,n_jogada,tabuleiro] = hanoi_code(N,torre_final,vec_movimentos,n_jogada,tabuleiro);

\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\

function [vec_movimentos, n_jogada,tabuleiro] =hanoi_code(N,torre_final,vec_movimentos,n_jogada,tabuleiro)
%torre_final == 1 consiste no deslocamento para a torre 1 posição à direita
%torre_final == 2 consiste no deslocamento para a torre 2 posições à
%direita
 if N == 0;
     return
 else
hanoi_code(N-1,torre_final,vec_movimentos,n_jogada,tabuleiro);

[vec_movimentos, n_jogada, tabuleiro]= shift(N,torre_final,vec_movimentos,n_jogada,tabuleiro);
hanoi_code(N-1,torre_final,vec_movimentos,n_jogada,tabuleiro);
end

\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\

function [vec_movimentos, n_jogada, tabuleiro]

=shift(N,torre_final,vec_movimentos,n_jogada,tabuleiro)
vec_movimentos(n_jogada,2)=N;
[inicio,fim,comparacao]= game(N,tabuleiro,torre_final);
vec_movimentos(n_jogada,3)=inicio;
vec_movimentos(n_jogada,4)=fim;
aux_1 = find(tabuleiro(:,inicio)==0);
if isequal(isempty(aux_1),1)==0 
tabuleiro(max(aux_1)+1,inicio)=0;
else
    tabuleiro(1,inicio)=0;
end
aux = find(tabuleiro(:,fim)==0);
if isequal(isempty(aux_1),1)==0 
tabuleiro(max(aux),fim)=N;
else
    tabuleiro(5,fim)=N;
end
n_jogada =n_jogada+1;
end

\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\

function [inicio,fim,comparacao]= game(N,tabuleiro,torre_final)
fim = 0;
%No vector de comparações vamos adicionar uma linha a mais que contém
%informação sobre quais as 2 torres possíveis para movimentação. As
%restantes linhas e colunas formam o tabuleiro com portas e paredes de
%jogadas possíveis
comparacao = zeros(2,2);
indice = find(tabuleiro ==N);
%Ver posição dos indices e conforme estejamos na primeira, segunda , ou
%terceira coluna o vector de comparações contém informação relativa às
%outras 2 torres. 1 indica que é possivel mover a peça para essa posição 0
%indica que não. Vector comparações com 2 linhas e 2 colunas. 1 linha
%indica as 2 torres que são analisadas. Segunda linha indica se a repectiva
%torre é possível ou não a movimentação.
    if (indice >=1 & indice<=5)
        inicio=1;
        comparacao(1,1)=2;
        comparacao(1,2)=3;
        aux = find(tabuleiro(:,2));
        if isequal(isempty(aux),1)==0
        if (tabuleiro(min(aux),2)>N)==1

              comparacao(2,1)=1;
          end
          end
          if any(tabuleiro(:,2))==0 
               comparacao(2,1)=1;
          end
          aux = find(tabuleiro(:,3));
          if isequal(isempty(aux),1)==0  
          if (tabuleiro(min(aux),3)>N)==1
              comparacao(2,2)=1;
          end
          end
          if  any(tabuleiro(:,3))==0
              comparacao(2,2)=1;
          end
      end
       if (indice >=6 & indice<=10)
           inicio= 2;
          comparacao(1,1)=3;
          comparacao(1,2)=1;
         aux = find(tabuleiro(:,3));
         if isequal(isempty(aux),1)==0     
         if(tabuleiro(min(aux),3)>N)==1
              comparacao(2,1)=1;
         end
         end
         if any(tabuleiro(:,3))==0 
             comparacao(2,1)=1;
         end
          aux = find(tabuleiro(:,1));
          if isequal(isempty(aux),1)==0 
          if (tabuleiro(min(aux),1)>N)==1
              comparacao(2,2)=1;
          end
          end
          if any(tabuleiro(:,1))==0 
              comparacao(2,2)=1;
          end
       end 
        if (indice >=11 & indice<=15)
            inicio=3;
          comparacao(1,1)=1;
          comparacao(1,2)=2;
         aux = find(tabuleiro(:,1));
         if isequal(isempty(aux),1)==0 
         if (tabuleiro(min(aux),1)>N)==1
              comparacao(2,1)=1;
         end
         end
          if any(tabuleiro(:,1))==0 
          comparacao(2,1)=1;
          end
          aux = find(tabuleiro(:,2));
         if isequal(isempty(aux),1)==0
          if (tabuleiro(min(aux),2)>N)==1
              comparacao(2,2)=1;
          end
         end
        if any(tabuleiro(:,2))==0 
            comparacao(2,2)=1;
        end
        end
  %Tomar decisão conforme torre_final
  if torre_final ==1
      if comparacao(2,1)==1
          fim = comparacao(1,1);
      else if comparacao(2,2)==1
              fim = comparacao(1,2);
          end
      end
  end
  if torre_final ==2
      if comparacao(2,2)==1
          fim = comparacao(1,2);
      else if comparacao(2,1)==1
              fim = comparacao(1,1);
          end
      end
  end

\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\

Here´s the code so you can run ti and try it. The first line of the movements matrix appears values both wrong ones. I dont get get why the first N to be used in shift is N=5 , it should be N=1 , because the recursion goes from N=5 to N=0 then the hanoi_code function return´s , and we have N=1 for the first shift call.

Thank you in advance

[Walter Roberson]

Is this the version to be ignored?