プラパズルNo.600(ヘキソミノ)に関しては「関連リンク集」(2002/12/18)を参照ください。
各ピースの名称は暇人さんの定義を採用しました。各ピースの向き番号リスト
を追加 (2010/2/22)
各ピースの画像ファイルを中村さんの画像を元に作成しました。(2010/2/5)
このページの目的:
SETIが地球外生命を見つけるまでに完全解を求める。
いままでの検討結果から5年、10年は平気でかかりそうなのでライフワークとして細く、長く、途切れながら進めて行く予定です。ご意見、アイデア、情報何でも結構です、「掲示板」にてお待ちしています。
まだまだやります、と書いてもうすぐ4年、はじめてから9年!!
・・・ 2010/1/21
2005年当時、それなりにいろいろやってはみたのですが、エントリーに上げるほどの成果も出せないうちに、公私共にいろいろバタバタとしてそのまま放置になってしまいました。期待していただいた方へ、あらためてお詫び申し上げます。
今回も書き始めたところで突発の重い仕事が入って、微妙な状況ですが、少しずつでも書き込んでいこうと思ってます。
今回、再開のきっかけとなったのは、サブパーツに対する新しいアイデアが浮かんだことです。
今までは、組み合わせた時に重ならないパーツのリストを作成し、それらを組み合わせて、残りの空白部分を探索するという考え方でした。これを実際に試してみると、パーツの組み合わせが想定以上に爆発的に増加し、その対処として、数手先チェック等を検討していましたが、なかなか有効なものが見つからず、行き詰まってしまいました。
今回は、逆に重なる部分をインデックスにすることにより、パーツリストを作成した後は、一切探索は不要になるはずではというものです。少しずつでも具体的な説明、検討結果を載せていければと思っています。
この場合のキー(ボトルネック)は、CPUの制限に対する演算スピード、アルゴリズムよりも、メモリーおよびストレージの制限に対する、データベースサイズ、インデックス性能といったものになるのではと考えています。
第4期顛末 (2010/1/22)
すぐにでも本題に入りたいところですが、まずは前回の内容を軽くまとめておきます。
部分解への分割方法の検討 (ver.0.15 2010/02/14)
前置きが長くなりましたが、やっと新アイデアの話で、少しずつ追加していく予定です。
ver.0.10 2010/01/24 全面改訂 境界部分のピースをインデックスに
ver.0.11 2010/01/28 パーツ・リストの考察追加
ver.0.12 2010/02/01 パーツ定義の変更
ver.0.13 2010/02/04 2分割パーツ
・リストの考察追加
ver.0.14 2010/02/07 ヘキソミノ
分割方法、組み合わせ順序、パーツ・リスト書きかけ
ver.0.15 2010/02/14 ヘキソミノ
分割方法 細分化→8分割検討
ヘキソミノ完全解へのシナリオ (ver.0.34 2010/03/03)
0.34 2010/03/03 下層パーツの組み合わせで4分割パーツ1個完成。
検証用4分割パーツ結果
0.33 2010/02/28 下層パーツの組み合わせで4分割パーツを作り始める
0.32 2010/02/24 詰める順番を左上から、右上に変更、各章追記、
バイナリデータの図示化追加
0.31 2010/02/22 計算時間の推定、ピースの数値表現、処理フロー書きかけ
0.30 2010/02/20 部分解への分割方法の検討ver.0.15に合わせて全面改訂初稿
まだまだやります、2年間の休止を経て「第4期?」 2005/4/21
皆様、ご無沙汰しております。
と、言うか、このページを定期的に見ていただいている方はいるのでしょうか?
私は、しばらく見ていなかったので、掲示板に書き込みがあったのも気がつきませんでした。書き込んでくれた方、本当にごめんなさい。
さて、第3期が総括もなしに尻つぼみになって早や2年以上が過ぎ、久々にまたごそごそと、思考をめぐらせています。さてさて今回は、どこまで続くやら。。。
今回は、第三期のシナリオを再検討し、サブパーツの設定を下図のように変更しているのと、サブパーツを作るにしても、素の計算速度がないことには、作業が進まないので、あらためて枝刈りの高速化の検討を予定してます。
出直しの「第3期の方針」
原点の「パズルのプログラミングを楽しもう」に戻って、部分解の最適化(高速化)で遊ぶ。
但し、あくまでもその内容は、完全解を目指したものにする。
命題1計算用スクリーン・セイバー by 岡田好一さん (2003/01/01)
ソース付き圧縮ファイル
meidai.lzh readme.txt
Ver2.0に差し替え(2003/01/23)
使用条件:フリーソフト。岡田さんの許諾なしに無制限に配布可。
Web等に掲載時には、事後承諾で構わないので、岡田さんに連絡してください。
ver 2.0 (2003-01-15) 対称を考慮
完全に対称のもの以外は、片方のみを計算。全体の計算時間が約半分になるはず。
v1.xとは途中経過データの互換性なし。
中村さんがホームページにて、ヘキソミノあれこれを掲載。 (2002/12/31)
ヘキソミノ 分割、分類方法 その1 その2 (2002/12/29)
部分解への分割方法の検討 (ver0.02
2002/12/22)
ヘキソミノ完全解へのシナリオVer0.10リリース
(2002/12/11)
現在までの経過
第1期(01/01/27〜01/03/16)の成果
( 詳細は ヘキソミノの掲示板 過去ログ
No.1 )
- 全解の推定は10の20乗から25乗程度
- 全解をリニアに、しらみつぶしで解くことは時間的に困難
- 全解の保存もDisk容量的に困難
- 仮に保存できたとしても、全解の比較検証は困難
第2期(01/07/20〜01/10/09)の成果、反省
( 詳細は ヘキソミノ完全解へのシナリオVer.
0.05 掲示板 )
予想(期待)に反して、部分解においても、計算時間、必要Disk容量が膨大になることが判明。
プログラミング・テクニックよりもプロジェクト・マネージメント的な要素が強くなり、なんか仕事をしているようで、やる気が持続しなかった。
第2期までのTopページ
ヘキソミノ全解の推定
*** 参考になる物何でも構いません、連絡お待ちしてます。***
ヘキソミノ実計算結果
全解数 |
Date |
Author |
Time |
Comment |
20,360,000,000 |
2001/03/13 |
daichon |
182H+α |
1里塚: 203億6千万解 |
10,000,000 |
2001/03/07 |
中村さん |
182H |
1千万解です。でも全解にはほど遠い。 |
1,637,396 |
2001/02/12 |
暇人さん |
193H |
163万7千解 |
100,000 |
2001/02/02 |
暇人さん |
5H04M |
10万解です |
10,000 |
2001/02/01 |
中村さん |
2H18M |
ヘキソミノ、とりあえず10,000解 |
祝!! ペントミノ
1秒の壁突破 (0.84秒 Pen3 800M) (2002/12/13)
半年遅れのお祝いですが、中村さんのホームページにて、改善内容が詳しく紹介されています。
すごい、すごい!! でも、ちょっと悔しい。。。。。
でもでも、すごくためになるので、しゃぶらせてもらいます。
シナリオV0.10を作ったばかりですが、初期条件の設定がまだまだ高すぎることが分かり、当面のターゲットを200億解をやったときの左側部分解を求めたところの高速化をやろうとしていました。
やっぱり悔しいので、そこで試そうとしていた、アイデアをもう一度ペントミノでやってみることにします。(多分、掲示板がメイン)
究極の最高速、ペントミノ全解数、出力プログラムとベンチマーク考 (2002/12/14)
部分解への分割方法の検討 (ver0.02
2002/12/22)
休止している間に、ヘキソミノ関連のページがいくつか増えていました。リンクの承認が取れしだい追加していきます。(2002/12/18)
古いプラパズル No.600の推定解数の変遷がはじめてわかりました。
(投稿コーナーに私の手持ちの写真を載せていただきました。)
余詰指摘 テンヨーからの手紙は家宝ものですね。(URL変更予定あり)
岡田好一ホームページ
の ヘプタモンド・スクリーンセーバ (try7s)
はやく枠組みを完成させて、スクリーンセーバーにして配りたい!!
へきそみのらんど リンクまだしてなかった。しもまっちさんすいません。
|