How to Do BFS in a chess board for the shortest path of the king?

Question

I have given a source index and a destination index in standard chess co-ordinates. Now I have to print the shortest path from the source to destination.

#include <iostream>
#include <queue>
#include <string.h>
using namespace std;
int dx[]={1,1,1,-1,-1,-1,0,0};
int dy[]={1,0,-1,1,0,-1,1,-1};
int cost[10][10];
int parent[70];
bool visited[70];
int main()
{
    memset(parent,-1,sizeof parent);
    memset(visited,0,sizeof visited);
    memset(cost,255,sizeof cost);
    char a,b;
    cin>>a>>b;
    int s1 = a-'a',s2 = b-'0'-1;
    cin>>a>>b;
    int t1 = a-'a',t2 = b-'0'-1;
    queue<int> q;
    q.push(s1*8 + s2);
    visited[s1*8+s2] = true;
    cost[s1][s2] = 0;
    while(!q.empty())
     { 
        int u = q.front(),x=u/8,y=u%8;
        q.pop();
        for(int i=0;i<8;++i)
        {
            int vx = x+dx[i];
            int vy=y+dy[i];
            int v = vx*8+vy;
            if(vx<0 ||vy<0 || vx>=8 ||vy >=8)
                continue;
            visited[v] = true;
            parent[v] = u;
            q.push(v);

        }
    }
    int t = t1*8+t2;
    while(parent[t]!=(-1))
    {
        cout<<t/8<<" "<<t%8<<endl;
        t = parent[t];
   }
}

But when I run it with input like a8 h1 The path isn't the shortest path rather a very long path. How do I find the shortest path ?

Answer 1

Where is your BFS stop clause?

Your main loop should break once you find x == t1 && y == t2
Alternatively, you can modify parent[v] only if visited[v] was already true.
(The first option is usually better if you just want the shortest path).

Otherwise, you'll just keep developing more paths, and override the shortest path to each node.

Answer 2

You should not update a single entry of a visited array more than once, if you visit a node, that means that shortest path already found (because your graph is not weighted). Also I do not see how you handle multiple visits to the same node. Looks like you forgot to use cost array.

Answer 3

Lee algorithm might help: https://en.wikipedia.org/wiki/Lee_algorithm. It's a bfs way of getting shortest paths in a matrix.