三角パズルsolverの修正と拡張

アルゴリズムはというと，
   H
  G I
 F E J
A B C D
と，数字を置く箇所にA〜Jの名前を割り振りまして，まずA〜Eについては{1,2,3,4,5}の順列です．次にF〜Hは，{1,2,3,4,5}からAの値とEの値を除いた，3つの数の集合について，順列を求めて割り振ります．IとJは，{1,2,3,4,5}からDとEとHの値を除いた，2つの数の順列です．
(略)
ruby -d TrianglePuzzleSolver.rbと実行すると，条件1と条件2を満たすすべてのパターンや，条件3に関する6つの数字（和）をもとにしたパターンも，出力します．条件1と条件2を満たすのは960通りです．ABCDEは5!＝120通りなのにFGHIJは960÷120＝8通りの自由度しかないのは興味深いところです．
三角パズルsolver

アルゴリズムを少し変えれば，すっきりすることに気づきました．A〜Eを決めたら次に，Hを選べばいいのです．これは，{1,2,3,4,5}からAとDとEの値を除いた，2つの数のいずれかです．FとGの選び方も，少し変わりまして，{1,2,3,4,5}からAとEとHの値を除いた，2つの数の順列となります．IとJは，変更ありません．これにより，5!×2×2!×2!＝120×8＝960通りを得ることができました．
そしてこの方法にすると，10か所に数字を並べたあと，それが適切かを判定するメソッドの呼び出しが不要となります．Gistのスクリプトファイルを更新しました．

これで話は終わりませんで，少し探すと，PDFによる三角パズルの紹介文書が見つかりました．

「三角パズル」のご紹介と今後の展開・展望について

そこには，三角形の一辺の大きさを一つ増やした「5×5*1」の問題が出てきます．

これも，solverを作りました．TrianglePuzzleSolver5x5.txtです．
前のエントリで検討していた「4×4」では，6つの和による制限がなければ960だったところ，5×5だと，4,354,560通りとなります．実際，

    I
   L M
  K H N
 J F G O
A B C D E

と，数字を置く箇所にA〜Jの名前を割り振ったら，（ACBDEFGHの配置）×（Iの配置）×（JKLの配置）×（MNOの配置）＝8!×3×3!×3!=4354560となります．Iの配置が3通りなのは，{1,2,3,4,5,6,7,8}から，A,E,F,G,Hの値を除いた集合から1個を選ぶからです．
ruby TrianglePuzzleSolver5x5.txtによって，上記「5×5の例題」の解を，以下のとおり出力します．

==== 7,11,23,5,20,15,14,17,8 ====
    3
   5 2
  6 1 4
 2 8 7 6
4 3 6 2 5
left[1]  = 7
left[2]  = 11
left[3]  = 23
down[1]  = 5
down[2]  = 20
down[3]  = 15
right[1] = 14
right[2] = 17
right[3] = 8

すべてのパターンを生成し，ハッシュに入れてから，9つの和をキーとして取り出す*2という処理をしているので，手元の計算機では5分弱かかりました．
また，ruby -d TrianglePuzzleSolver5x5.txtを実行すると，前回記事と同様に全パターンを出力します*3．このサイズでは，別解の存在，すなわち指定された9つの和によっては，解が一意に定まるとは限らないことを確認しました．ちょうど4つの別解を持つのは

====== values=7,12,18,7,15,14,19,16,7 ======
(case 1)
    6
   2 5
  1 4 7
 5 8 3 2
7 2 6 5 1
(case 2)
    6
   5 2
  1 4 7
 2 8 3 5
7 5 6 2 1
(case 3)
    6
   4 3
  3 2 7
 1 8 5 4
7 6 4 3 1
(case 4)
    6
   5 2
  2 3 7
 1 8 4 5
7 6 5 2 1

をはじめ276通り*4あり，5つ以上というのが出現しないのは，場合の数だの順列だのといった，高校までの数学の知識では，説明できそうにありません．

*1:どのあたりが「×」なのか，想像つきかねるのですが．

*2:実のところ，プログラムでは，すでに配置されている1〜8の数字を取り除いた，についての解を求めています．