「5個の4つ分」をRubyで

次の図とともに，「●の数をかけ算の式にしましょう」という問題を出したところ，5×4＝20とする子がいました．
　　●●　　
　　●●　　
●●●●●●
●●●●●●
　　●●　　
　　●●　　
どのように考えて，5×4としたのでしょうか．
5個の4つ分

　　１２　　
　　３４　　
１２１２１２
３４３４３４
　　１２　　
　　３４

「90度回転させても同形」となることを確認するため，Ruby スクリプトを書きました．

Four fives: Method A · GitHub

実行結果は以下のとおり．

$ ruby rot90a.rb
  1*
  **
1*1*1*
******
  1*
  **

  14
  23
141414
232323
  14
  23

初期画面は，空白文字と「*」「1」からなります．図形の真ん中を中心として，それぞれの「1」を反時計回りに90度回転させて移動する位置に「2」，同様に「3」「4」を書きます．
出力を見ると，「14(改行)23」が5つあるように見えますが，1行3列（左上を1行1列として）の「1」は，90度回転により，4行1列~~3行1列~~に移動しています．2行3列の「2」について，元の（回転前の）「1」は，3行5列です．
スクリプトの肝心なところは，この，90度回転によって，各点がどこに移るかを求める処理です．メソッドxy_rot90で書いていまして，以下の手順を踏んでいます．

(x_from,y_from)（左上が(0,0)）に対して，（x1,y1)=(x_from-2.5,y_from-2.5)として平行移動
(x2,y2)=(y1,-x1)として，反時計回りに90度回転*1
(x_to,y_to)=(x2+2.5,y2+2.5)として，平行移動

1例ではつまらないので，初期パターンからすべての「5個の4つ分」を求めるようにしましょう．ただし，それぞれの「5個」は，反時計回りに90度回転させていけば同一になるものに限ります．wikipedia:回転対称の用語を使うと，4回対称であることの根拠となる分け方をすべて求めます．
スクリプトは以下から取得できます．

Four fives: Method B · GitHub

wikipedia:エイト・クイーンを（鈍くさい）方法で解くのと同様に，20箇所の「*」から5箇所を選んで「1」とします*2．そして，90度回転で「2」「3」「4」を割り当てて，「*」がなくなれば，解とします．回転や鏡像のチェックはしておらず，別々に解としています．
何通りあるかな…と実行してみると，面白い数字が出ました．

$ ruby rot90b.rb
  **  
  **  
******
******
  **  
  **  
Answer No.1
  11  
  11  
221444
222344
  33  
  33  
(略)
Answer No.1024
  33  
  33  
443222
444122
  11  
  11

2の10乗通りです．なぜこの数になるのかは，わかりません*3．
答えの数を絞るとともに，高速化を試みます．

Four fives: Method C · GitHub

そうして見直してみると，どれも，真ん中の4つの●に，１２３４をちょうど一つずつ割り当てています．

と先日書いたのですが，真ん中の4つの「*」のうち左上，すなわち6×6の平面なら3行3列に「1」が配置されるもののみに，限定します．
それと，90度回転について，0.5とはいえ実数が入るのは高速化の妨げに見えますので，座標の値から一律に2.5を引いていたところを，次のように変更します．

もとの座標の値	0	1	2	3	4	5
修正前	-2.5	-1.5	-0.5	0.5	1.5	2.5
修正後	-3	-2	-1	1	2	3

もちろん，2.5を加えるところも修正します．これらの変換は，ローカル変数@coord1および@coord2に値を割り当て，ハッシュとして実現しています．
結果は，256通りとなりました．さらに見ていくと，どの「1」にも8近傍*4に他の「1」がないものは，次の2種類だけです．

Answer No.42
  14  
  23  
141414
232323
  14  
  23  
Answer No.98
  41  
  23  
241413
132324
  14  
  32

そして，5つの「1」が4連結となっているのは，次の5種類です．

Answer No.1
  11  
  11  
221444
222344
  33  
  33  
Answer No.2
  11  
  14  
211444
222334
  23  
  33  
Answer No.20
  14  
  14  
111444
222333
  23  
  23  
Answer No.123
  44  
  14  
111443
122333
  23  
  22  
Answer No.181
  44  
  44  
111433
112333
  22  
  22

No.20は，先日のエントリにも入れていましたが，No.2のようにS字型でも「5個」が取れるのには，気づいていませんでした．
No.1とNo.181，No.2とNo.123の「1」はそれぞれ，(0,0)からの対角線を軸とした鏡像の関係になっています．No.42，No.98，No.20の「1」の配置は，同じ軸で線対称となっています．回転・鏡像は同じ解とみなす（重複してカウントしない）として，さらに解を少なくしたとき，全部で何通りになるかというのは，2のべき乗になってくれないようです．

翌日追記：2番目のスクリプトで，初期配置を

******
******
******
******
******
******

とし，Linuxマシン（Ruby 1.9）で実行してみたところ，7時間半ほどかけて，解を出力しました．ファイルには保存しておらず，最後の2つだけを書いておきます．

(略)
Answer No.262143
433333
433322
443222
444122
441112
111112
Answer No.262144
333332
433322
443222
444122
441112
411111

262144は馴染みでない数なので，素因数分解計算機にかけると，「2の18乗」と出ました．
ということで， $4k$ 個のドットからなる4回対称の配置に対して，同じ形状になるグループ分け（「1」「2」「3」「4」の番号付けの仕方）は，回転・鏡像を別に数えたら， $2^{2k+1}$ 通りになる，という仮説が立てられます．指数のところに1を加えているのは，番号付けに関して時計回りと反時計回りがあるためです． $k$ に関する数学的帰納法で，証明できそうです．