Create a hashmap from letter to position on the board.

Now for each letter, try moving there in steps, where at each step you check if it is inside the boundaries of the board.