「レイトン教授」というのはNintendo DS向け“頭の体操”ゲームのシリーズ名。すでに3作リリースされてる。
レイトン教授ってなによ? - Life Goes On で解かれてしまった ;-)
同じような枝刈りには行き着いていたんだけど……ということで、javascript版。
あ、これはa-a'から先に探索しているけど、ちょっと変えればc-c'から探索するようにできると思う。
(追記)後の自分が分からなくならないように、コードのことを書いておこう。
function Node(name) { this.name = name; this.nextNodes = []; this.link = function(node) { if (node.nextNodes) { this.nextNodes.push(node); node.nextNodes.push(this); } } this.toString = function() { /* snip */ } }
Node型を定義したけど、逆に面倒くさくなったかも。初期化とかが。
function State() { this.ways = []; // snip this.getNextStates = function() { for (var i in this.ways) { if (!this._reachable(i)) return []; } for (var i in this.ways) { if (this._reached(i)) continue; var way = this.ways[i]; var current = way[way.length - 1]; var result = []; for (var j in current.nextNodes) { var next = current.nextNodes[j]; if (this._visited(next)) continue; result.push(this._move(i, next)); } return result; } returun []; } // snip }
盤面の探索状況をあらわすState型と、次の盤面候補を返すgetNextStates関数。waysは色ごとのNode配列(ジャグ配列)。ここには書いてないけど、開始ノードの配列 starts と、終了ノードの配列 goals の2つをState.prototypeにセットしておく必要がある。
var model = { initialized: false, count: 0, nodes: [], states: null, state: null, removeState: null, addState: null, ready: function() { this.state = this.removeState(); this.count++; }, go: function() { var nextStates = this.state.getNextStates(); for (var i in nextStates) { this.addState(nextStates[i]); } } }
モデル。後で初期化するフィールドをここで定義することには意味がないんだけど、IDEのために一応書いておいた。ready と go を繰り返し呼び出すことで探索する(関数名がひどいし、よく考えたら2関数に分ける必然性はなかったな)。statesとaddStateとremoveStateは外から注入するのだけど、ここをスタックにすればDFSだし、キューにすればBFS。