The basic approach here is to write a backtracking search that takes the board, the start location, and a word as inputs and returns true if the word is there, false otherwise. Then write a loop that goes through the entire board calling the backtracker at each spot until the word is found or no spots are left. When exploring possible paths through the board, you need to mark squares that you have already visited to avoid overlapping paths. A 2D array of Booleans or ints could serve this purpose.

Potential Pitfalls

There are traps in this question. The sample data contains only "realistic" situations. There are some insidious bugs that are easy to introduce such that most cases will still work, but certain special cases will not (in some cases testing with other words that are on the boards in the given data but not present in the lists may reveal the bugs).

First pitfall: You could create a solution without a "visited" array, but you might find words that aren't there. For example, in the board shown in the problem, the word SALTALT would be wrongly identified as being in the board.

Second pitfall: Even with a "visited" array, you could run into trouble in cases where there are two paths to go down, but only one leads to finding the word (this happens a lot with repeated letters). In a recursive backtracker this means that if the current part of the search finds nothing, you have to mark the current location as not visited before returning. If not, you could end up not finding something that is in fact there. In the two examples below, depending on your search order (e.g. up down left right vs. left right down up) you will get two of the four words wrong if you have made this mistake. Again, cases like this are not present in the sample data.

Board:  AADA    Board:  ADAA
        DDPC            ADAA
        AACA            DPCC
        AACA            ACAA

Words:  PDDD    Words:  PDDD
        PCCC            PCCC