baroque-tower.lp

\ ドラクエ７のバロックの塔 (バロックタワー) の謎解き (ギミック)
\
\ http://ryocotan.tumblr.com/post/46204757099
\ http://msakai.jp/d/?date=20130402#p01
\
\ 銅像が上下左右に４つあり、それを全て中心に向かせればOK。
\ 銅像の間 （四隅） にはボタンがあって、それを押すと、
\ そのボタンから反時計周りに３つの銅像が、右に９０度回転する。
\ 初期状態では、上下左右の銅像の向きは順に右上上左。
\
\ x1, x2, x3, x4 をそれぞれ左上、右上、右下、左下の石を押す回数とすると、
\ 最短の手順を求める問題は、以下の最適化問題として定式化できる。
\
\ Minimize
\   x1 + x2 + x3 + x4
\ Subject To
\   3 + x1 + x2 + x3 ≡ 0 mod 4  (左の像の条件)
\   3 + x2 + x3 + x4 ≡ 0 mod 4  (上の像の条件)
\       x3 + x4 + x1 ≡ 0 mod 4  (右の像の条件)
\       x4 + x1 + x2 ≡ 0 mod 4  (下の像の条件)
\   x1, x2, x3, x4 ≥ 0
\   x1, x2, x3, x4 ∈ Z
\ 
\ 追加的な変数を導入してmodを取り除けば、これは整数線形計画問題になる。
\
Minimize
  x1 + x2 + x3 + x4
Subject To
  x1 + x2 + x3 - 4 n1 = -3
  x2 + x3 + x4 - 4 n2 = -3
  x3 + x4 + x1 - 4 n3 = 0
  x4 + x1 + x2 - 4 n4 = 0
Bounds
  0 <= x1
  0 <= x2
  0 <= x3
  0 <= x4
  0 <= n1
  0 <= n2
  0 <= n3
  0 <= n4
General
  x1 x2 x3 x4 n1 n2 n3 n4
End

\ o 6
\ s OPTIMUM FOUND
\ v n1 = 2
\ v n2 = 2
\ v n3 = 1
\ v n4 = 1
\ v x1 = 1
\ v x2 = 2
\ v x3 = 2
\ v x4 = 1