)
CCM にもとづく制約充足とくに N クイーン問題の解法をさらにくわしく
しりたければ，文献 [3] をみるとよいでしょう．また，
CCM にもとづくさまざまなソート法についてしりたければ，
文献 [4] をみるとよいでしょう．
| [Japanese version] | [English version] |
| [一時的なミラーページ (高速 !)] | [オリジナルページ (最新 ?!)] |
N クイーン問題とは， N × N のおおきさの ``チェス・ボード'' に N 個の クイーンを，たがいにとれない位置に配置する 制約充足問題 です． (ただし，N クイーン問題の解をシステマティックに構成する方法は しられていて，それにしたがえば，解を N に比例する時間でもとめる ことができます.) 8 × 8 という 通常のチェス・ボードのばあいがエイト・クイーン問題です．制約充足 問題のおおくは効率のよい解法がしられていない NP 困難 (NP-hard) な 問題に属しますが，N クイーン問題もそのひとつです． N クイーン問題は人工知能の研究などで，例題としてよく つかわれてきました．
下記のアプレットは，初期状態のままでは動作がある程度目でおえるかたちで N クイーン問題のひとつの解をもとめます．(このアプレットが おおきすぎるときはこのちいさいアプレット をつかえばよいし，ちいさすぎるときはこの おおきいアプレットをつかえばよい.) 初期状態では ``Medium speed (20 rps)'' となっているオプションを ``Full speed'' に変更すれば最高速で 計算できます．(20 rps とは 1 秒間に 20 回 規則を適用する (rps = reductions per second) という意味．ただし， このアプレットにおいては 20 回よりすくなくなる.) ``Restart'' ボタンをおすことによって再度スタートさせることが できます．乱数をつかっているので，そのたびごとにことなる解がもとめられ ますし，計算時間もばらつきます．
[Java アプレットがみえない (実行できない) とき…]
N の値はかえることができます．アプレット上で ``Full speed'' というオプションを選択すれば，N = 20 くらいまでは だいたい数秒で解をもとめることができます．``Variable catalyst rule'' とかかれたオプションを変更すると，使用するプロダクション規則を変更する ことができます．その詳細は文献 [1]にかかれていますし 計算方法のページでもかんたんに 説明していますが， かんたんにいうと，``Single catalyst swapping rule'' はよりせまい範囲の データをみる (つまり局所的な) ので解がもとまるまでの反応回数 (規則の適用回数) がおおくなるのに対して， ``Variable catalyst MOVING rule'' はよりひろい範囲のデータをみる (つまり非局所的な) ので解がもとまるまでの反応回数が すくなくなるということです．もっとも局所的な規則である ``No catalyst swapping rule'' をつかうと，計算は停止しなくなります． (この規則と ``Full speed'' をあわせて選択すると計算をとめることが むずかしくなるので，このくみあわせは禁止しています.)
非局所的な規則をつかってうまく 解をもとめるには，シミュレーテッド・アニーリング (SA) に類似した方法をつかう 必要がでてきます．うえのアプレットでは，SA に類似しているが局所的な 情報だけをつかうフラストレーション蓄積法 (FAM) (文献 [1] または [2]) という方法を つかっています．``Frustration OFF'' (FAM をつかわない) という オプションを選択すると，``Variable catalyst MOVING rule'' のばあいには 解をもとめるのに失敗する (停止しなくなったり，解に到達せずに停止する) 確率がたかくなることがためせます (それでも，N クイーン問題のばあいには 解に到達せずに停止する確率はひくい)．計算が停止したときに解がもとめ られていれば ``MOD = 1'' と表示されますが，この値が 1 よりちいさいときは 解がもとまらないまま停止したことを意味します．
``N Queens problem LOD'' のかわりに ``Sort LOD'' というオプションをえらべば， ならべかえをすることができます (なにがどうならべかえられるかは，ためして みればわかるでしょう)．ここで LOD (Local Order Degree) というのは 局所評価関数のことです．おなじ規則をつかっていても局所評価関数をかえれば ほかの目的につかえるようになるというわけです． ただし，``Variable catalyst MOVING rule'' はソートのためには適していません． うまくソートできないことがわかるでしょう．``Single catalyst swapping rule'' などを選択してください．
CCM にもとづく N クイーン，ならべかえの計算方法に興味があれば，
計算方法のページを参照してください．
(ここでも説明のためにアプレットを使用しています.
)
CCM にもとづく制約充足とくに N クイーン問題の解法をさらにくわしく
しりたければ，文献 [3] をみるとよいでしょう．また，
CCM にもとづくさまざまなソート法についてしりたければ，
文献 [4] をみるとよいでしょう．
古典的な方法 (バックトラックをつかった方法) にもとづいて N クイーン問題をとくアプレットとしては， たとえば Timothy Budd によるものや このページ があります．この古典的な方法は計算時間が N の指数に比例するので N がおおきくなると膨大な計算時間がかかりますが，この方法が すぐれているひとつの点は，すべての解を網羅的に もとめることができるという点です．
注意事項などについては例題 ホームページの「参考文献など」を参照してください．
なお，上記のアプレットの原始プログラムは ここにあります．ただし，このアプレットはローディングの時間を短縮するために オブジェクト指向プログラミングとしては最低のものになっています． つまり，すべてがひとつのクラスのなかにつめこまれています．
作成: 1996-8-25, 改訂: 2015-4-12.