CODEWITHSUNDEEP
calgorithmgraph
BluPixel
BluPixel

Reputation: 13

Path-finding algorithm in C

Ok so I have a board and I need to find all possible solutions of it. It starts at the top left corner of the board and by only going horizontally or vertically, it has to visit each element of the board. In order to successfully move to another element the first letter or the second letter must match with the previous. It can only visit each element once and only once but it can jump over it. So if I have a board like this:

XY YX XX

XX YY XY

YX XY XX

A sample solution path would be: XY->XX->YX->XX->XY->YY->YX->XX->XY

I was thinking of using BFS but I haven't learned about queues yet so am I able to use it without them? This is in C btw, the reason is that the programming course I'm taking is only covering C.

Upvotes: 1

Views: 6756

Answers (3)

BLUEPIXY
BLUEPIXY

Reputation: 40145

#include <stdio.h>

typedef struct data {
  const char *element;
  int  visited;
} Data;

#define Size 3

Data Board[Size][Size] = {
    {{ "XY", 0 }, { "YX", 0 },{ "XX", 0 }},
    {{ "XX", 0 }, { "YY", 0 },{ "XY", 0 }},
    {{ "YX", 0 }, { "XY", 0 },{ "XX", 0 }}
};

#define PathLen (Size*Size)

int Path[PathLen];

Data *pos(int *x, int *y){
    if(*x < 0)     *x += Size;
    if(*x >= Size) *x -= Size;
    if(*y < 0)     *y += Size;
    if(*y >= Size) *y -= Size;
    return &Board[*y][*x];
}

void neighbor(int x, int y, int wx, int wy, int level);

void search_path(int x, int y, int level){
    Path[level] = Size * y + x;
    if(level == PathLen - 1){
        int i;
        for(i=0;i<PathLen;++i){
            int x = Path[i] % Size;
            int y = Path[i] / Size;
            if(i == PathLen - 1)
                printf("%s\n", Board[y][x].element);
            else
                printf("%s->", Board[y][x].element);
        }
    } else {
        neighbor(x, y, x - 1, y, level);//origin -> left
        neighbor(x, y, x + 1, y, level);//origin -> right
        neighbor(x, y, x, y - 1, level);//origin -> up
        neighbor(x, y, x, y + 1, level);//origin -> down
    }
}
//subroutine
//origin(x,y) -> neighbor(wx,wy)
void neighbor(int x, int y, int wx, int wy, int level){
    Data *wk;
    wk = pos(&wx,&wy);
    if(wk->visited == 0 &&
       (Board[y][x].element[0] == Board[wy][wx].element[0] ||
        Board[y][x].element[1] == Board[wy][wx].element[1])){
        wk->visited = 1;
        search_path(wx, wy, level + 1);
        wk->visited = 0;
    }
}

int main(void){
    int x = 0, y = 0, level = 0;
    Board[0][0].visited = 1;
    search_path(x, y, level);
    return 0;
}
/*
XY->XX->YX->YY->XY->XX->YX->XX->XY
XY->XX->YX->YY->XY->XX->YX->XX->XY
XY->XX->YX->YY->XY->XX->XY->XX->YX
XY->XX->XY->XX->YX->XX->XY->YY->YX
XY->XX->XY->XX->YX->YY->XY->XX->YX
XY->XX->YX->XX->XY->YY->XY->XX->YX
XY->XX->YX->XX->XY->YY->YX->XX->XY
XY->XX->YX->XX->XY->XX->YX->YY->XY
*/

Upvotes: 0

amit
amit

Reputation: 178431

Note that even finding one solution, and not all of them is NP-Hard problem, because of the visit each element once and only once constraint. Your problem is actually a variation of the Hamiltonian-Path Problem on a grid.

Thus, there is no known polynomial solution do decide if such a path even exist, let alone find all of them.

@Doct0rz suggestion to use backtracking is probably your best shot to solve this problem. specifically, I'd go for some variation of DFS that maintains visited set only for the relevant branch.

Pseudo-code:

specialDFS(v,visited):
  if (visited.size == |V|):
      print this path by following the "father" field up to the root.
  for each edge (v,u):
     if (u is in visited): //do not check vertices that are already on the path
          continue
     visited.add(u)
     u.father <- v
     specialDFS(u,visited) //recursive call
     visited.remove(u) //clean the work environment, we maintain visited set only for the same path

invoke with:

visited <- {source} //add the single source here
source.father <- null //source is the root of all paths
specialDFS(source,visited)

Note: This is high-level OOP-style pseudo code. Since the question is tagged homework - I'm leaving the actual implementation to you.
Good Luck!

Upvotes: 3

Doct0rZ
Doct0rZ

Reputation: 163

You could try backtracking and pruning. It uses recursion instead of queues.

http://en.wikipedia.org/wiki/Backtracking

Upvotes: 3

Related Questions