# Crossword Solver (#132)

**URL:** <https://www.ruby-forum.com/t/crossword-solver-132/111099>\
**Category:** Ruby\
**Created:** [August 2, 2007, 5:08pm UTC](https://www.ruby-forum.com/t/crossword-solver-132/111099 "2007-08-02T17:08:24Z")\
**Posts on this page:** 1\
**Page:** 1

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [August 2, 2007, 5:08pm UTC](https://www.ruby-forum.com/t/crossword-solver-132/111099/1 "2007-08-02T17:08:24Z")

</div>

Many of these solutions got pretty sluggish when run on large  
crosswords. The  
reason is simple: the search space for this problem is quite large.  
You have  
to try a significant number of words in each position before you will  
find a  
good fit for the board.

The good news is that this summer Google has paid to bring a very  
powerful  
search tool to Ruby. I’ve been lucky enough to have a ring-side seat  
for this  
process and now I want to show you a little about this new tool.

You’ve probably seen Andreas L. solving a fair number of the recent  
quizzes  
using his Gecode/R library. Gecode/R is a wrapper over the C Gecode  
library for  
constraint programming. Constraint programming is a technique for  
describing  
problems in a way that a tool like Gecode can then use to search the  
solution  
space and find answers for you. Gecode is a very smart little searcher  
though  
and will heavily prune the search space based on your constraints. This  
leads  
to some mighty quick results, as you can see:

$ time ruby solve\_crossword.rb /path/to/scowl-6/final/english-words.20  
\< /path/to/test\_board.txt  
Reading the dictionary…  
Please enter the template (end with ^D)  
Building the model…  
Searching for a solution…  
A B I D E

N C A

G H O S T

E N E

L A S E R

real 0m0.430s  
user 0m0.360s  
sys 0m0.068s

Let’s have a look at Andreas’s code to see how it sets things up for  
Gecode.  
Here’s the start of the code:

require ‘enumerator’  
require ‘rubygems’  
require ‘gecoder’

# The base we use when converting words to and from numbers.

BASE = (‘a’…‘z’).to\_a.size

# The offset of characters compared to digits in word-numbers.

OFFSET = ‘a’[0]

# The range of integers that we allow converted words to be in. We are

# only using the unsigned half, we could use both halves, but it would

# complicate things without giving a larger allowed word length.

ALLOWED\_INT\_RANGE = 0…Gecode::Raw::Limits::Int::INT\_MAX

# The maximum length of a word allowed.

MAX\_WORD\_LENGTH = (Math.log(ALLOWED\_INT\_RANGE.last) /  
Math.log(BASE)).floor

# …

You can see that Andreas loads Enumerator and Gecode/R here as well as  
setting  
up some constants. The constants relate to how this code will model  
words in  
the database. The plan here is to represent words as numbers made up of  
base 26  
digits which represent letters of the alphabet. This will allow Andreas  
to use  
Gecode’s integer variables to model the problem. The downside is that  
word size  
will be limited by the maximum size of an integer and thus this solution  
has a  
weakness in that it can’t be used to solve the larger puzzles.

You can see this conversion from numbers to words in the Dictionary  
class:

# …

# Describes an immutable dictionary which represents all contained

words

# as numbers of base BASE where each digit is the corresponding letter

# itself converted to a number of base BASE.

class Dictionary  
# Creates a dictionary from the contents of the specified dictionary  
# file which is assumed to contain one word per line and be sorted.  
def initialize(dictionary\_location)  
@word\_arrays = []  
File.open(dictionary\_location) do |dict|  
previous\_word = nil  
dict.each\_line do |line|  
word = line.chomp.downcase  
# Only allow words that only contain the characters a-z and  
are  
# short enough.  
next if previous\_word == word or word.size \> MAX\_WORD\_LENGTH  
or  
word =~ /[^a-z]/  
(@word\_arrays[word.length] ||= []) \<\< self.class.s\_to\_i(word)  
previous\_word = word  
end  
end  
end

```
# Gets an enumeration containing all numbers representing word of 

```

the  
# specified length.  
def words\_of\_size(n)  
@word\_arrays[n] || []  
end

```
# Converts a string to a number of base BASE (inverse of #i_to_s ).
def self.s_to_i(string)
  string.downcase.unpack('C*').map{ |x| x - OFFSET }.to_number(BASE)
end

# Converts a number of base BASE back to the corresponding string
# (inverse of #s_to_i ).
def self.i_to_s(int)
  res = []
  loop do
    digit = int % BASE
    res << digit
    int /= BASE
    break if int.zero?
  end
  res.reverse.map{ |x| x + OFFSET }.pack('C*')
end

```

end

# …

We’ve already talked about the number representation which is the  
majority of  
the code here. Do have a look at initialize() and words\_of\_size()  
though, to  
see how words are being stored. An Array is created where indices  
represent  
word lengths and the values at those indices are nested Arrays of words  
with  
that length. This makes getting a list of words that could work in a  
given slot  
of the puzzle easy and fast.

The s\_to\_i() method above relies on a helper method added to Array,  
which is  
simply this:

class Array  
# Computes a number of the specified base using the array’s elements  
# as digits.  
def to\_number(base = 10)  
inject{ |result, variable| variable + result \* base }  
end  
end

Again, this is just another piece of the conversion I explained earlier.

With a Dictionary created, it’s time to model the problem in Gecode  
constraints:

# Models the solution to a partially completed crossword.

class Crossword \< Gecode::Model  
# The template should take the format described in RubyQuiz #132 .  
The  
# words used are selected from the specified dictionary.  
def initialize(template, dictionary)  
@dictionary = dictionary

```
  # Break down the template and create a corresponding square 

```

matrix.  
# We let each square be represented by integer variable with  
domain  
# -1…BASE where -1 signifies # and the rest signify letters.  
squares = template.split(/\n\s\*\n/).map!{ |line| line.split(’ ') }  
@letters = int\_var\_matrix(squares.size, squares.first.size,  
-1…BASE)

```
  # Do an initial pass, filling in the prefilled squares.
  squares.each_with_index do |row, i|
    row.each_with_index do |letter, j|
      unless letter == '_'
        # Prefilled letter.
        @letters[i,j].must == self.class.s_to_i(letter)
      end
    end
  end

  # Add the constraint that sequences longer than one letter must 

```

form  
# words. @words will accumulate all word variables created.  
@words = []  
# Left to right pass.  
left\_to\_right\_pass(squares, @letters)  
# Top to bottom pass.  
left\_to\_right\_pass(squares.transpose, @letters.transpose)

```
  branch_on wrap_enum(@words), :variable => :largest_degree,
    :value => :min
end

# Displays the solved crossword in the same format as shown in the
# quiz examples.
def to_s
  output = []
  @letters.values.each_slice(@letters.column_size) do |row|
    output << row.map{ |x| self.class.i_to_s(x) }.join(' ')
  end
  output.join("\n\n").upcase.gsub('#', ' ')
end

# ...

```

After storing the dictionary, this code breaks the crossword template  
down into  
an integer matrix created using the Gecode/R helper method  
int\_var\_matrix().  
This will be our puzzle of words Gecode is expected to fill in.

The next two sections of the initialize() method build up the  
constraints.  
These are the rules that must be satisfied when we have found a correct  
solution.

The first of these chunks of code sets rules for any letters that were  
given to  
us in the template. This code tells Gecode that the number in that  
position of  
the matrix must equal the value of the provided letter. Take a good  
look at  
this RSpec like syntax because Andreas has spent a considerable effort  
on making  
it easy to express your constraints in a natural syntax and I hope you  
will  
agree with me that the end result is quite nice.

The other chunk of constraints are defined using a helper method we will  
examine  
in just a moment. The result of this code though is to ensure that the  
numbers  
selected represent letters that form actual words.

The final step in describing the problem to Gecode is to choose a  
branching  
strategy. This tells Gecode which variables it will need to make  
guesses about  
in order to find a solution as well as selecting a heuristic to use when  
guesses  
must be made. In this case, words will be selected based on how much of  
the  
overall puzzle they affect, hopefully ruling out large sections of the  
search  
space quickly.

The problem model we just examined is pretty much always how constraint  
programming goes. You just need to remember the three steps: create  
some  
variables for Gecode to fill in, define the rules for the values you  
want Gecode  
to find, and select a strategy for Gecode to use in solving the problem.

The to\_s() method above just creates the output used in the quiz  
examples for  
display to the user.

Let’s have a look at the helper methods used in the model definition  
now:

# …

```
private

# Parses the template from left to right, line for line, 

```

constraining  
# sequences of two or more subsequent squares to form a word in the  
# dictionary.  
def left\_to\_right\_pass(template, variables)  
template.each\_with\_index do |row, i|  
letters = []  
row.each\_with\_index do |letter, j|  
if letter == ‘#’  
must\_form\_word(letters) if letters.size \> 1  
letters = []  
else  
letters \<\< variables[i,j]  
end  
end  
must\_form\_word(letters) if letters.size \> 1  
end  
end

```
# Converts a word from integer form to string form, including the #.
def self.i_to_s(int)
  if int == -1
    return '#'
  else
    Dictionary.i_to_s(int)
  end
end

# Converts a word from string form to integer form, including the #.
def self.s_to_i(string)
  if string == '#'
    return -1
  else
    Dictionary.s_to_i(string)
  end
end

# Constrains the specified variables to form a word contained in the
# dictionary.
def must_form_word(letter_vars)
  raise 'The word is too long.' if letter_vars.size > 

```

MAX\_WORD\_LENGTH  
# Create a variable for the word with the dictionary’s words as  
# domain and add the constraint.  
word = int\_var @dictionary.words\_of\_size(letter\_vars.size)  
letter\_vars.to\_number(BASE).must == word  
@words \<\< word  
end  
end

# …

The i\_to\_s() and s\_to\_i() methods here are mostly just wrappers over the  
Dictionary counterparts we examined earlier. The real interest is the  
other two  
methods that together define the word constraints.

First, left\_to\_right\_pass() is used to walk the puzzle looking for runs  
of two  
or more letters that will need to become words in the Dictionary. Each  
time it  
finds one, a hand-off is made to must\_form\_word(), which builds the  
actual  
constraint.

With the problem modeled, it takes just a touch more code to turn this  
into a  
full solution:

# …

puts ‘Reading the dictionary…’  
dictionary = Dictionary.new(ARGV.shift || ‘/usr/share/dict/words’)  
puts ‘Please enter the template (end with ^D)’  
template = ‘’  
loop do  
line = $stdin.gets  
break if line.nil?  
template \<\< line  
end  
puts ‘Building the model…’  
model = Crossword.new(template, dictionary)  
puts ‘Searching for a solution…’  
puts((model.solve! || ‘Failed’).to\_s)

You can see that this application code is just reading in the dictionary  
and  
template, then constructing a model and pulling a solution with the  
solve!()  
method. That’s all it really takes to get answers after describing your  
problem  
to Gecode.

If you want to continue exploring Andreas’s Gecode/R wrapper, drop by  
the Web  
site which has links to many useful resources:

[http://gecoder.rubyforge.org/](http://gecoder.rubyforge.org/)

My thanks to all who put a good deal of effort into a hard search  
problem.

Tomorrow we will take another peek at our dictionary, this time to see  
what  
numbers are hiding in there…