畳の敷き方をRubyで求める

いきなりですが問題です．

（大きめの画像, オリジナル）

「畳の敷き方」の算数問題を，自身はじめて知ったのは，昨年度の全国学力テストでした*1．いまWebで調べてみると，先人の取り組みが何件か，ヒットしました．

冒頭の全国学力テストの問題は，頭の中で解くことができ，配置は1通りしかないことの確かめも，さほど難しくないのですが，他の場合でも求められるよう，Rubyでソルバを作りました．
仕様は次のとおり．

2×1のサイズの畳のみを使用して配置します．
縦と横は任意の正整数です．ただし少なくとも一方は偶数とします．
デフォルトでは，畳を1つも敷いていない状態から，解を求めますが，初期状態を与えることも可能です．
敷き詰められたら出力します．回転や鏡像は，異なる解となります．
敷き詰めた状態について，「4つの角が1箇所に集まっているか」「断層線ができているか」のチェックを行い，該当する場合には解と見なさないことも可能です．

いつものようにRuby スクリプトをGistに置いています．コマンドライン引数は3つとり（いずれも省略可），幅，高さ，絞り込みラベル*4です．最初の引数が「B」の場合，全国学力テストの問題を解きます．
出力例は次のとおり．「←→」が，横に敷いた1枚の畳を，「↑」と「↓」が，縦に敷いた1枚の畳を表します*5．

$ ruby tatami.rbNo.1 (FC,SL)
↑↑↑↑
↓↓↓↓
↑↑↑↑
↓↓↓↓
No.2 (FC,SL)
↑↑↑↑
↓↓↓↓
↑↑←→
↓↓←→
(略)
No.13
↑←→↑
↓↑↑↓
↑↓↓↑
↓←→↓
(略)
No.36 (FC,SL)
←→←→
←→←→
←→←→
←→←→

$ ruby tatami.rb 4 4 fcsl
No.1
↑←→↑
↓↑↑↓
↑↓↓↑
↓←→↓
No.2
←→←→
↑←→↑
↓←→↓
←→←→

$ ruby tatami.rb B
No.1
←→↑
↑↑↓
↓↓↑
←→↓

$ ruby -d tatami.rb B
(略)
displace_tatami(0,0,:ud)
・・↑
・・↓
・・・
←→・
place_tatami(0,0,:lr)
←→↑
・・↓
・・・
←→・
place_tatami(0,1,:ud)
←→↑
↑・↓
↓・・
←→・
place_tatami(1,1,:ud)
←→↑
↑↑↓
↓↓・
←→・
place_tatami(2,2,:ud)
fc_h: {}
sl_h: {}
No.1
←→↑
↑↑↓
↓↓↑
←→↓
(略)

アルゴリズムには「バックトラッキング」を用いています．敷かれていない箇所を走査して見つけ，その箇所を含んで縦に敷くこと，横に敷くことを別々に試みます．1枚を敷くことができたとき，次の1枚を敷くには，startメソッドを再帰的に呼び出します．
2種類のチェックは，2次元配置（「↑↓←→」を用いた出力結果）ではなく，どこを起点にどの方向に畳を敷いたかの配列を内部で持っていて，その情報をもとに行っています．

*1:http://d.hatena.ne.jp/takehikom/20140429/1398720384,

*2:http://www.jsse.jp/jsse/modules/note7/index.php?id=28より，2010年（平成22年）9月25日発表とのこと．

*3:参考として挙げられている『心を揺する楽しい授業話題源数学』は，気軽に購入できる本ではなさそうです．自校の図書館検索ではヒットしたので，思い出したときに見に行くとしますか．

*4:"fc"を書いていれば，「4つの角が1箇所に集まっている」ものを解と見なしません．"sl"を書いていれば，「断層線ができている」ものを解と見なしません．

*5:ソースコードを1箇所，変更することで，ASCII文字のみによる出力も可能です．横は「[]」，縦はいろいろ試して「!」と「!」にしました．