2007/07/22(日)魔方陣

全探索でとくプログラムを作成していたのですが
4x4ですでに探索範囲広すぎ...

枝狩りしてもいい感じな時間がかかって現実的ではありませんでした.
とりあえずやっている枝狩り

  • 縦・横のいままでの合計から,次に入れられる最小値を求める\4x4の場合目標値が34なので,最初2マスに2, 3が入っていたら3マス目は13以上じゃないと34に届かない
  • 列がそろったときに目的の値になっているかテストする

他に何か効率あげる枝狩りの手段ってあるの?

全パターン

回転,対称を含めた7040パターン出すのに20分近くかかってる.
4隅の大小関係に制限をかけて1/8にしても2-3分くらいはかかってしまう模様.