-1

i have heard that backtracking can be used to find whether a given word exits in a 2-D matrix of alphabets but am not sure how to implement it. E.g if we have a matrix like :

G O P
N N A
A B E

and the rules are that one can move horizontally,vertically and diagonally from any position then we need to tell whether the above matrix contains the word "GONE" . Here we can first store the positoin of all G's (if >1 G is present) and start checking from each of that postion but how to check using backtracking? Thanks.

pranay
  • 2,339
  • 9
  • 35
  • 58

2 Answers2

2

This game is called Boggle. Here is a nice thread on SO about it (including code example).

Community
  • 1
  • 1
Franck Dernoncourt
  • 77,520
  • 72
  • 342
  • 501
0

I will pseudo code the algorithm

Find the starting letter from your word start backtraking function with that position (pass the next letter or the next position of leeter)

if this is the last position you are looking, you find it. Check if letter at N (north) is the next letter, Ok call function again with that position (where you are now) and the next letter (or the position in your string of next letter). If not check letter at NE and so on. If you finish and not find a good match, return to previous call.

HTH, feel free to ask for clarifications if you need.

gbianchi
  • 2,129
  • 27
  • 35