Problems with making Puzzle 8 with A* Search in Matlab

Hi i am trying to make a program that solve puzzle 8 with A* Search in Matlab. I have done this code but i don't know how to make it work. It doesn`t order it correctly and ignores previous expanded nodes. The initial state is choose by the user and the final state must be always [1,2,3;4,5,6;7,8,0]. Could anyone help me? Thanks!

clc;
clear all;

fprintf('Starting...\n\n');

%% Declaration of variables

vi=[]; %Creating de Initial Vector
r=0;
vgoal = [1 2 3;4 5 6;7 8 0];
MaxC = 3;
MaxR = 3;
while (r~=1)
% Loop to ask for the components of the Matrix to be introduce
for aux1=1 : MaxR %For 1 to Max number of Rows
    for aux2=1 : MaxC 
    vi(aux1,aux2)= input('Enter the number in the matrix (from 1 to 8). Type "0" for the Empty one :\n');
    end
end
% Show the Start State of the Matrix
fprintf('\nStart State: \n');
for aux1=1 : MaxR
    for aux2=1 : MaxC 
        fprintf('\t %d\t',vi(aux1,aux2));
    end
    fprintf('\n');
end
% If you type 0, the program will ask you again for all the data
r=input('Is that the Matrix you wanted to create? Type "1" for YES or "0" for NO :\n');
end

vf=vi;

%% A* Search
g=0;
res=0;

while ((sum(sum(vf==vgoal)))~=res)
    for aux1=1 : MaxR 
        for aux2=1 : MaxC 
                 if (vf(aux1,aux2)==0)
                    g= g+1;
                    lf=0;
                    rf=0;
                    uf=0;
                    df=0;
                    if(aux2~=1)
                        lv=vf;
                        lv(aux1,aux2)= lv(aux1,aux2-1);
                        lv(aux1,aux2-1)=0;
                        lh = getH(lv,vgoal);
                        lf = getF(lh,g);
                    else
                        lf=1000;
                    end
                    if (aux2~=3)
                        rv=vf ;
                        rv(aux1,aux2)= rv(aux1,aux2+1);
                        rv(aux1,aux2+1)=0;
                        rf = getF(getH(rv,vgoal),g);
                    else
                        rf=1000;
                    end
                    if(aux1~=1)
                    uv=vf;
                    uv(aux1,aux2)= uv(aux1-1,aux2);
                    uv(aux1-1,aux2)=0;
                    uf = getF(getH(uv,vgoal),g);
                    else
                        df=1000;
                    end 
                    if (aux1~=3)
                    dv=vf;
                    dv(aux1,aux2)= dv(aux1+1,aux2);
                    dv(aux1+1,aux2)=0; 
                    df = getF(getH(dv,vgoal),g);
                    else
                        uf=1000;
                    end
                    if ((lf<=rf) && (lf<=uf) && (lf<=df) && (lf~=0))
                        fprintf('\nLeft: \n');
                        vf=lv;
                    end
                    if ((rf<lf) && (rf<uf) && (rf<df) && (rf~=0))
                        fprintf('\nRight: \n');
                        vf=rv;
                    end
                    if ((uf<lf) && (uf<rf) && (uf<df) && (uf~=0))
                        fprintf('\nUp: \n');
                        vf=uv;
                    end
                    if ((df<lf) && (df<uf) && (df<rf) && (df~=0))
                        fprintf('\nDown: \n');
                        vf=dv;
                    end
                

                for aux5=1 : MaxR
                    for aux6=1 : MaxC 
                        fprintf('\t %d\t',vf(aux5,aux6));
                    end
                    fprintf('\n');
                end
                fprintf('\n');
                 end
        end
    end
    c=[vf==vgoal];
    res=sum(sum(c));
    fprintf('Resultado %d\n',res);
    
end



%% Final Outputs


% Show the final State of the Matrix
fprintf('\nGoal State: \n');
for aux1=1 : MaxR
    for aux2=1 : MaxC 
        fprintf('\t %d\t',vf(aux1,aux2));
    end
    fprintf('\n');
end


%% Functions

function H = getH(vm,vgoal)
H=0;
MaxR=3;
MaxC=3;
for aux1=1 : MaxR
    for aux2=1 : MaxC 
        if (vm(aux1,aux2)~=vgoal(aux1,aux2))
            H = H+1;
        end
    end
end
end

function getF = getF(h_score,g_score)
getF=h_score+g_score;
end

[Geoff Hayes]

@Sergio Álvarez Varela - can you clarify what the rules for this game are? Why should the output always be

vgoal = [1 2 3;4 5 6;7 8 0];

?

Oh something like https://blog.goodaudience.com/solving-8-puzzle-using-a-algorithm-7b509c331288.

[Sergio Álvarez Varela]

@Geoff Hayes Yeah, it is the same problem. What you have to do is to move the empty space (0 in my case) up, down, righ or left using the A* search (Depending on the result of A* fórmula f-score = h-score + g-score). And get the vgoal state. I have found this page on Matlab: Link It is doing the same as i am trying to do and it works pretty well, but i do not understand his code.

Answer 1

[Nipun]

Hi Sergio,

I understand that you want to implement a 8-Puzzle solver with A* heuristic search. As mentioned by you, the shared code does not work as intended and you want to mend it accordingly.

Upon in-depth investigation of the shared code, I can confirm there are a few areas of improvement that might help get the desired result. They are as follows:

1. Main Loop Condition: The condition in your main while loop seems to be intended to continue until the current state (vf) matches the goal state (vgoal). However, the way res is used and updated might not correctly reflect when the goal state is reached. Consider simplifying this condition to directly check if vf equals vgoal.
2. Your method of checking if the current state matches the goal state (sum(sum(vf==vgoal))) is correct, but the way you're using res to track this is a bit convoluted. It's more straightforward to directly compare matrices using isequal(vf, vgoal).

Here's a simplified and corrected approach for the main loop and condition checks, addressing points 1 and 2:

% Correcting the misplaced 'else' conditions and simplifying the main loop condition
while ~isequal(vf, vgoal)
    for aux1 = 1:MaxR
        for aux2 = 1:MaxC
            if vf(aux1, aux2) == 0  % Found the empty tile
                % Increment g for each move
                g = g + 1;

                % Initialize variables for holding F scores of possible moves
                lf = rf = uf = df = 1000;  % Default to high value to represent 'impossible' moves

                % Check and perform moves, calculating F scores
                if aux2 ~= 1  % Can move left
                    % Calculate left move F score
                end
                % Similar checks for right, up, down with corrected 'else' placement

                % Choose move with lowest F score
                % Update vf to new state after chosen move

                % Print current state vf
            end
        end
    end
end

Hope this helps.

Regards,

Nipun