配置チェックプログラムの動作確認

オライリー・ジャパンの「アルゴリズム・クイックリファレンス」　P213 に記載されている 幅優先探索プログラムの一部を変更して、ゴール可能な配置と不可能な配置を全て確認します。

ゴール可能な配置を確認する場合、ゴールの配置を初期配置として、そこから１つずつ移動させてゴール可能な全パターンを確認します。

同様に、不可能な配置の場合は、ゴールの配置で１と2を入れ替えた以下の配置を初期配置として、ゴール不可能な全パターンを確認します。

サンプルプログラムの実行結果は以下のようになり、3x3（8パズル）ではゴール可能な全配置が181440通りで、その配置全てで、 GoalCheckerクラスによる判定は、全てゴール可能になりました。 また、同様にゴール不可能な全配置は181440通りで、GoalCheckerクラスによる判定は全てゴール不可能になりました。

Initial: Node  Board:
  1  2  3             ← 初期配置（ゴール可能）
  4  5  6
  7  8  0
closed: 181440       ← 調べた重複しないゴール可能な配置の数
Possible:  181440    ← GoalCheckerで判定したときのゴール可能な数
Impossibe: 0           ← GoalCheckerで判定したときのゴール不可能な数

Initial: Node  Board:
  2  1  3             ← 初期配置（ゴール不可能）
  4  5  6
  7  8  0
closed: 181440       ← 調べた重複しないゴール不可能な配置の数
Possible:  0            ← GoalCheckerで判定したときのゴール可能な数
Impossibe: 181440   ← GoalCheckerで判定したときのゴール不可能な数

プログラムの実行結果のゴール可能と不可能な配置の数を合計すると　362880（181440 + 181440)通りになります。 これは以下の計算した3x3の全配置数と一致します。同様にサンプルプログラムで、2x3や2x4のケースを求めても計算値と一致しました。

4x4（15パズル）や5x5などでは、配置数が多すぎてプログラムを実行すると Out Of Memory Error が起こり、完了できません。 そのため、手動でゴール可能と不可能な配置を数個試し、それらでは正しく判定することを確認しただけです。

public class SlidelGoalCheck {

    public static void main(String[] args) {
        SlidelGoalCheck sgc = new SlidelGoalCheck();
        sgc.test();
    }

    private INodeSet impossible =  StateStorageFactory.create(OpenStateFactory.TYPE.HASH);
    private int countPossible;
    private int countImpossible;
    private SlideGameManager manager;
    
    /**
     * Constructor
     * 
     */
    public SlidelGoalCheck() {
        // 3x3以上の場合は、Out of Memory Error になりやすいので注意すること
        int maxPx = 3;
        int maxPy = 3;
        manager = new SlideGameManager(maxPx, maxPy);
    }
    
    /**
     * ゴール可能な配置、不可能な配置の全てで、GoalCheckerが
     * 正しく判定しているかを確認する
     * 
     */
    public void test() {
        // ゴール可能な配置全てをチェックする
        INode initial = new NodeSlideGame(manager.cloneGoalBoard());
        countPossible = 0;
        countImpossible = 0;
        breadthFirst(initial);
        
        // ゴール不可能な配置全てをチェックする
        Board goal = manager.cloneGoalBoard();
        goal.setNumber(0, 0, 2);
        goal.setNumber(1, 0, 1);
        initial = new NodeSlideGame(goal);
        countPossible = 0;
        countImpossible = 0;
        breadthFirst(initial);
    }
    
    /**
     * オライリー・ジャパンの「アルゴリズム・クイックリファレンス」　P213 に記載されている
     * 幅優先探索を一部変更したもの。
     * 
     * @param initial 初期配置
     */
    public void breadthFirst(INode initial) {
        GoalChecker checker = new GoalChecker();
        
        // 初期状態から始める
        INodeSet open = StateStorageFactory.create(OpenStateFactory.TYPE.QUEUE);
        open.insert(initial.copy());
        
        // すでに訪問した状態
        INodeSet closed =  StateStorageFactory.create(OpenStateFactory.TYPE.HASH);

        while (! open.isEmpty()) {
            INode n = open.remove();
            closed.insert(n);
            
            // 次の手はすべて、オープン状態に追加されている。
            DoubleLinkedList<IMove> moves = n.validMoves();

            for (Iterator<IMove> it = moves.iterator(); it.hasNext();) {
                 IMove move = it.next();
                
                // 盤面状態の集合を保守するために、コピーの上で手を実行する。
                INode successor = n.copy();
                move.execute(successor);

                // 訪問済みなら、この状態はもう探索しない
                if (closed.contains(successor) != null) {
                    continue;
                }
                open.insert(successor);
            }
        }
        
        Iterator i = closed.iterator();
        while (i.hasNext()) {
            INode n = (INode) i.next();
            checkGoal(checker, n);
        }
        
        System.out.println("Initial: " + initial
                + "closed: " + closed.size()
                + "\nPossible:  " + countPossible
                + "\nImpossibe: " + countImpossible
                + "\n"
                );
    }
    
    private void checkGoal(GoalChecker checker, INode node) {
        Board board = ((NodeSlideGame) node).cloneBoard();
        if (checker.isPossibleGoal(board) == false) {
            countImpossible ++;
        } else {
            countPossible ++;
        }
    }
}

修正.　2012.3.30　メソッド breadthFirst の　INodeSet open　の定義部分が間違っていましたので修正

	// 初期状態から始める
	INodeSet open = StateStorageFactory.create(OpenStateFactory.TYPE.STACK);

	// 初期状態から始める
	INodeSet open = StateStorageFactory.create(OpenStateFactory.TYPE.QUEUE);