------art_51657_8085079.1185932826325
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

Here is my solution: http://pastie.caboo.se/83905

This took a bit longer to finish than expected (apparently I need more
practice with these types of problems), but it was fun to put together and I
was pleased to write a fairly elegant solve method, once a framework was in
place. Anyway, this solution does work for partial puzzles (bonus 1), but is
fairly slow (no bonus 2).

Some example output:

>crossword_solver.rb linux.words.txt test_board.txt
C E L I A

H # U # C

A S C O T

N # K # E

T O Y E D

Here is a link to all of the files, if anyone is interested:
http://justin.ethier.googlepages.com/132_Crossword_Solver_JEthier.zip

Thanks,

Justin


On 7/27/07, Ruby Quiz <james / grayproductions.net> wrote:
>
> 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
>
>

------art_51657_8085079.1185932826325--