From the 1996 UF ACM High School Programming Competition

Words, words, words

Cathy Chino loves coffee and word searches and absolutely despises sleep. One night (or possibly morning), she goes to her favorite 24-hour coffee shop with a book of word search puzzles. As soon as she gets her quintuple cup of espresso, she sits down and starts working on the one shown below. 
adaddonot
jliaredhi
xodrecord
egikauwao
siendwren
schemeyru
urcsramyt
sensezrgn
qdifftick
darkness scheme logic record dowry
inch ordo sussex gyre rear
...

In a haze induced by caffeine overdose and sleep deprivation, Cathy invents a new, easier type of word search (which makes perfect sense to her at the time). There are simply too many letters, so she decides that removing them could only simplify the puzzle.

Each time she finds a word, she takes all the letters out of the block. Soon, she finds that she cannot finish the puzzle. Some of the letters she needs have mysteriously disappeared! After looking all around the cafe for them, she remembers that she removed them from the puzzle. It suddenly appears interesting to find out just how many words she can remove before being blocked.

You, of course, are sitting at the next table with your trusty laptop, working diligently on some obscure little problem of your own. You need a break, so you offer to help, in exchange for a cup...

Problem Statement

Write a program which finds and removes strings from the block of characters above. The strings may appear forward, backward, up, down, or diagonally. Case does not matter, and the strings must not wrap around the block. When a string is removed, it is essentially replaced by blanks; the block remains a 9-by-9 block.

The input will consist of a sequence of words which are to be removed sequentially. The output will be either the first word which cannot be removed or a message indicating that all the words can be removed succesfully.

Notes

The input strings will occur at most once in the block of characters, although they may not appear at all (hey, it's late, you can come up with some pretty strange words).

At most six words will be given, all of which will fit within the block.

Examples

Enter words: wren derail rear tick
Cannot remove "rear".

Enter words: wren tick scheme
Sucessfully removed all words.

Grader's Test Data

Enter words: inch scheme ordo dowry
Cannot remove "scheme".

Enter words: gyre tick log sussex
Sucessfully removed all words.

Enter words: cram not thou dread dada logic
Cannot remove "thou".

Enter words: do not derail darkness
Cannot remove "darkness".

Enter words: tick keen
Sucessfully removed all words.

Enter words: random garbage
Cannot remove "random".

Solutions

C solution by Jason Riedy:
words.c