CODEWITHSUNDEEP
algorithmdata-structuresgraph-algorithm
zeko
zeko

Reputation: 13

Random Path that covers entire grid

I have a 3 * 3 grid. I have a 9 letter word that I have to arrange randomly in the grid. The arrangement should be such that there is a valid path in the grid that covers the word sequentially. Valid moves in the grid are: up, down, left, right, diagonal. Cant visit the same element again.

Could you please point me in the right direction? I just want to know what algorithm I should use in this case?

Sorry if I wasn't clear earlier. By random arrangement I meant that the path should not be fixed.

if I have the word BUZZINGLY, a sample path can be: | B U Z | | N I Z | | G L Y | , so whatever arrangement I choose should be different each time.

Upvotes: 0

Views: 249

Answers (1)

Gene
Gene

Reputation: 46970

There aren't very many alternatives and very few if you eliminate symmetric variants. You can just compute them all, store them, and choose one randomly. Then choose a random rotation and mirror operation.

To get you started, this considers the 3 possible starts: corner, center, and mid-edge, and finds all the valid paths.

#include <stdio.h>

int b[3][3];

void print(void) {
  for (int i = 0; i < 3; ++i) printf("%d %d %d\n", b[i][0], b[i][1], b[i][2]);
  printf("\n");
}

void search(int n, int i, int j) {
  if (i < 0 || j < 0 || i > 2 || j > 2 || b[i][j]) return;
  b[i][j] = n;
  if (n == 9) print();
  else {
    search(n + 1, i + 1, j);
    search(n + 1, i - 1, j);
    search(n + 1, i, j + 1);
    search(n + 1, i, j - 1);
    search(n + 1, i + 1, j + 1);
    search(n + 1, i - 1, j + 1);
    search(n + 1, i + 1, j - 1);
    search(n + 1, i - 1, j - 1);
  }
  b[i][j] = 0;
}

int main(void) {
  search(1, 0, 0); search(1, 0, 1); search(1, 1, 1);
  return 0;
}

Upvotes: 1

Related Questions