From: Ruby Quiz <james@...>
Date: 2007-07-27T22:10:09+09:00
Subject: [QUIZ] Crossword Solver (#132)

The three rules of Ruby Quiz:

1.  Please do not post any solutions or spoiler discussion for this quiz until
48 hours have passed from the time on this message.

2.  Support Ruby Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3.  Enjoy!

Suggestion:  A [QUIZ] in the subject of emails about the problem helps everyone
on Ruby Talk follow the discussion.  Please reply to the original quiz message,
if you can.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

by Eugene Kalenkovich

Write a Ruby crossword solver.  Randomly fill a crossword template with words
from a dictionary. Use any dictionary you want (/usr/share/dict/words, text of
pickaxe, etc.).

Template is provided in a file formatted very similarly to one in quiz #10
(http://www.rubyquiz.com/quiz10.html), with "X" substituted with "#". Simple
template example:

	 _ _ _ _ _
	 
	 _ # _ # _
	 
	 _ _ _ _ _
	 
	 _ # _ # _
	 
	 _ _ _ _ _

Format output any way you want, just make it readable. Each run of the program
with big enough dictionary should give a different solution. Example results for
a simple template:

	 F U G U E
	 
	 U   U   R
	 
	 D E I G N
	 
	 G   D   S
	 
	 E J E C T
	 
	  
	 
	 R E S T S
	 
	 I   K   T
	 
	 N I E C E
	 
	 D   W   E
	 
	 S U S A N

Bonus 1 (simple). Allow partially pre-filled templates:

	 # # _ # # # # M
	 
	 _ _ _ _ _ _ # A
	 
	 # # _ # # _ # T
	 
	 R U B Y Q U I Z
	 
	 U # _ # # _ # #
	 
	 B # _ _ _ _ _ _
	 
	 Y # # # # _ # #

One of result variants:

	     U         M
	 
	 P A S C A L   A
	 
	     A     O   T
	 
	 R U B Y Q U I Z
	 
	 U   L     N
	 
	 B   Y E A G E R
	 
	 Y         E

Bonus 2: Avoid combinatorial explosion. Fill a big template within reasonable
time:

	 _ _ _ _ # _ _ _ _ _ _ _ _ _ # _ _ _ _
	 
	 _ # _ # _ # _ # _ # _ # _ # _ # _ # _
	 
	 _ _ _ _ _ _ _ _ _ # _ _ _ _ _ _ _ _ _
	 
	 _ # _ # _ # _ # _ _ _ # _ # _ # _ # _
	 
	 # _ _ _ _ # _ # _ # _ # _ # _ _ _ _ #
	 
	 _ # _ # # # _ _ _ _ _ _ _ # # # _ # _
	 
	 _ _ _ _ _ _ # # _ # _ # # _ _ _ _ _ _
	 
	 _ # _ # # _ # _ _ _ _ _ # _ # # _ # _
	 
	 _ _ _ _ _ _ _ _ # _ # _ _ _ _ _ _ _ _
	 
	 _ # # _ # _ # _ _ _ _ _ # _ # _ # # _
	 
	 _ _ _ _ _ _ _ _ # _ # _ _ _ _ _ _ _ _
	 
	 _ # _ # # _ # _ _ _ _ _ # _ # # _ # _
	 
	 _ _ _ _ _ _ # # _ # _ # # _ _ _ _ _ _
	 
	 _ # _ # # # _ _ _ _ _ _ _ # # # _ # _
	 
	 # _ _ _ _ # _ # _ # _ # _ # _ _ _ _ #
	 
	 _ # _ # _ # _ # _ _ _ # _ # _ # _ # _
	 
	 _ _ _ _ _ _ _ _ _ # _ _ _ _ _ _ _ _ _
	 
	 _ # _ # _ # _ # _ # _ # _ # _ # _ # _
	 
	 _ _ _ _ # _ _ _ _ _ _ _ _ _ # _ _ _ _
	 
	 
	 
	 C H A O   L E N I E N T L Y   C O I L
	 
	 Y   V   L   M   D   O   E   O   K   A
	 
	 S H A R E A B L E   O E D I P A L L Y
	 
	 T   I   A   R   N U N   G   E   A   S
	 
	   F L I P   Y   T   T   E   C O H N
	 
	 I   A       O L I V I E R       O   I
	 
	 R E B U F F     F   M     A S H M A N
	 
	 R   L     A   B Y T E S   D     A   T
	 
	 I N E R T I A L   Y   I S S U A N C E
	 
	 T     U   R   A S P E N   O   D     N
	 
	 A L T E R E R S   E   U P R O O T E D
	 
	 T   O     S   E A S E S   B     O   I
	 
	 E X T A N T     B   N     S U N T A N
	 
	 S   T       U T R E C H T       A   G
	 
	   W E E P   N   A   L   R   D E L L
	 
	 P   R   U   T   M A O   U   A   L   M
	 
	 R E I N S E R T S   S O M E W H E R E
	 
	 O   N   H   U   O   E   A   N   R   A
	 
	 S A G S   B E R N A D I N E   U S E D