# \[SOLUTION\]Crossword Solver (#132)

**URL:** <https://www.ruby-forum.com/t/solution-crossword-solver-132/110888>\
**Category:** Ruby\
**Created:** [July 31, 2007, 7:23pm UTC](https://www.ruby-forum.com/t/solution-crossword-solver-132/110888 "2007-07-31T19:23:19Z")\
**Posts on this page:** 1\
**Page:** 1

<div class="post-metadata">

**Author:** ![jameskelly](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/3ab097/32.png) [@jameskelly](https://www.ruby-forum.com/u/jameskelly)\
**Post date:** [July 31, 2007, 7:23pm UTC](https://www.ruby-forum.com/t/solution-crossword-solver-132/110888/1 "2007-07-31T19:23:19Z")

</div>

Sorry for the delay; ruby-talk-ctl suddenly decided to stop working for  
me.

This is another depth-first recursive search. Dictionary should be saved  
in wordlist.txt. It implements the first bonus, but not the second.

$template =\<\<EOL  
\_ \_ \_ \_ # \_ \_ \_ \_ \_ \_ \_ \_ \_ # \_ \_ \_ \_

\_ # \_ # \_ # \_ # \_ # \_ # \_ # \_ # \_ # \_

\_ \_ \_ \_ \_ \_ \_ \_ \_ # \_ \_ \_ \_ \_ \_ \_ \_ \_

\_ # \_ # \_ # \_ # \_ \_ \_ # \_ # \_ # \_ # \_

# \_ \_ \_ \_ # \_ # \_ # \_ # \_ # \_ \_ \_ \_

\_ # \_ # # # \_ \_ \_ \_ \_ \_ \_ # # # \_ # \_

\_ \_ \_ \_ \_ \_ # # \_ # \_ # # \_ \_ \_ \_ \_ \_

\_ # \_ # # \_ # \_ \_ \_ \_ \_ # \_ # # \_ # \_

\_ \_ \_ \_ \_ \_ \_ \_ # \_ # \_ \_ \_ \_ \_ \_ \_ \_

\_ # # \_ # \_ # \_ \_ \_ \_ \_ # \_ # \_ # # \_

\_ \_ \_ \_ \_ \_ \_ \_ # \_ # \_ \_ \_ \_ \_ \_ \_ \_

\_ # \_ # # \_ # \_ \_ \_ \_ \_ # \_ # # \_ # \_

\_ \_ \_ \_ \_ \_ # # \_ # \_ # # \_ \_ \_ \_ \_ \_

\_ # \_ # # # \_ \_ \_ \_ \_ \_ \_ # # # \_ # \_

# \_ \_ \_ \_ # \_ # \_ # \_ # \_ # \_ \_ \_ \_

\_ # \_ # \_ # \_ # \_ \_ \_ # \_ # \_ # \_ # \_

\_ \_ \_ \_ \_ \_ \_ \_ \_ # \_ \_ \_ \_ \_ \_ \_ \_ \_

\_ # \_ # \_ # \_ # \_ # \_ # \_ # \_ # \_ # \_

\_ \_ \_ \_ # \_ \_ \_ \_ \_ \_ \_ \_ \_ # \_ \_ \_ \_  
EOL

$dict = File.open(“wordlist.txt”){|f|f.read.upcase.split(/\n/)}

class Array  
###This version only works for down and left-to-right, but  
###for this quiz I don’t care.  
###Also not really a line if not at a 0, -45, or -90 degree angle;  
again, it doesn’t matter  
def each\_in\_line(y1,x1,y2,x2, &block)  
until x1==x2 and y1==y2  
block.call \*([self[y1][x1],y1,x1][0…block.arity])  
x1 += 1 unless x1==x2  
y1 += 1 unless y1==y2  
end  
end

def deep\_dup  
self.dup.map do |el|  
if el.is\_a? Array  
el.deep\_dup  
else  
el.dup  
end  
end  
end  
end

###Assumes crossword is rectangular  
###Returns an array of arrays, each containing an array with the start  
and end y and x  
###of a section of the crossword to be filled  
def word\_queue(crossword)  
queue = []  
crossword.each\_with\_index do |row, y|  
#"|" is just a spacer; preserving hashes eases computing x index  
words = row.join.gsub(’#’,’|#|’).squeeze(’|’).split(’|’)  
words.each\_with\_index do |word, n|  
next if word.length == 1  
next unless word.include? ‘\_’ #For EC 1  
queue \<\<  
[[y,words[0…n].join.length],[y,words[0…n].join.length]]  
end  
end

crossword[0].each\_index do |x|  
words = crossword.map{|row|row[x]}.  
join.gsub(’#’,’|#|’).squeeze(’|’).split(’|’)  
words.each\_with\_index do |word, n|  
next if word.length == 1  
next unless word.include? ‘\_’ #For EC 1  
queue \<\< [[words[0…n].join.length,  
x],[words[0…n].join.length,x]]  
end  
end  
queue  
end

def crossword\_solution(crossword, queue=word\_queue(crossword))  
return crossword if queue.empty?  
word\_coords = queue.first  
word\_space = “”  
crossword.each\_in\_line(\*word\_coords.flatten) {|c|word\_space \<\< c}  
regex = Regexp.new("^%s$" % word\_space.gsub(’\_’,’\w’))  
possible\_words = $dict.select{|w| w =~ regex}.sort\_by{rand}  
until possible\_words.empty?  
crossword\_copy = crossword.deep\_dup  
word\_arr = possible\_words.shift.split(//)  
crossword\_copy.each\_in\_line(\*word\_coords.flatten) do |el,y,x|  
crossword\_copy[y][x] = word\_arr.shift  
end  
solved=crossword\_solution(crossword\_copy,queue-[word\_coords])  
return solved if solved  
end  
nil  
end

puts crossword\_solution($template.chomp.gsub(’ ‘,’’).  
gsub("\n\n","\n").split(/\n/).map{|s|s.split(//)}).  
map{|r|r.join}.join("\n").tr(’#’,’ ')