エンジニアのソフトウェア的愛情

または私は如何にして心配するのを止めてプログラムを・愛する・ようになったか

バロックタワーのパズルを解く(演算で)

じーっと、内容を眺めて。「演算で解けそう」と感じたので、やってみた。
いつものように。あんまり厳密ではないです。と、最初に言い訳。


パズルの内容と数値との対応はこんな感じ。

  • 像の番号: 上=0, 右=1, 下=2, 左=3
  • 像の向き: 上=0, 右=1, 下=2, 左=3
  • ボタン: 像0と1の間=0, 像1と2の間=1, 像2と3の間=2, 像3と0の間=3


像0の向きは、最初の向きとボタン0、ボタン1、ボタン2のそれぞれを押した回数との合計なので、最初の向きをa0、ボタンを押した回数をそれぞれx0、x1、x2、最終的な向きを下(=2)とすると次のような式で表すことができます。

a0 + x0 + x1 + x2 ≡ 2 (mod 4)


それぞれの像についても同様に考えます。結果次の4つの式が得られます。

a0 + x0 + x1 + x2 ≡ 2 (mod 4)
x3 + a1 + x1 + x2 ≡ 3 (mod 4)
x3 + x0 + a2 + x2 ≡ 0 (mod 4)
x3 + x0 + x1 + a3 ≡ 1 (mod 4)


この連立方程式を解くと、次のようになります。

3x0 ≡ - a0 + 2a1 -  a2 -  a3 - 3 (mod 4)
3x1 ≡ - a0 -  a1 + 2a2 -  a3 + 6 (mod 4)
3x2 ≡ - a0 -  a1 -  a2 + 2a3 + 3 (mod 4)
3x3 ≡  2a0 -  a1 -  a2 -  a3     (mod 4)


これにa0, a1, a2, a3に3, 2, 2, 3を代入して計算すると。

3x0 ≡ - 3 + 2 × 2 - 2 - 3 - 3 (mod 4)
    ≡ -7 ≡ -3 ≡ 1 ≡ 5 ≡ 9 ≡ 13 ≡ ... (mod 4)


解が正の整数になるもので最小のものを選ぶと、3x0 = 9、ゆえにx0 = 3となります。

同様に他の解も選ぶと、

x0 = 3
x1 = 2
x2 = 2
x3 = 1

となり「ボタン0を3回、ボタン1を2回、ボタン2を2回、ボタン1を1回、押す」が答えになります。


…。


なんか、人の努力を台無しにした気分がしないでもない…。

いつか読むはずっと読まない:ヘアスタイルを法として

mod演算をどっかで扱ってたはず、と思ったら、この第7章でした。

数学ガール/フェルマーの最終定理 (数学ガールシリーズ 2)

数学ガール/フェルマーの最終定理 (数学ガールシリーズ 2)