From: Andreas Launila <ruby-talk@...>
Date: 2008-04-24T17:47:49+09:00
Subject: Re: [QUIZ] Crossword Solver (#132)

Andreas Launila wrote:
> Ruby Quiz wrote:
>> 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.).
>>
> 
> This solution requires Gecode/R ( http://gecoder.rubyforge.org/ ).
> 

I thought I would update this solution to use the recently introduced
tuple constraints. The updated version no longer has a limitation on
word-lengths and seems to scale well with both the template size and
dictionary size.

The model is almost the same as before. Each square is represented by an
integer variable that can be assigned a number representing one of the
letters a..z and #. The difference is that a different type of
constraint is used to force sequences of cells, longer than one letter,
to form words. The model now uses tuple constraints, which each
constrain an enumeration of integer variables (e.g. letters that should
form words) to take the value of one of many tuples (e.g. all tuples
representing words of the correct length).

The code requires Gecode/R 0.8.1 to run, which can be installed, along
with the Gecode 2.1.1 dependency, using

  gem install gecoder-with-gecode


== Code

require 'enumerator'
require 'rubygems'
require 'gecoder'

# The alphabet used.
ALPHABET = ('a'..'z').to_a

# Describes an immutable dictionary which represents all contained words
# as an array of integers where each integer represents a letter. Each
# integer used is between 0 and ALPHABET.size - 1.
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
      # A regexp that matches strings not in our alphabet.
      not_in_alphabet = /[^#{ALPHABET.join}]/
      dict.each_line do |line|
        word = line.chomp.downcase
        # Only allow words that are in our alphabet.
        next if previous_word == word or not_in_alphabet.match(word)
        (@word_arrays[word.length] ||= []) <<
          self.class.s_to_i_array(word)
        previous_word = word
      end
    end
  end

  # Gets an enumeration containing all arrays of integers representing
  # word of the specified length.
  def words_of_size(n)
    @word_arrays[n] || []
  end

  # Converts a string to an array of integers (inverse
  # of #i_array_to_s ).
  def self.s_to_i_array(string)
    if @c_to_i_map.nil?
      @c_to_i_map =
        Hash[*ALPHABET.zip((0...ALPHABET.size).to_a).flatten]
    end
    @c_to_i_map.values_at *string.scan(/./)
  end

  # Converts an array of integers back to the corresponding string
  # (inverse of #s_to_i_array ).
  def self.i_array_to_s(int_array)
    if @i_to_c_map.nil?
      @i_to_c_map = ALPHABET
    end
    @i_to_c_map.values_at *int_array
  end
end

# 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 an integer variable with
    # domain -1...BASE where -1 signify # 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...ALPHABET.size)

    # 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_array(letter).first
        end
      end
    end

    # Add the constraint that sequences longer than one letter must form
    # 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 intersections first.
    branch_on @letters, :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_array_to_s([x]) }.join(' ')
    end
    output.join("\n\n").upcase.gsub('#', ' ')
  end

  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_array_to_s(int_array)
    if int_array == [-1]
      return '#'
    else
      Dictionary.i_array_to_s(int_array)
    end
  end

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

  # Constrains the specified variables to form a word contained in the
  # dictionary.
  def must_form_word(letters)
    words_of_right_size = @dictionary.words_of_size(letters.size)
    if words_of_right_size.empty?
      raise RuntimeError, "There are no words of size #{letters.size}."
    end
    # Add the tuple constraint. Use propagation kind :memory if you run
    # out of memory.
    wrap_enum(letters).must_be.in words_of_right_size, :kind => :speed
  end
end

puts 'Reading the dictionary'
dictionary = Dictionary.new(ARGV.shift || '/usr/share/dict/words')
puts '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)

__END__

-- 
Andreas Launila