アルゴリズムパズル 5 行と列の入れ替え 実装例

1. 概要

『アルゴリズムパズル ―プログラマのための数学パズル入門』の5番目の問題「行と列の入れ替え」の実装例です．
この本はパズルの問題文・ヒント・解法が羅列されているという少し特殊な本なので，ブログにパズルの内容について書くのは引用に収まるのか？という疑問があるので問題文は書かないです．

2. 解説など

まぁ少し考えれば答えが「いいえ」であることはあきらかで，理由は解説に書いてあるとおりである(15と13といった同じ行にある数字を，相異なる行に移動させるという操作は行の入れ替え・列の入れ替えではできない)．
また一つの行を揃えれば全部の行の並びは揃うし，一つの列を揃えれば全部の列の並びは揃うという性質がある．
なお，パネルの並びを行列としてみたときに行の入れ替え・列の入れ替えは行列の積で表せる．
また行・列を入れ替えるような行列は行列式が-1であるから，初期状態と最終状態の行列式の絶対値が異なってるかどうかでもこの問題では判定できる(初期状態では行列式は0だが最終状態では行列式が0でない)．
ただし「行列式の絶対値が異なる→解はNo」は真だが「行列式の絶対値が等しい→解はYes」は必ずしも真ではない(行列によっては成り立たない).

3. ソースコード

一致させられるか判定するプログラムをCommon Lispで書こうとして詰まってしまって，ひょっとして単に僕のプログラミング力が低いからではと思いRustで実装した．
単に僕のプログラミング力が低いからだった．
判定方法は実際に揃えてみて一致するか確認してるだけ．

4. 感想

線形代数の勉強をしているので少し面白かった．