Crossword Solver (#132)

The three rules of Ruby Q.:

  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 Q. by submitting ideas as often as you can:

http://www.rubyquiz.com/

  1. Enjoy!

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

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

by Eugene K.

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
(Ruby Quiz - Crosswords (#10)), 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

Where can I get a file with the dictionary list? I would rather not
have to make my own.

On 7/27/07, Lloyd L. [email protected] wrote:

Where can I get a file with the dictionary list? I would rather not
have to make my own.

Posted via http://www.ruby-forum.com/.

If you’re on a mac, cat /usr/share/dict/words
Not sure where this is on linux, and no idea if something like this even
exists on windows.
Chris

Lloyd L. wrote:

Where can I get a file with the dictionary list? I would rather not
have to make my own.

/usr/share/dict/words on most any *NIX.

Where can I get a file with the dictionary list? I would
rather not have to make my own.

http://wordlist.sourceforge.net/ is a good resource, especially if
you’re on Windows and don’t have /usr/share/dict/words

  • donald

Ball, Donald A Jr (Library) wrote:

http://wordlist.sourceforge.net/ is a good resource, especially if
you’re on Windows and don’t have /usr/share/dict/words

Perfect! I got this, then chose the 6 files that were straight
wordlists. I wrote a program to read each file, change it to uppercase,
get rid of non alpha characters (which are no good for the puzzle), get
rid of all duplicates and write the new (sorted) list to a new file. It
has something like 108k words. nice!

Thanks all!

Hi,

Here’s my solution: Parked at Loopia

I’ve been inspired by Eric I.'s solution to the Verbal Arithmetic Ruby
Quiz
(Ruby Quiz - Verbal Arithmetic (#128)): divide the problem into steps, solve
each step in turn, backtrack if you’re stuck. Things are a lot simpler
though for this case than for the Verbal Arithmetic case, since there
are
less different types of step to consider for the Crossword case.

Some examples using /usr/share/dict/words as dictionary (1.cw, 2.cw
and 3.cwcontain the 3 given crossword definitions):

$ ./rq132_crosswordsolver_rafc.rb 1.cw
INNER
N#O#E
CRUMB
A#N#E
SISAL
(Solution found in 0.042307 seconds.)

$ ./rq132_crosswordsolver_rafc.rb 2.cw
##D####M
CLOSES#A
##U##T#T
RUBYQUIZ
U#L##C##
B#ERECTS
Y####O##
(Solution found in 0.029773 seconds.)

$ ./rq132_crosswordsolver_rafc.rb 3.cw
CLUE#OLIGOCENE#ODER
A#N#S#I#L#H#A#O#I#E
PARAMECIA#ENVISAGED
E#U#U#K#DIN#I#L#E#S
#SLOG#E#I#I#E#OHSA#
W#I###DOODLES###T#C
HYENAS##L#L##RETINA
O#S##E#SINEW#E##O#T
OUTREACH#A#INSIGNIA
S##E#L#ATOLL#O#I##L
HEADBAND#M#MALAGASY
I#M##N#ERICA#V##N#Z
NOUGAT##O#A##EXCITE
G#S###ESTELLA###M#S
#WINE#N#T#L#G#WAIF#
I#N#L#K#ELI#A#I#S#V
DIGESTION#POSTNATAL
E#L#A#D#E#E#S#E#I#A
SAYS#GUARDRAIL#SCAD
(Solution found in 0.575114 seconds.)

For this last case, the runtime is usually under a second, but I must
admit
that it can wildly fluctuate and sometimes takes minutes to find a
solution.

Regards,
Raf

Ruby Q. 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/ ).

== Overview

The problem is modelled as a matrix of cells where each cell can be
assigned a number representing the letters a…z and #. The letters are
converted to integers in order to use integer variables to represent
them. Similarly each word is converted to a base 26 number with the
converted letters as digits. Hence allowing the words to be represented
as integers as well.

The constraint that sequences of cells longer than one letter must form
words is then added by constraining that the linear combination of the
involved cells forming the corresponding base 26 number, with each
variable as one digit, must be equal to one of the words converted to a
number.

== Weaknesses

It has two major problems

  • The words converted to numbers have to fit in the range of an integer
    variable, which only allows words of up to 6 characters in my case. This
    can probably be helped by using multiple numbers to represent each word.
  • There’s no randomness in the exploration. Gecode itself does support
    custom branching (which would allow such randomness), but Gecode/R does
    not.

In some cases the exploration will take a long time. I’m unsure whether
it’s because of flaws in the model or because of the problem’s
difficulty.

== 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

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

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

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 accumelate 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

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

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)

END

Ruby Q. [email protected] writes:

by Eugene K.

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.).

A simple, stupid and not very efficient recursive depth-first

solver, written using regular expressions.

28jul2007 +chris+

Transpose a string

def flip(str)
str.split(“\n”).map { |s| s.split(//) }.transpose.map { |s| s.join
}.join(“\n”)
end

def wordlist(crossword)
sizes = ( crossword .scan(/[A-Z][A-Z]+/) +
flip(crossword).scan(/[A-Z]
[A-Z]+/)).
map { |w| w.size }.uniq - [1]

print “Gathering words… "
all_words = File.read(”/usr/share/dict/words").
split(“\n”). # save a chomp
reject! { |w| not sizes.include?(w.size) }.
map! { |w| w.upcase }
puts “found #{all_words.size}”

all_words
end

def solve(crossword, words=wordlist(crossword), flipped=false)

Is there a word to be filled?

if crossword =~ /([A-Z][A-Z]+)/
words.grep(Regexp.new(“\A#{$1.tr(‘_’, ‘.’)}\z”)).
sort_by { rand }. # faster results
each { |fit|
solve flip(crossword.sub(/[A-Z]
[A-Z]+/, fit)), words,
!flipped
}
elsif flip(crossword) =~ /([A-Z]*[A-Z]+)/
solve(flip(crossword), words, !flipped)
elsif crossword !~ /_/ # fully filled?
crossword = flip(crossword) if flipped
puts crossword
puts
end
end

def clean(crossword)
crossword.delete(" \t").gsub(/\n{2,3}/, “\n”)
end

Test data

cw = <<EOF


_ # _ # _


_ # _ # _


EOF

cw2 = <<EOF

# _ # # # # M

_ _ _ _ _ _ # A

# _ # # _ # T

R U B Y Q U I Z

U # _ # # _ # #

B # _ _ _ _ _ _

Y # # # # _ # #
EOF

Good luck with this one…

cw3 = <<EOF
_ _ _ _ # _ _ _ _ _ _ _ _ _ # _ _ _ _

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

_ _ _ _ # _ _ _ _ _ _ _ _ _ # _ _ _ _
EOF

solve(clean(cw2))

Here is my solution: Parked at Loopia

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:

Thanks,

Justin

On Jul 27, 8:10 am, Ruby Q. [email protected] wrote:

The three rules of Ruby Q.:

Here is my solution. :smiley:

http://pastie.caboo.se/83968

I think there is still a little bug in which search cycles, but it’s
highly improbable (got it once in ~50 runs) Will try to fix it.

“Ruby Q.” [email protected] wrote in message

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.).

My solution, slightly optimized for performance version of the code that
was
used originally to generate examples for this quiz:

class CrossTempl
def initialize(templ)
@tmpl=templ.collect { |line| line.split(//) }
@words=[]
@tmpl.each_index do |i|
@tmpl[i].each_with_index do |char, j|
if char!=‘#’
if (j==0||@tmpl[i][j-1]==‘#’) && !@tmpl[i][j+1].nil? &&
@tmpl[i][j+1]!=‘#’
@words << [i,j,0] if self.template(i,j,0).include?(‘‘)
end
if (i==0||@tmpl[i-1][j]==’#‘) && !@tmpl[i+1].nil? &&
@tmpl[i+1][j]!=’#’
@words << [i,j,1] if self.template(i,j,1).include?('
’)
end
end
end
end
@words.sort! {|a,b| a[0]+a[1]<=>b[0]+b[1]}
end

def template(i,j,dir)
str=‘’
chr=@tmpl[i][j]
while !chr.nil? && chr!=‘#’
str<<chr
i+=dir
j+=1-dir
break if @tmpl[i].nil?
chr=@tmpl[i][j]
end
str
end

def
ar=@words[idx]
return nil if ar.nil?
template(ar[0],ar[1],ar[2])
end

def []=(idx,word)
ar=@words[idx]
i=ar[0]; j=ar[1];
word.split(//).each do |chr|
@tmpl[i][j]=chr
i+=ar[2]
j+=1-ar[2]
end
end

def to_s
@tmpl.each do |line|
lstr=line.to_s
puts lstr.gsub(/#/,’ ').gsub(/(.)/) {"#{$&} "}
end
end

end

$words=[]
File.open(“/usr/share/dict/words”) {|f| f.readlines}.each do |word|
w=word.upcase.delete(“^A-Z”)
l=w.length
$words[l]||=[]
$words[l]<<w
end
$words.each {|ar| ar.uniq! if ar }

tfile=ARGV[0]
if tfile.nil?
STDERR.puts “please provide a template file”
exit 1
end

tmpl=File.read(tfile).split(/\n/).collect{|line|
line.gsub(/\s/,‘’).upcase}
$ct=CrossTempl.new(tmpl)

def findWord(i)
pattern=$ct[i]
return true if pattern.nil?
choices=$words[pattern.length].grep(/\A#{pattern.tr(“_”,
“.”)}\Z/).sort_by
{ rand }
until choices.empty?
guess=choices.pop
$ct[i]=guess
puts $ct
return true if findWord(i+1)
break if i>0 && rand(2)==1 # fighting incorrect word sorting
# by un-ballancing search
end
$ct[i]=pattern
return false
end

if findWord(0)
puts $ct
else
puts “O-ops”
end

Andreas L. wrote:

Ruby Q. 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