# Backtracking — Search a Word In a Matrix

Objec­tive : Given a 2D matrix of char­ac­ters. Check whether the word exist in the matrix or not. If it exists then print its path. All move­ments are allowed (right, left, up, down and diagonally).

Exam­ple:

Search a Word In a Matrix

Approach:

We will show the path as incre­ment counter

Search a Word In a Matrix — Solution

• Cre­ate a solu­tion matrix of the same struc­ture as Matrix.
• Try each cell a start­ing point.
• Check cur­rent cell is not already used and char­ac­ter in it matches with the char­ac­ter in the word at index (starts will 0).
• Check if index = length of the word, means we have found the word. return true and print the solu­tion matrix.
• If above cri­te­ria matches, mark that cell with a num­ber When­ever any cell matches with the cri­te­ria, put a num­ber cor­re­spond­ing to it in solu­tion matrix. (start with 0 and keep incre­ment­ing it, it will show us the path for the word).
• Now try to solve rest of the prob­lem recur­sively by mak­ing index +1. Check all 8 direc­tions ( up, down, left right, diag­o­nally up-left, diag­o­nally up-right, diag­o­nally down-left, diag­o­nally down-right). Check the bound­ary con­di­tions as well
• If none of the 8 recur­sive calls return true, BACKTRACK and undo the changes ( put 0 to cor­re­spond­ing cell in solu­tion matrix) and return false.
• Choose dif­fer­ent start­ing point.
• If all the start­ing points tried and solu­tion not found, return false
• See the code for bet­ter understanding.

Code:

```Output:

0 0 0 0 0
0 1 0 5 0
0 0 2 4 6
0 0 0 3 7
0 0 0 0 0

```