プログラミングパズルに関心のある人は雑談しましょう！
deepgreenさんの考えているアイデアを想像しています。 上半分だけの探索と下半分だけの探索を合成させて、かけ算方式で解の個数を 積み上げて行こうという構想なのでしょうか。面白いですね。 上半分だけの部分解についてクイーンの配置が異なっていても、下半分に影響を 与える利き筋が同型であれば、以後の探索が重複することになるので、その無駄 を省けるということなのでしょうね。 単なるバックトラックではない何か別のアイデアが必要だと思っていましたが、 ビット処理に頼ることなく queen4a.c を超えているというのは成功していると 思います。具体的にどんなプログラムを組んでいるのかは想像もつきませんが、 これからが楽しみです。
こんばんは、deepgreenです。 言い出しっぺが何も書けないのは、歯がゆい思いです。 いろいろと試行錯誤をしましたが、ほとんどは失敗作でした。 その中でようやくqueen4aを超えるものができました。しばらくは これをベースに改善をしてみようと思っています。 deepgreen result queen4a (msec) (sec) ===== N=12 Count = 1787 time= 159 0 ===== N=14 Count = 45752 time= 2865 2 ===== N=16 Count = 1846955 time=74550 104 Pentium3 450Mhz 次の目標は、nqueen3ですが、私のＰＣでは２８秒(=104/22*6) になります。果たしてどこまで迫れるか？ ハードルは非常に 高いですね。 補足：実装は、１６ｘ１６の問題を２分割して２つの１６ｘ８の 部分解を求めて、それを合成して最終解を求める方式です。 部分解を求める部分は、queen4aの論理を使っています。 この部分は、ビット演算にすれば改善できますが、大幅な 改善は望めません。一番処理が重いのは合成する処理でこ の部分のうまいアルゴリズムがなくて苦戦しています。
Ｎクイーン問題に関する話題が続かないようなので、私自身のとりあえずの 完成版となるソースコードとプログラムの説明を下のURLに置いておきました。 気力を使い果たしてしまったので、これを見て何か思いつく新たなアイデア等 ありましたら是非とも投稿をお願いします。../../puzzle/nqueens/index.html
ご無沙汰しております。広井です。 最小完全ハッシュ関数の出典ですが、私は次の文献で知りました。 村田敏幸, 『X68000マシン語プログラミング 探しもの』, Oh!X 1992 年 12 月号, ソフトバンク ご参考までに、上記文献から最小完全ハッシュ関数の説明を引用します。 『もし、探索対象が固定であれば, 全データのハッシュ値が重複しないところまで, ハッシュ関数を煮詰めることも可能だ。このようなハッシュ関数を完全ハッシュ関数 といい, 特に, n 個のデータを 0 〜 n - 1 に変換する場合を最小完全ハッシュ関数 という。』 > 確かに最少完全ハッシュ関数という言葉は一般的には使われていないようです。 そうみたいですね。Google で検索してみたところ、ヒットするページがあまりにも 少なくて、ちょっと驚いてしまいました。私はパズルの解法で「最小完全ハッシュ 関数」を使いましたが、それ以外ではコンパイラの作成など特定の分野でしか使わ れていないのかもしれません。 > しかし、今にして思うと「下限値枝刈り法」という用語は私が勝手に付けてしまった > 名前だったかも知れません。(恐ろしい) 私は高橋さんが執筆された特集で「下限値枝刈り法」を知りましたが、この用語も 一般的ではないかもしれませんね。ですが、アルゴリズムをよく表している名前な ので、とくに問題はないと思いますよ。 ところで、高橋さんが作成された N Queens Problem の解法プログラム queenbit1.c はとても参考になりました。ありがとうございます。こんな簡単な方法でここまで 速くなるとは、とても驚きました。 ではでは。
塗り壁さん、ご指摘ありがとうございます。確かに最少完全ハッシュ関数という 言葉は一般的には使われていないようです。順列の完全ハッシュ関数の中で値の 範囲が最少になるもの、という言い方が正しいかも知れません。ただ、その逆関数 がつまりは順列生成ルーチンそのものである、という意識のないままに逆関数を 自作したことがあり、それが結局は順列生成ルーチンだったと今更ながら知って 驚いていたりする訳です。 ただ、最少完全ハッシュ関数という用語については内容を正確に表わしているし、 他のものとの混同や誤解を招くような要因もないので、私は今後とも使っていく ことになるだろうと思います。(いいのか？) ところで私の持っている用語の知識は、Ｃマガ電脳クラブの読者の投稿プログラム からだったり、私的なウェブサイトから得たものだったりと、かなり曖昧である ことは事実です。何年か前にＣマガの特集記事の原稿依頼があった時も、そのことが 気になって一旦はお断りした経緯があります。結局は、内容や用語について専門の人 からチェックして頂けるという条件で引き受けていたのです。 しかし、今にして思うと「下限値枝刈り法」という用語は私が勝手に付けてしまった 名前だったかも知れません。(恐ろしい)
高橋謙一郎さん、今晩は、塗り壁です。私の記事を見て下さって、 有り難う御座います。 速度の点で不満との事ですが、私にとっては、論理を簡潔にする事 と汎用性が大事であり、速度の優先順位は低くなっています。 前者については、全ての解をつくしているのを示すのは、私の方法では ほとんど自明ですが、他の方法ではそう簡単には行かないでしょう。 また、後者は最少完全ハッシュ関数（私はあまりこういう言い方は知りませんが、 その言葉の出典はどこでしょう）というクイーン問題だけでなく、他のいろいろ な問題にも適用できるものを使っている事です。 と言っても、性能面をなおざりにする気もありませんので、性能向上に関して ３回目、４回目で取り上げる予定です。 全ての順列を生成している事が性能が悪い原因ですので、クイーン問題の解の 可能性のある順列のみを生成する、というのが基本方針です。 但し、生成の仕組みがかなり複雑になりますので、性能はかえって悪くなるような気は しますが、理論的重要性を考えて敢えて取り上げるつもりです。
塗り壁さんのアプローチはまさに最少完全ハッシュ関数の逆関数によるものでしたね。 とても面白い方法という印象を受けましたが実行速度の点でかなり劣りますので 私の気持ちとしては不満が残ってしまいます。組合せ論的な方法で高速に求める方法 はないものでしょうか。 私事ですが、ビット処理方法による Total Soltions を求めるプログラムが好成績だった ので、今度はそれを改造して Unique Soltions を求めるプログラムを書いてみました。 ところで、鏡像解のチェックは３つのパターンだけを照合すればよいですね。 N-Queens Unique Solutions 15: 285053 0.94sec 16: 1846955 6.15sec 17: 11977939 42.46sec 18: 83263591 307.36sec 19: 621012754 2358.56sec CPU = Athlon XP 2100+ (1.73GHz)
高橋謙一郎さん、今晩は。 工学社のホームページに 今回分のサンプルプログラムが掲載されています。 よろしければ見てください。 画面の上の「サポート」タブをクリックして、出てきた画面で 「I/O 2003年 5月号 「数学的プログラミング 第1回」」を 選んで下さい。 本を買ってない人でも自由に見る事ができます。
藤原さんのqueen4.cに追加した枝刈り(queen4a.c)の説明をします。 最後の対称解のチェックで必ず却下されることが明白なパターンを 排除してしまおうという枝刈りです。 ×禁禁×口禁禁禁 ×口×口口口口禁 ××口口口口口禁 ●××××××× ××口口口口口口 ×口×口口口口禁 ×口口×口口口禁 ×禁禁口×禁禁禁 x=0,y=2 に最初のコマ●を置いた瞬間 図に示した[禁]は対称解のチェックの関係で置けない場所です。 探索終盤のマスは既に制限がきつく、あまり効果はないものの、 y=0 と y=boardsize-1 のラインにかかる序盤の[禁]にはそれ なりの枝刈り効果が発揮出来るようです。 また、効果は薄いですが対称解のチェックの中で自分自身との 比較と上下反転したのみのパターンとの比較は不要でしょう。 とは言っても、queen4.c の探索方法があまりに優秀なので、 これを上回る探索方法を見つけるのは相当に厳しい感じがします。
塗り壁さん、こんばんは。 近くのちょっと大きめな本屋で「Ｉ／Ｏ」を探してみましたが、見つかり ませんでした。連休中にでも遠出して大きな本屋でまた探してみます。 Ｎクイーン問題を順列や組合せの観点から解析するというのは面白そう ですね。絶対に読んでみたいです。