ホーム > 家族のギャラリー > ペントミノを解く > 第5章 C言語版の高速化あれこれ > 以前の高速化の取り組み
以前の高速化の取り組み

C言語バージョンで以下の結果が得られています。以下の結果を得たソースコードは 付録3 C言語版ソース で公開しますのでご興味のある方は遊んでみて下さい。

1999.2.15
JavaScript版の速度改善を目指し、C言語版でアルゴリズムの調査を行ってみました。完成できないピースの配置パターンを早めに探索し、諦めるように(探索の刈り込み)したところ赤字のような結果になりました。20×3は劇的に早くなりましたが、10×6は遅くなっています。もう少し色々な刈り込み方法を試して全てのタイプが早く処理できるようになったら、JavaScript版に反映したいと思います。併せて公開C言語版ソースも更新します。

1999.3.14
今までの解法は、完成したピースの回転と反転を考慮せずに計算していたので、正解数の4倍の解を求めていました。これが遅い原因でもあった訳で、今回、10×6の場合には正解数のみ計算する方法にしました。表の緑字が結果です。アルゴリズムの都合で、10×6以外は2倍の解が求まります。探索枝の刈り込みは、1999.2.15版を組み込んでます。10×6の場合には、初期バージョンの刈り込みの方が15%程度早いのですが、他のケースでは1999.2.15版が圧倒的に早いのでこれにしました。

1999.9.19
1999.3.14版(下記表の緑字の性能)をJavaScript版に反映して公開しました(半年もかかってしまった^_^;)。なお、付録3 C言語版ソース公開しているC言語版のソースはまだ古い(1999.2.15以前)です。

2001.2.22
daichonさんのプラパズルNo.600(ヘキソミノ)の完全解を求めて。。。に刺激されて久しぶりにプログラミングをしてみました。
daichonさんのページでBorlandがフリーでDOS(Windows)用のC++コンパイラを提供していることを知り、自宅のPCに開発環境を作った次第です。また、ペントミノやヘキソミノの解法として左から右に向かって解く方が高速とのアイデアを利用させて頂きトライしてみました。

このため(というか、ヘキソミノのため)にピースデータの作成を自動化しました。今までは、事前に人手で12ピースの回転・反転を計算してピースデータを書いていましたが、今回は回転や反転、及び重複の削除をプログラムで計算しています。ヘキソミノの35ピースの回転や反転を手で計算するのが大変だったのが本音(^_^)

枝苅りの方法や求める解数は、1999.3.14版と同じです。プラットホームが変更になったので単純には比較できませんが劇的に早くなりました。下記の表の青字が今回の測定結果です。解のリストを出力しなければもう少し早いかもしれない。また今回、8×8−4のドーナツ形状も追加してみました。新しく書き直したソースは付録3 C言語版ソースで公開しています。JavaScript版の方はまだ旧いままです。

タイプ 解の数 版数(日付) 処理時間 計算した解数 全解リストのダウンロード
10×6 2,339 1999.1.24版
1999.2.15版
1999.3.14版
2001.2.22版
13m12s
20m17s
1m20s
3.1s
792s
1217s
80s
3.1s
9,356
9,356
2,339
2,339
list6_10.lzh(61KB)
12×5 1,010 1999.1.24版
1999.2.15版
1999.3.14版
2001.2.22版
31m03s
32m50s
4m00s
2.4s
1863s
1970s
240s
2.4s
4,040
4,040
2,020
2,020
list5_12.lzh(53KB)
15×4 368 1999.1.24版
1999.2.15版
1999.3.14版
2001.2.22版
1h12m53s
23m55s
2m55s
2.2s
4373s
1435s
175s
2.2s
1,472
1,472
736
736
list4_15.lzh(18KB)
20×3 2 1999.1.24版
1999.2.15版
1999.3.14版
2001.2.22版
1h16m14s
1m30s
5s
0.006s
4574s
90s
5s
0.006s
8
8
4
4
list3_20.lzh(1KB)
8×8 130 2001.2.22版 0.9s 0.9s 130 list8_8.lzh(4KB)
  Copyright (C) Nakamura 1999