真ん中が「く」の平仮名三文字の言葉を「田」の形に並べるには？

Question

まくつくり
く＿く＿く
らくばくち
く＿く＿く
どくふくろ
↑
魔窟、旁、落馬、博打、読譜、袋、
枕、筑波、陸地、楽土、幕府、築炉

のように、
真ん中が「く」の平仮名三文字の言葉を「田」の形に並べる
（ただし、「く」で繋がれる文字は互いに異なるものとする。）
にはどうすればよいでしょうか？

以下のコードは、
皆様が回答されるうえで何か役に立つかもしれないので
載せておきます。

# -*- coding: cp932 -*-
words = [
'あくび', 'あくま',
'いくじ', 'いくら',
'えくぼ',
'おくて', 'おくば',
'かくご', 'かくさ', 'がくし', 'かくほ', 'かくり', 
'ごくい', 'こくし',
'さくが', 'さくし', 'さくら', 'ざくろ',
'しくみ',
'すくい',
'そくい',
'たくじ', 'たくち',
'ちくま', 'ちくろ', 'ちくわ',
'つくし', 'つくば', 'つくり',
'てくだ',
'とくぎ', 'とくし', 'どくふ', 'どくろ',
'はくい', 'はくし', 'ばくし', 'ばくち', 'ばくふ', 'ばくろ',
'びくに',
'ふくい', 'ふくし', 'ふくつ', 'ふくろ',
'ぼくし', 'ほくろ',
'まくつ', 'まくら',
'もくじ', 'もくず',
'やくみ', 'やくめ',
'らくだ', 'らくど', 'らくば',
'りくち'
]

ary = ['ち', 'つ', 'ど', 'ば', 'ふ', 'ま', 'ら', 'り', 'ろ']

ary.permutation(9){|a|
  i = 0
  while (words.include?(a[i] + 'く' + a[i + 1]) || i % 3 == 2) && i < 7
    i += 1
  end
  if words.include?(a[i] + 'く' + a[i + 1])
    j = 0
    while words.include?(a[j] + 'く' + a[j + 3]) && j < 5
      j += 1
    end
    if words.include?(a[j] + 'く' + a[j + 3])
      (0..2).each{|k|
        puts a[3 * k] + 'く' + a[3 * k + 1] + 'く' + a[3 * k + 2]
        puts 'く く く' if k < 2
      }
      puts ''
    end
  end
}

Answer 1

予め各単語の末尾に接続できる単語は求めておいて、
縦の制約は都度満たしているかどうか判断する方式にしました。

#coding: Windows-31J
words = [
'あくび', 'あくま',
'いくじ', 'いくら',
'えくぼ',
'おくて', 'おくば',
'かくご', 'かくさ', 'がくし', 'かくほ', 'かくり', 
'ごくい', 'こくし',
'さくが', 'さくし', 'さくら', 'ざくろ',
'しくみ',
'すくい',
'そくい',
'たくじ', 'たくち',
'ちくま', 'ちくろ', 'ちくわ',
'つくし', 'つくば', 'つくり',
'てくだ',
'とくぎ', 'とくし', 'どくふ', 'どくろ',
'はくい', 'はくし', 'ばくし', 'ばくち', 'ばくふ', 'ばくろ',
'びくに',
'ふくい', 'ふくし', 'ふくつ', 'ふくろ',
'ぼくし', 'ほくろ',
'まくつ', 'まくら',
'もくじ', 'もくず',
'やくみ', 'やくめ',
'らくだ', 'らくど', 'らくば',
'りくち'
]

def gen_connect_info(words)
  connect_info = {}
  
  words.each do |word|
    connect_info[word] = []
    words.each do |w|
      if word[-1] == w[0] && word != w
        connect_info[word] << w
      end
    end
  end
  
  connect_info
end

def print_answer(words)
  puts words.each_slice(2).map{|w1, w2|
    w1 + w2[-2 .. -1]
  }.join("\nく く く\n")
  
  puts
end

def unused_list(words, used)
  words.select{|e| !used.include?(e)}
end

def check_exists_and_unused(w, connect_info, used)
  connect_info[w] && !used.include?(w)
end

def search_pattern(i, max_size, connect_info, acc=[], used = [])
  if i >= max_size
    print_answer(acc)
  else
    words = unused_list(connect_info.keys, used)
    words.each do |w|
      unused_list(connect_info[w], used).each do |w2|
        prev1, prev2 = acc[-2 .. -1]
        if prev1
          v1 = prev1[0] + "く" + w[0]
          v2 = prev1[-1] + "く" + w[-1]
          v3 = prev2[-1] + "く" + w2[-1]
          if check_exists_and_unused(v1, connect_info, used) &&
            check_exists_and_unused(v2, connect_info, used) &&
            check_exists_and_unused(v3, connect_info, used) &&
            search_pattern(i + 1, max_size,connect_info, acc + [w, w2], used + [w, w2, v1, v2, v3])
          end
        else
          search_pattern(i + 1, max_size, connect_info, acc + [w, w2], used + [w, w2])
        end
      end
    end
  end
end
 
connect_info = gen_connect_info(words)
#p connect_info
search_pattern(0, 3, connect_info)