おもこん

おもこんは「思いつくままにコンピュターの話し」の省略形です

「ブラサガリ算」をコンピュータで解く

 芦ケ原伸之という有名なパズル作家をご存知だろうか。数々のパズル本を出していて、その一つに「超々難問数理パズル」という本がある。この本が出版されたのは2002年で、私が買ったのもおそらくその頃だと思う。購入して、いくつか解いてみたが、当時は仕事も忙しく、やがて書棚に置きっぱなしになってしまった。この本の裏表紙に「この一冊でたっぷり10年は楽しめます!」と書かれているが、私の場合は10年以上(本を開かなかったので)楽しまなかったことになる。退職して時間に余裕ができたので、あらためて取り組んでみた。タイトルの通り、かなり難しい。今回はその中から9番目の問題「ブラサガリ算」という問題について書きたいと思う。

 この問題は逆三角形に並べた数字で、隣り合う2数の差が下に来るという単純なルールが成り立つものを見つけるのである。例えば3個の数字(1,2,3の3つの数)で逆三角形をつくる場合は簡単で、下のような図になる。なお、答えは一種類ではない。

      2 3
       1

 次に6個の数字にすると少し難しくなるが、しばらく試行錯誤を繰り返せばできるだろう。これも答えは一通りではない。

     4 6 1
      2 5
       3

 さて、問題はこれを5段組15個の数字(1から15の整数)で三角形を作れ、というものだった。

  まず、手作業でやってみたがなかなかできない。大きな数、例えば15や14が上の方に来なければいけないということはわかったが、それでも場合が多くて答えが見つからなかった。それならコンピューターに計算をさせて全数テストをしてしまえ、ということになった。ところが、このプログラムを考えるのも結構難しかったのである。できあがったプログラムはここに記しておくので、興味のある方は、プログラムを走らせて答を見てほしい。

※ 以下の枠で囲まれた文は、最初に投稿したときのものである。その後、rubyのArray(配列)オブジェクトに標準でpermutationメソッドがあるのに気がついて、プログラムを書き直した。

 プログラムの中に、n個からr個をとってできる順列をひとつずつ取り出すというメソッドがある。具体的にはプログラムを見てもらいたいが、再起手続きとyield命令を使って、ひとつひとつの順列をブロックで処理できるようなメソッドになっている。この計算は一般的なものなので、すでにライブラリがあるのではないかと思う。もしこれをお読みの方で、そのようなライブラリーを知ってる方がいらっしゃったら、コメントで教えていただければ幸いです。

 プログラムを走らせると1秒ほどで答えが出る。答えは対象を除き、一通りである。ついでに6段の場合も試してみた。2分4秒かかって、条件を満たす並べ方が無いことが分かった。実は、パズル本の解答編にも6段には答えがないと書いてあった。

@n = 5
@max = @n*(@n+1)/2
@a = []
1.upto(@max) do |i|
  @a << i
end
@b = []
0.upto(@n-1) do |i|
  @b[i] = []
end
@c = []

def success?
  0.upto(@n-1) do |i|
    if @c[i] != true
      return false
    end
  end
  return true
end

def check x
  if @c[x] == true
    return false
  end
  @c[x] = true
end

def try
  @c = []
  0.upto(@n-1) do |i|
    unless @b[@n-1][i].instance_of? (Integer)
      raise "@b[#{@n-1}][#{i}] is not an integer.\n"
    end
    if @b[@n-1][i] < 1 || @b[@n-1][i] > @max
      raise "@b[#{@n-1}][#{i}]=#{@b[@n-1][i]} is too big or too small.\n"
    end
    if ! check(@b[@n-1][i])
      return false
    end
  end

  (@n-2).downto(0) do |i|
    0.upto(i) do |j|
      @b[i][j]=(@b[i+1][j+1]-@b[i+1][j]).abs
      if ! check(@b[i][j])
        return false
      end
    end
  end
  true
end

@a.permutation(@n) do |p|
  @b[@n-1] = p
  if try()
    (@n-1).downto (0) do |i|
      p @b[i]
    end
  end
end