## Word Search Solver

### May 26, 2009

Word search puzzles are a popular time-wasting pasttime. To redeem some of that lost time, we will write a program to search puzzles. For instance, given a problem like

```F Y Y H N R D R L J C I N U A A W A A H R N T K L P N E C I L F S A P E O G O T P N H P O L A N D```

and the list of words ITALY, HOLLAND, POLAND, SPAIN, FRANCE, JAPAN, TOGO, and PERU, you should find words at the following locations:

```ITALY row 5 column 2 up HOLLAND row 7 column 1 up right POLAND row 7 column 2 right SPAIN row 5 column 5 up FRANCE row 1 column 1 down JAPAN row 2 column 3 down right TOGO row 6 column 5 left PERU row 5 column 7 up```

Your task is to write a word search solver. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

### 8 Responses to “Word Search Solver”

1. […] Praxis – Word Search Solver By Remco Niemeijer Today’s Programming Praxis problem is about word search solvers. The provided solution is 77 lines, so […]

2. Remco Niemeijer said

import Data.List
import Data.Map (Map, fromList, member, keys, (!))
import Text.Printf

dirs :: [(String, (Int, Int) -> (Int, Int))]
dirs = zip [“down right”, “up right”, “right”, “down left”,
“up left”, “left”, “down”, “up”] \$
[\(x,y) -> (x+h, y+v) | h < - [1,-1,0], v <- [1,-1,0]] toGrid :: [[a]] -> Map (Int, Int) a
toGrid = fromList . concat .
zipWith (\y -> zipWith (\x c -> ((x,y), c)) [1..]) [1..]

found :: (Eq a, Ord k) => k -> (k -> k) -> Map k a -> [a] -> Bool
found pos dir g w = isPrefixOf w . map (g !) .
takeWhile (flip member g) \$ iterate dir pos

findWord :: Map (Int, Int) Char -> String -> String
findWord g w = head [printf “%s row %d column %d %s” w y x ds |
(x,y) <- keys g, (ds, dir) <- dirs, found (x,y) dir g w] puzzle :: [String] puzzle = ["FYYHNRD", "RLJCINU", "AAWAAHR", "NTKLPNE", "CILFSAP", "EOGOTPN", "HPOLAND"] main :: IO () main = mapM_ (putStrLn . findWord (toGrid puzzle)) \$ words "ITALY HOLLAND POLAND SPAIN FRANCE JAPAN TOGO PERU" [/sourcecode]

3. Rich Hrkins said

A Python RE-heavy solution:

#!/usr/bin/env python
“””
Do the word search, using standard input for the puzzle and the arguments
for words. For example if /tmp/x.txt is:

F Y Y H N R D
R L J C I N U
A A W A A H R
N T K L P N E
C I L F S A P
E O G O T P N
H P O L A N D

and the program is saved as /tmp/x.py, then (under UNIX) the solutions can
be generated using:

/tmp/x.py ITALY HOLLAND POLAND SPAIN FRANCE JAPAN TOGO PERU #

4. Here’s a python approach which puts each letter into a tuple with its row and column numbers, making it easy to retrieve the words’ locations after we have scrambled the grid looking for matches. No RE’s, just uses the “in” construct.

#!/usr/bin/python
# -*- coding: utf-8 -*-

puzzle=”’F Y Y H N R D
R L J C I N U
A A W A A H R
N T K L P N E
C I L F S A P
E O G O T P N
H P O L A N D
”’
clues = [‘ITALY’, ‘HOLLAND’, ‘POLAND’, ‘SPAIN’,
‘FRANCE’, ‘JAPAN’, ‘TOGO’, ‘PERU’]

puzzle = puzzle.replace(‘ ‘,”)
length = puzzle.index(‘\n’)
#Make a list of tuples containing each letter and its row and column
left = [(letter, divmod(index, length+1))
for index, letter in enumerate (puzzle)]
#Reorder the list to represent each reading direction
right = [i for i in reversed(left)]

down = []
for i in range(length):
for j in range(i, len(left), length+1):
down.append(left[j])
down.append(‘\n’)

up = [i for i in reversed(down)]

right_down =[]
for i in range(length):
for j in range(i, len(left), length):
right_down.append(left[j])
right_down.append(‘\n’)

left_up = [i for i in reversed(right_down)]

left_down = []
for i in range(length):
for j in range(i, len(left), length + 2):
left_down.append(left[j])
left_down.append(‘\n’)

right_up = [i for i in reversed(left_down)]

lines = {‘left’:left, ‘right’:right, ‘up’:up, ‘down’:down,
‘left down’:left_down, ‘left up’:left_up,
‘right down’:right_down, ‘right up’:right_up}

for word in clues:
for k,v in lines.items():
string = ”.join([i[0] for i in v])
if word in string:
loc = v[string.index(word)][1]
print word, ‘row’, loc[0]+1, ‘column’, loc[1]+1, k

5. Oops, all the indenting disappeared! I obviously need to work out how to post code properly here – sorry…

6. Another attempt to post the above code:

```#!/usr/bin/python
# -*- coding: utf-8 -*-

puzzle='''F Y Y H N R D
R L J C I N U
A A W A A H R
N T K L P N E
C I L F S A P
E O G O T P N
H P O L A N D
'''
clues = ['ITALY', 'HOLLAND', 'POLAND', 'SPAIN',
'FRANCE', 'JAPAN', 'TOGO', 'PERU']

puzzle = puzzle.replace(' ','')
length = puzzle.index('\n')
#Make a list of tuples containing each letter and its row and column
left = [(letter, divmod(index, length+1))
for  index, letter in enumerate (puzzle)]
#Reorder the list to represent each reading direction
right = [i for i in reversed(left)]

down = []
for i in range(length):
for j in range(i, len(left), length+1):
down.append(left[j])
down.append('\n')

up = [i for i in reversed(down)]

right_down =[]
for i in range(length):
for j in range(i, len(left), length):
right_down.append(left[j])
right_down.append('\n')

left_up = [i for i in reversed(right_down)]

left_down = []
for i in range(length):
for j in range(i, len(left), length + 2):
left_down.append(left[j])
left_down.append('\n')

right_up = [i for i in reversed(left_down)]

lines =  {'left':left, 'right':right,  'up':up, 'down':down,
'left down':left_down, 'left up':left_up,
'right down':right_down, 'right up':right_up}

for word in clues:
for k,v in lines.items():
string = ''.join([i[0] for i in v])
if word in string:
loc = v[string.index(word)][1]
print word, 'row', loc[0]+1, 'column', loc[1]+1, k
```
7. ```An improved (shorter, more efficient) version of the above:

#!/usr/bin/python
# -*- coding: utf-8 -*-

puzzle='''F Y Y H N R D
R L J C I N U
A A W A A H R
N T K L P N E
C I L F S A P
E O G O T P N
H P O L A N D
'''
clues = ['ITALY', 'HOLLAND', 'POLAND', 'SPAIN',
'FRANCE', 'JAPAN', 'TOGO', 'PERU']

puzzle = puzzle.replace(' ','')
length = puzzle.index('\n')+1
#Make a list of tuples containing each letter and its row and column
letters = [(letter, divmod(index, length))
for  index, letter in enumerate (puzzle)]
#Reorder the list to represent each reading direction,
#and add them all to a dictionary
lines = {}
offsets = {'down':0, 'right down':-1, 'left down':1}
for direction, offset in offsets.items():
lines[direction] = []
for i in range(length):
for j in range(i, len(letters), length + offset):
lines[direction].append(letters[j])
lines[direction].append('\n')
lines['left']  = letters
lines['right'] = [i for i in reversed(letters)]
lines['up'] = [i for i in reversed(lines['down'])]
lines['left up'] = [i for i in reversed(lines['right down'])]
lines['right up'] = [i for i in reversed(lines['left down'])]
#Make strings from the letters, find the words in them and retrieve
#their original locations
for direction, tup in lines.items():
string = ''.join([i[0] for i in tup])
for word in clues:
if word in string:
location = tup[string.index(word)][1]
print word, 'row', location[0]+1, 'column', location[1]+1, direction
```
8. Emily said

GIVE ME A WORD SEARCH SOLVER!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!