Problem in knight tour code...need help

I'm trying to solve knight tour problem with backtracking algorithm using MATLAB.It's recursive algorithm. my code is:

function[tElaps solution]=backtrack(n,x,y,show)

if nargin==3
    show=false;
end
tStart=tic;
global boardSize;
boardSize=n;
global sol;
sol=zeros(boardSize);
sol(y,x)=1;
global movs;
global count;%to count the number of moves
count=1;
movs=[1, 2,  2,  1, -1, -2, -2, -1;2, 1, -1, -2, -2, -1,  1,  2]';
start=struct('x',x,'y',y);
if ~Solve(start,2)
    error('Solution does not exist! ');
else
    tElaps=toc(tStart);
    solution=sol;
    if(show)
        timereq=sprintf('Solution found in %f seconds..', tElaps);
        disp(timereq);
        disp(solution);
    end
end
end

the Solve function is:

function [solved]=Solve(pos,movNum)
global boardSize;
global sol;
global movs;
global count;
count=count+1;%counter increases 1 each time this function is invoked
disp(count);
if movNum==boardSize*boardSize
    solved=true;
else
for i=1:8
    solved=false;
    next=struct('x',pos.x+movs(i,1),'y',pos.y+movs(i,2));
    if valid(next)            
        sol(next.y,next.x)=movNum;
        solved=Solve(next,movNum+1);                
        if ~solved               
            sol(next.y,next.x)=0;
        end
    end
end    
end    
end

and the last function to check validity of next move is:

    function [validity]=valid(pos)
    global boardSize;    
    global sol;
    validity=false;
    validity1=pos.x<=boardSize && pos.x>=1 && pos.y<=boardSize && pos.y>=1;
    if(validity1)
        validity=validity1 && sol(pos.y,pos.x)==0;
    end
    end

The code runs in infinite sequence. I tried invoking function with backtrack(5,1,1) and the counter was running over 100000 moves and i stopped the execution. For 4*4 chess board the problem failed after 707 moves.....

[abinaya sangi]

how to perform knight's tour and it's backtracing process?