Avendia19
English

日記 (2018 年 5 月 15 日)

大学院の院生室の棚に、 誰が置いていったのか知りませんがこんなパズルが置いてありました。

まあ見れば分かると思いますが、 小さな立方体がいくつか繋がっている 6 個のピースをうまく組み合わせて、 3 × 3 × 3 の大きな立方体を作るパズルです。 私がこのパズルを発見したときはバラバラの状態で、 以後事あるごとにこのパズルに挑戦していたんですが、 どうもうまくいきませんでした。 挙句の果てには、 これは絶対に解けないように設計されていて、 「こういうのが置いてあると立方体状に綺麗に組み上げたくなる」 という人間心理を逆手にとったおもちゃなんじゃないか、 と考えました。 なるほど、 それなら解けないことを証明してやる!! ・・・とまあそういう意気込みで、 コンピュータに解を探索させて解けないことを証明することにしました。

さて、 まずは 6 個のピースをデータ化する必要があります。 その場にいた私の友人が 「ピースの各小立方体の位置を 3 次元ベクトルで保持すれば回転が行列をかけるだけでできる」 と助言してくれたので、 そうすることにします。 幸い、 Ruby には行列やベクトルを扱えるライブラリが標準で入っているので、 使ってみましょう。

まず、 行列を使うためにライブラリを読み込みます。

require 'matrix'

6 個のピースを、 そのピースを構成する小立方体の座標の配列で保持します。 最終的に 3 × 3 × 3 の大きな立方体になるはずなので、 座標の値は -1, 0, 1 の 3 種類としました。

pieces = [
  [Vector[0, -1, -1], Vector[-1, 0, -1], Vector[0, 0, -1], Vector[0, -1, 0], Vector[1, -1, 0]],
  [Vector[-1, -1, -1], Vector[0, -1, -1], Vector[0, 0, -1], Vector[0, 0, 0]],
  [Vector[-1, -1, -1], Vector[0, -1, -1], Vector[1, -1, -1], Vector[-1, 0, -1], Vector[-1, 0, 0]],
  [Vector[-1, -1, -1], Vector[0, -1, -1], Vector[1, -1, -1], Vector[-1, 0, -1], Vector[0, -1, 0]],
  [Vector[-1, -1, -1], Vector[0, -1, -1], Vector[-1, 0, -1], Vector[-1, 0, 0]],
  [Vector[-1, -1, -1], Vector[0, -1, -1], Vector[1, -1, -1], Vector[-1, 0, -1]]
]

ピースの回転は、 そのピースを構成する小立方体の座標それぞれに適切な回転行列を左からかけることで行います。 ピースに適当に 「表面」 を定めると、 その表面の向きが 6 通り (上, 下, 右, 左, 前, 後ろ) あり、 各向きに対して表面の回転の仕方が 4 通り (0°, 90°, 180°, 270°) あるので、 考えられるピースの回転は 24 通りあります。 このそれぞれの回転に対して、 それを実現する回転行列を求める必要があります。

ということで、 まずは各軸の周りで反時計回りに 90° 回転させる行列を用意します。

BASIC_ROTATIONS = {
  :x => Matrix[  # x 軸周りの回転
    [1, 0, 0],
    [0, 0, -1],
    [0, 1, 0]
  ],
  :y => Matrix[  # y 軸周りの回転
    [0, 0, 1],
    [0, 1, 0],
    [-1, 0, 0]
  ],
  :z => Matrix[  # z 軸周りの回転
    [0, -1, 0],
    [1, 0, 0],
    [0, 0, 1]
  ]
}

ピースの 24 通りの回転は全てこの 90° 回転の組み合わせで実現できます。 具体的には以下の通りです。

これに従って、 24 個の回転行列を計算します。 後で定義するメソッドの中で使うので、 グローバルな定数 ROTATIONS にまとめておきます。

ROTATIONS = []
(0..3).each do |i|
  power = BASIC_ROTATIONS[:z] ** i
  ROTATIONS << power
  ROTATIONS << power * (BASIC_ROTATIONS[:x] ** 2)
end
(0..3).each do |i|
  power = BASIC_ROTATIONS[:y] ** i
  ROTATIONS << power * BASIC_ROTATIONS[:x]
  ROTATIONS << power * (BASIC_ROTATIONS[:x] ** 3)
end
(0..3).each do |i|
  power = BASIC_ROTATIONS[:x] ** i
  ROTATIONS << power * BASIC_ROTATIONS[:y]
  ROTATIONS << power * (BASIC_ROTATIONS[:y] ** 3)
end

これで準備は整いました。 パズルを解かせるプログラムを書いていきましょう。

パズルを解くアルゴリズムですが、 ピースの 24 種類の回転それぞれに対して空いているところに置いていくのを繰り返すという、 愚直な方法でやろうと思います。 たぶんこれは一番早くないと思います。

ということで、 まずはピースが特定の場所に置けるかどうかを判定するメソッドを作ります。 まだピースが置かれていない座標の配列 cells, 置きたいピース piece, ピースの回転行列 rotation, ピースの平行移動ベクトル translation の 4 つを引数に受け取って、 回転と平行移動を施したときにそのピースを構成する小立方体が全て空いている座標に入るかを判定させます。 判定の結果、 ピースが置けないなら nil を返させ、 置けるならそれを置いた後に空いている座標の配列を返させます。

def check_single(cells, piece, rotation, translation)
  new_cells = cells.clone  # 返り値用にピース座標列を複製
  piece.each do |cube|
    after_cube = rotation * cube + translation  # 回転と平行移動後の小立方体の座標
    if after_cube.all?{|s| s.between?(-1, 1)}  # 座標が全て -1 以上 1 以下の場合
      if cells.include?(after_cube)  # その座標が空いている場合
        new_cells.delete(after_cube)
      else
        return nil
      end
    else  # 座標が範囲からはみ出た場合
      return nil
    end
  end
  return new_cells
end

このメソッドを使ってパズルを解きます。 空いている座標列 cells, これから置きたいピースの列 pieces を受け取って、 そのピースが全て置けるかどうかを判定するメソッドを作ります。 まず pieces の先頭のピースを取り出して、 考えられる全ての回転と位置に対してその状態で置けるかどうかを判定して、 もし置けるなら、 残りのピースも置けるかを再帰的にこのメソッドを呼び出してチェックさせれば OK でしょう。 パズルが解けるかどうかだけでなく、 解けるならどのようにピースを置けば良いかも結果と欲しいので、 cells の経過を result という引数に受け渡していき、 解けたらこの result を返すことにします。 ・・・まあ、 このパズルはどうせ解けないように作ってあるんだからこんなことしなくても良いと思いますけどね!

def check(cells, pieces, result) 
  return result if pieces.empty?  # ピースがないなら終了
  piece = pieces[0]
  ROTATIONS.each do |rotation|  # 考えられる各回転に対して
    first_cube = rotation * piece[0]  # ピースを構成する 1 つ目の小立方体の回転後の座標を計算
    cells.each do |cell|  # 空いている座標に対して
      translation = translation = cell - first_cube  # 1 つ目のピースをそこに置くための平行移動を計算
      new_cells = check_single(cells, piece, rotation, translation)  # 置けるかチェック
      if new_cells  # もし置けるなら
        new_result = result + [new_cells]  # result に経過を保存
        final_result = check(new_cells, pieces.reject{|s| s == piece}, new_result)  # 残りのピースでチェック
        if final_result  # 残りの全てのピースも可能なら
          return final_result
        end
      end
    end
  end
  return nil
end

万が一このパズルが本当に解けるとすれば、 返り値として返ってくる result の各要素は、 途中経過で空いている座標の配列です。 これを見やすいように出力するメソッドも、 万が一に備えて、 一応、 作っておきます。

def output(cells)
  (-1..1).each do |z|
    (-1..1).each do |y|
      print("[")
      (-1..1).each do |x|
        if cells.include?(Vector[x, y, z])  # その座標が空なら
          print(" ")
        else
          print("#")
        end
      end
      puts("]")
    end
  end
end

これでプログラムは書き終わったのであとは実行するだけです! これで本当にパズルが解けないことを証明してやる・・・!!

result = check(cells, pieces, [])
if result
  result.each do |result_cells|
    output(result_cells)
    puts("---")
  end
else
  puts("impossible")
end

実行!

[   ]
[   ]
[   ]
[ # ]
[## ]
[   ]
[ ##]
[   ]
[   ]
---
[   ]
[ ##]
[  #]
[ # ]
[## ]
[  #]
[ ##]
[   ]
[   ]
---
[   ]
[ ##]
[ ##]
[ # ]
[## ]
[ ##]
[ ##]
[  #]
[ ##]
---
[   ]
[ ##]
[ ##]
[ # ]
[## ]
[###]
[###]
[###]
[###]
---
[ ##]
[ ##]
[ ##]
[ ##]
[###]
[###]
[###]
[###]
[###]
---
[###]
[###]
[###]
[###]
[###]
[###]
[###]
[###]
[###]
---

解けるんかーい!! え? 本当に?

・・・本当でした。 ということで、 私の頭が悪かっただけでした。 変な言いがかりしてごめんなさい・・・。

コード全体は Gist に置いておいたので、 需要は知りませんがよければご覧ください。