Scribd
Upload
6 views5 pages

Online Pathfinding Algorithms

This document contains 3 algorithms - Backtracking, Backtracking recursively, and Greedy - for solving the knight's tour problem of moving a knight on a chessboard such that it visits every square only once. The Backtracking algorithm uses a numar function to count empty neighboring squares and tries all possible moves, backtracking when it gets stuck. The Backtracking recursively algorithm does the same recursively. The Greedy algorithm also uses numar to always choose the move with the fewest empty neighbors.

Uploaded by

Arina Bulancea
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
6 views5 pages

Online Pathfinding Algorithms

This document contains 3 algorithms - Backtracking, Backtracking recursively, and Greedy - for solving the knight's tour problem of moving a knight on a chessboard such that it visits every square only once. The Backtracking algorithm uses a numar function to count empty neighboring squares and tries all possible moves, backtracking when it gets stuck. The Backtracking recursively algorithm does the same recursively. The Greedy algorithm also uses numar to always choose the move with the fewest empty neighbors.

Uploaded by

Arina Bulancea
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Backtracking

#include <iostream>

using namespace std;


int
n,m,k,diry[]={0,1,2,2,1,-1,-2,-2,-1},dirx[]={0,-2,-1,1,2,2,1,-1,-2},x,y,a[100][100],xmin,ymin,minp
,nrmutare;
int numar(int x,int y)
{
int nr=0;
for(int i=1;i<=8;i++)
{
int xp=x+dirx[i];
int yp=y+diry[i];
if(xp>=1 && xp<=n && yp>=1 && yp<=m && a[xp][yp]==0)
nr++;
}
return nr;
}
int main()
{
cin>>n>>m>>x>>y;
k=1;
a[x][y]=k;

while(k<n*m)
{ minp=9;
for(int i=1;i<=8;i++)
{
int xd=x+dirx[i];
int yd=y+diry[i];
if(xd>=1 && xd<=n && yd>=1 && yd<=m && a[xd][yd]==0)
{
nrmutare=numar(xd,yd);
if(nrmutare<=minp)
{
minp=nrmutare;
xmin=xd;
ymin=yd;

}
}

}
x=xmin;
y=ymin;
k++;
a[x][y]=k;

for(int i=1;i<=n;i++)
{for(int j=1;j<=m;j++)
cout<<a[i][j]<<" ";
cout<<endl;}
return 0;
}

Backtracking recursiv
#include <iostream>

using namespace std;


int n,m,k,diry[]={0,1,2,2,1,-1,-2,-2,-1},dirx[]={0,-2,-1,1,2,2,1,-1,-2},x,y,a[100][100],xs,ys;
bool gasit=false;
bool ok(int i, int j)
{
if(i>=1 && i<=n && j>=1 && j<=m)
{
if(a[i][j]==0)
return true;
else return false;
}
else return false;
}

bool solutie(int k)
{
return k==n*m;
}
void afisare()
{
int i,j;
for(i=1;i<=n;i++)
{for(j=1;j<=m;j++)

cout<<a[i][j]<<" ";
cout<<endl;
}
gasit=true;
}
void Back(int x,int y,int k)
{ int i;
if(!gasit)
{for( i = 1 ; i <= 8 ; i++)
{
int xnou=x+dirx[i];
int ynou=y+diry[i];
if(ok(xnou,ynou))
{
if(solutie(k))
{ a[xnou][ynou]=k;
afisare();}

else {a[xnou][ynou]=k;
Back(xnou,ynou,k+1);
a[xnou][ynou]=0;}
}

}
}
}
int main()
{
cin>>n>>m>>xs>>ys;
a[xs][ys]=1;
Back(xs,ys,2);
return 0;
}

Greedy
#include <iostream>
#include <fstream>

using namespace std;


int
n,m,k,diry[]={0,1,2,2,1,-1,-2,-2,-1},dirx[]={0,-2,-1,1,2,2,1,-1,-2},x,y,a[101][101],xmin,ymin,minp
,nrmutare;
ifstream f("saritura_calului1.in");
ofstream g("saritura_calului1.out");

int numar(int x,int y)


{
int nr=0;
for(int i=1;i<=8;i++)
{
int xp=x+dirx[i];
int yp=y+diry[i];
if(xp>=1 && xp<=n && yp>=1 && yp<=m && a[xp][yp]==0)
nr++;
}
return nr;
}
int main()
{
f>>n>>m>>x>>y;
k=1;
a[x][y]=k;

while(k<n*m)
{ minp=9;
for(int i=1;i<=8;i++)
{
int xd=x+dirx[i];
int yd=y+diry[i];
if(xd>=1 && xd<=n && yd>=1 && yd<=m && a[xd][yd]==0)
{
nrmutare=numar(xd,yd);
if(nrmutare<=minp)
{
minp=nrmutare;
xmin=xd;
ymin=yd;

}
}

}
x=xmin;
y=ymin;
k++;
a[x][y]=k;

}
for(int i=1;i<=n;i++)
{for(int j=1;j<=m;j++)
g<<a[i][j]<<" ";
g<<endl;}
return 0;
}

You might also like