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

chapter 10

fun and games

I n this chapter we introduce three important algorithmic techniques and
show how to use them by implementing programs to solve two recreational
problems. The first problem is the word search puzzle and involves finding
words in a two-dimensional grid of characters. The second is optimal play in
the game of Tic-Tac-Toe.
In this chapter, we show

How to use the binary search algorithm to incorporate information
from unsuccessful searches and to solve large instances of a word
search problem in under 1 sec

n

How to use the alpha-beta pruning algorithm to speed up the recur-
sive algorithm presented in Section 7.7

n

How to use maps to increase the speed of the Tic-Tac-Toe algorithm

n

word search puzzles

10.1

The input to the word search puzzle problem is a two-dimensional array of
characters and a list of words, and the object is to find the words in the grid.
These words may be horizontal, vertical, or diagonal in any direction (for a
total of eight directions). As an example, the grid shown in Figure 10.1