Kawa.netxp [JavaScript] Nクイーン問題（ノンプリエンプティブマルチタスク風）

有名な Nクイーン問題を解く JavaScript です。 アルゴリズムは、単純なバックトラックのみです。
ブラウザの動作をロックせずに、 処理状況をアニメーション表示させている点がミソです。
ノンプリエンプティブマルチタスク風に定期的に処理をブラウザ側に返すようにクラスを組むことで、 複数の処理を並列動作させる習作です。
盤の大きさ（デフォルトは8マス＝8クイーン問題）を入力して、[開始] ボタンを押して下さい。

盤の大きさ： マス  

0 個の解を検出しました。

[開始] ボタンを押して下さい。

アルゴリズム

深さ優先で、単純なバックトラックのみを使用しています。
また、再帰呼び出しもせずに、ぐるぐるループしています。
とりあえずなので、解の回転／反転すら使っていません。
試してませんが、JavaScript でビットマックを作ってマッチングさせると遅くなりそうですね。
上下反転くらいなら遅くならないけど、アニメーションが楽しいので未実装です。

JavaScript のソースで NQueens クラスと QBoard クラスが分離してあるのは、 NQueens クラス以外のアルゴリズムを実装したときに QBoard クラスを汎用利用できるようにしようと思っていたためです。
現在の NQueens クラスと QBoard クラスの組み合わせでは、 上下左右の効き筋チェックやコマ位置記憶など、冗長な部分があります。

総当りではなくてもっともっとエレガントに N クイーン問題を解く方法は、 takaken さんの「コンピュータ＆パズル」というページの Ｎクイーン問題（解の個数を求める） が詳しく、分かりやすいです。

ロックしないJavaScript

JavaScript は、処理中はブラウザがロックされて ユーザは何も操作ができません。 JavaScript の処理が優先されるので、 前時代的なシングルタスク＋タスク切替えのようなものです。 JavaScript 内で DOM 操作を行ってページ内容を更新していても、 全ての処理が終了するまで、画面表示には反映されません。

時間のかかるアルゴリズムを処理する場合は、 定期的にブラウザに処理を返して ノンプリエンプティブなマルチタスクを実現する必要があります。 

NQueens.prototype.next = function () {
    if ( this.stopflag ) return;
    var copy = this;
    var func = function(){
        copy.loop();
    };
    setTimeout( func, 1 );
};

今回の NQueens クラスでは上記のような内容の next() メソッド（実際のコードは少し違う）を用意して、 時間のかかる関数の処理中に return this.next(); と書くことで JavaScript を中断して、ブラウザに処理を返しています。 このタイミングで画面も描画され、ブラウザのメニュー等も利用可能になります。

1ミリ秒後には、再びタイマー割り込みで loop() メソッドの処理を再開します。 ループの状況などは、インスタンス内で管理しておく必要があります。

あんまり頻繁に next() メソッドを呼んでいると その度に 1ミリ秒ずつ待ってしまって遅くなるので、 適当な間隔を開けて呼び出す必要があります。 

NQueens.prototype.stop = function () {
    this.stopflag = true;
};

というメソッドも用意してあるので、 この stop() メソッドを呼ぶだけで タスクの動作をクラスの外部から停止することができます。

並列処理で解いてみる

試しに4クイーン〜9クイーン問題を並列で解いてみます。

4クイーン：   5クイーン：   6クイーン：   7クイーン：   8クイーン：   9クイーン：  
           

ブラウザの CPU 利用率は 100％近くになりますが、 ループでなくてノンプリエンプティブマルチタスク風に処理しているため、 ブラウザの操作はロックされません。

コメントはこちらへ by AjaxCom

その他のページへのリンク

このページへのトラックバック by AjaxTB

トラックバックURL：http://www.kawa.net/service/tb/ajaxtb.cgi/works/js/8queens/nqueens.html

Kawa.netxp © Copyright 2006 Yusuke Kawasaki