http://blog.ishotihadus.com/?p=133

makedic.rb

i = 0

$stdout.sync = true
arr_before = 'ぁぃぅぇぉヵヶっゃゅょゎ'
arr_after = 'あいうえおかけつやゆよわ'

IO.foreach('word_list.txt') do |l|
    next if l.length <= 2 # 改行文字を含むから
    str = ''
    l.strip.chars do |c|
        n = arr_before.index(c)
        if n
            str += arr_after[n]
        else
            str += c
        end
    end
    print "\r" + i.to_s + ": " + str + ('　' * (50 - str.length)) if i % 200 == 0

    File.open('dictionary/' + str.length.to_s + '.txt', 'a') do |file|
        file.puts str
    end
    i += 1
end

puts ''
puts '全 ' + i.to_s + ' 語'

solve.rb

# テーブルの定義

# ひらがなの重複を許すか
@allow_dup = false

first_list = ['と', 'き']
table =
[[2, 4, 1, 3, 4],
 [4, nil, 2, 4, nil],
 [2, 2, nil, 2, 5],
 [nil, 5, 3, nil, 1],
 [1, 3, 2, 5, 3]]

table.each do |l|
    l.each do |e|
        if e
            print e.to_s.rjust(2, ' ')
        else
            print 'XX'
        end
        print ' '
    end
    puts ''
end

# まずは縦と横の表をつくる

# 横
rows = []
table.each do |e|
    i = 0
    while i < e.count
        if e[i] != nil
            j = i
            while e[j] != nil
                j += 1
            end
            if j > i + 1
                rows += [e[i...j]]
            end
            i = j
        else
            i += 1
        end
    end
end

# 縦
cols = []
colcount = table[0].count
for i in 0...colcount
    j = 0
    while j < table.count
        if table[j][i] != nil
            k = j
            while table[k] != nil && table[k][i] != nil
                k += 1
            end
            if k > j + 1
                cols += [table[j...k].collect{|e| e[i]}]
            end
            j = k
        else
            j += 1
        end
    end
end

# すべての列
lines = rows + cols
puts "単語数: #{lines.count}"

def get_max_point_index(lines, list)
    max_p = 0
    max_i = 0
    for i in 0...lines.count
        l = lines[i]
        correct = true
        pnt = 0
        l.each do |e|
            if list[e - 1]
                pnt += 1
            else
                correct = false
                pnt += 0.3 if l.select{|f| f == e}.count > 1
            end
        end
        # 2文字はあまり参考にならない
        if l.count <= 2
            pnt *= 0.3
        end
        if !correct && max_p < pnt
            max_p = pnt
            max_i = i
        end
    end
    max_i
end

# 候補を得る部分はかなり上手にやらないといけないとは思っているんだ……
def get_candidate(line, list)
    arr = []
    word_length = line.count
    IO.foreach('dictionary/' + word_length.to_s + '.txt') do |d|
        # 辻褄が合うかどうかを判定
        tmplist = list.dup
        correct = true
        for i in 0...line.count
            e = line[i]
            if tmplist[e - 1]
                correct = correct && (tmplist[e-1] == d[i])
            else
                if list.any?{|e| e == d[i]} && !@allow_dup
                    correct = false
                else
                    tmplist[e - 1] = d[i]
                end
            end
        end
        if correct
            arr += [d.strip]
        end
    end
    arr
end

def foreach_any(str)
    IO.foreach('dictionary/' + str.length.to_s + '.txt') do |d|
        if d.strip == str
            return true
        end
    end
    false
end

@most_arr = []
@most_arr_count = 0

# search関数の定義
def search(lines, list)
    ans = nil

    arr_fulfill_count = list.select{|e| e != nil}.count
    if arr_fulfill_count > @most_arr_count
        @most_arr = list.dup
        @most_arr_count = arr_fulfill_count
    end

    correct = true
    lines.each do |l|
        l.each do |e|
            correct = correct && list[e - 1] != nil
        end
    end

    # すべて答えがそろっていればそのまま答えを返す
    if correct
        ans = list
    else
        # 各列の点数を計算して最も高い点数のインデックスを得る
        idx = get_max_point_index(lines, list)
        line = lines[idx]
        p line

        # 候補を探す
        cand_arr = get_candidate(line, list)
        p cand_arr

        cand_arr.each do |candidate|
            # puts candidate + ': '
            cand_list = list.dup
            def_arr = []
            for i in 0...line.count
                e = line[i]
                if !cand_list[e-1]
                    cand_list[e-1] = candidate[i]
                    def_arr += [e]
                end
            end

            # これによって埋まった場所を探して、それが辞書にあるかどうかを確かめる
            tmpcorrect = true
            lines.each do |l|
                if l.any?{|e| def_arr.any?{|f| f == e}}
                    thiscrr = true
                    l.each do |e|
                        thiscrr = thiscrr && cand_list[e - 1] != nil
                    end
                    if thiscrr
                        str = ''
                        l.each do |e|
                            str += cand_list[e - 1]
                        end
                        tmpcorrect = tmpcorrect && foreach_any(str)
                    end
                end
            end
            if tmpcorrect
                tmp_ans = search(lines, cand_list)
                if tmp_ans
                    ans = tmp_ans
                    break
                end
            end
        end
    end
    ans
end


@most_arr = first_list
@most_arr_count = first_list.select{|e| e != nil}.count
print '初期対応: '
p first_list
puts ''
before_time = Time.now
ans = search(lines, first_list)
after_time = Time.now

if ans
    p ans
    puts ''

    table.each do |l|
        l.each do |e|
            if e
                print ans[e - 1]
            else
                print '　'
            end
            print ' '
        end
        puts ''
    end
else
    puts '解答不明'
    p @most_arr
    puts ''
    print '不明行: '
    n = get_max_point_index(lines, @most_arr)
    p lines[n]
    puts ''
    table.each do |l|
        l.each do |e|
            if e
                if @most_arr[e - 1]
                    print @most_arr[e - 1]
                else
                    print e.to_s.rjust(2, ' ')
                end
            else
                print '　'
            end
            print ' '
        end
        puts ''
    end
end

puts ''
puts "経過時間: #{(after_time - before_time).to_i}秒"