How to implement an algorithm for searching words in a matrix of letters?

Question

Algorithms

There is a matrix of letters 5x5, you need to find all the words. There is a dictionary with the words of the Russian language.
The next letters can be adjacent letters and letters diagonally.
We need a word search algorithm. (or the direction in which direction to dig)

In the example, the word "timidly".

Answer 1

As one of the directions:
Take the first letter of the matrix - great, check if there is such a word in the dictionary. Further from it we build all possible words with two letters - we check whether there is such a dictionary. If for some paths there are no words that also begin, the paths are considered invalid.
For example, we have a path at the current moment - fhsht - there are no words in the dictionary that begin with such a combination of letters - we do not build the path further.
The algorithm is far from optimal, but working.

Answer 2

it's a search in a graph. those. either we use DFS (Depth First Search) or BFS (Breadth First Search). Also, mark letters that are dead ends for the position (for example, 'o' in position (4,3) is a dead end for the first letter 'o' from 'timidly' since there is no 'b' nearby), in general, somehow use caching. Look here:
https://www.geeksforgeeks.org/search-a-word-in-a-2...

Answer 3

you can only speed up the search by
the probability distribution of bi (tri-) grams of your dictionary