I think your algorithm has some problems. First, all words
have to start with the same letter, as you only call dfs
with 0, 0 initially, the rest just after adding a character.
Second, you only print out a word if you cannot do a move -
but of course prefixes of such a string are words too.
But the big issue has to do with combinatorial explosion.
The number of possible words found this way grows exponentially
in the size of the board. It's doable for a 4x4 board, the
number of possible words will be less than 2^16, but it will
grow rapidly when you increase the size. You should take your
dictionary and preprocess it to get all possible prefixes of
valid words. And while you create your words while walking the
board, stop as soon as your constructed word so far is not a
valid prefix. No point in continueing if the first two letters
are "QX". ;-)