Fun and games - Data Structures and Problem Solving Using Java - page 422

The word search
puzzle requires
searching for
words in a two-
dimensional grid of
letters. Words may
be oriented in one
of eight directions.

contains the words this , two , fat , and that . The word this begins at row 0,
column 0—the point (0, 0)—and extends to (0, 3); two goes from (0, 0) to
(2, 0); fat goes from (3, 0) to (1, 2); and that goes from (3, 3) to (0, 0).
(Additional, mostly shorter, words are not listed here.)

10.1.1 theory

We can use any of several naive algorithms to solve the word search puzzle
problem. The most direct is the following brute-force approach:

The brute-force
algorithm searches
each word in the
word list.

for each word W in the word list
for each row R
for each column C
for each direction D
check if W exists at row R, column C in direction D

Because there are eight directions, this algorithm requires eight word/row/
column (8 WRC ) checks. Typical puzzles published in magazines feature 40 or
so words and a 16 × 16 grid, which involves roughly 80,000 checks. That
number is certainly easy to compute on any modern machine. Suppose, how-
ever, that we consider the variation in which only the puzzle board is given
and the word list is essentially an English dictionary. In this case, the number
of words might be 40,000 instead of 40, resulting in 80,000,000 checks. Dou-
bling the grid would require 320,000,000 checks, which is no longer a trivial
calculation. We want an algorithm that can solve a puzzle of this size in a
fraction of a second (not counting disk I/O time), so we must consider an
alternative algorithm:

An alternative algo-
rithm searches
from each point in
the grid in each
direction for each
word length and
looks for the word
in the word list.

for each row R
for each column C
for each direction D
for each word length L
check if L chars starting at row R column C
in direction D form a word

figure 10.1
A sample word
search grid

0 1 2 3

this

0

wats

1

oahg

2

fgdt

3