スライドパズルの配置チェックプログラム

最終更新日: 2012年 3月15日

HomeBack

  1. Javaのサンプルプログラムについて
  2. サンプルソース

スライドパズルの配置の判定方法 のサンプルプログラムです。

Javaのサンプルプログラムについて

3x3(8パズル)や4x4(15パズル)だけでなく、3x2や、4x5などの縦横のマス目がそろっている長方形型(?)のスライドパズルで、現在の配置からゴールすることが可能か不可能かをチェックするプログラムのサンプルです。 このサンプルプログラムではBoardというクラスを利用しています。

サンプルソース

public class GoalChecker {

    public GoalChecker() {
    }

    /**
     * 与えられたBoardの配置が解ける場合は true を返す
     * 
     * @param board
     * @return true: ゴールに至る
     */
    public boolean isPossibleGoal(Board board) {
        int maxPx = board.getMaxPx();
        int maxPy = board.getMaxPy();
        int maxNum = maxPx*maxPy;

        List<Integer> list = getNumberList(board);

        // E.g.  3x3 => 1,2,3, 6,5,4, 7,8
        //       4x4 => 4,3,2,1, 5,6,7,8, 12,11,10,9, 13,14,15 
        int expectNum;
        
        // 1 から1つずつ増えていく
        // E.g.  3x3 =>  0, 1, 2, 3, 4, 5, 6, 7
        int index = 0;
        
        int moveCount;
        int totalMoveCount = 0;
        
        // 行が左から始まる場合は true
        //  E.g. 3x3で 1行目は true、2行目は false、3行目はtrue
        boolean isLeftStart;
        Integer value;

        for (int py = 0; py < maxPy; py ++) {
            if ((maxPy + 1 + py) % 2 == 0) {
                isLeftStart = true;
            } else {
                isLeftStart = false;
            }
            for (int px = 0; px < maxPx; px ++) {
                if (isLeftStart) {
                    expectNum = index + 1;
                } else {
                    expectNum = maxPx*(py + 1) - px;
                }

                // チェックしている数字のゴールの位置と、現在の位置の間にある数字の数を
                // 求めて moveCount にセットする。
                // E.g. リストが[1,3,6,2,5,4,7,8]のとき、現在2がある位置と、ゴールのときに
                // 2があるべき位置の間は2(間に3, 6 の2個ある) なので、moveCount = 2
                moveCount = -1;
                for (int j = index; j < maxNum - 1; j ++) {
                    value = list.get(j);
                    if (value == expectNum) {
                        moveCount = j - index;
                        break;
                    }
                }
                if (moveCount < 0) {
                    throw new RuntimeException("invalid data  moveCount: "
                            + moveCount + "  index: " + index + "  expectNum: "
                            + expectNum + "  list:" + list);
                }

                if (moveCount > 0) {
                    totalMoveCount += moveCount;
                    list = move(list, index, moveCount);
                }
                index ++;
                if (index >= maxNum - 1) {
                    // pxとpyの2つのループを抜けてtotalMoveCountをチェックする
                    py = maxPy;
                    break;
                }
            }
        }
        if (totalMoveCount % 2 == 0) {
            return true;
        } else {
            return false;
        }
    }
    
    /**
     * リストの中の、引数(index と moveCount)で指定した位置の数字を移動させ、
     * その移動済みのリストを返す
     * 
     * E.g.
     *   引数のリストが[1,3,6,2,5,4,7,8] で、index = 1, moveCount = 2 の場合
     *   index + moveCount = 1 + 2 = 3 なので、
     *   list.remove(3) となり、 listは [1,3,6,   5,4,7,8] になる。
     *   list.add(1, 2) となり 、listは [1,2,3,6,5,4,7,8] となる。
     *    
     * @param list
     * @param index  リストの基準となる位置(0, 1, 2, ・・・・)
     * @param moveCount リストで左側に飛び越す数字の数
     * @return 数字を移動させたリスト
     */
    private List<Integer> move(List<Integer> list, int index, int moveCount) {
        if (moveCount == 0) {
            return list;
        }
        Integer number = list.remove(index + moveCount);
        list.add(index, number);
        return list;
    }

    /**
     * Board の配置から一筆書きのようにしてマス目をチェックして数列を求め、リストにして返す。
     * ただし、ゴールの配置で右下のカドが最後になるような順番でマス目をチェックする
     *  E.g 
     *   -------
     *   |1|2|3|   3x3のゴールの配置の場合
     *   |4|5|6|   これから得られる数列は [1,2,3, 6,5,4, 7,8]
     *   |7|8| |
     *   -------
     *   
     *   -------
     *   |1|2|3|   3x2のゴールの配置の場合
     *   |4|5| |   これから得られる数列は [3,2,1, 4,5]
     *   -------
     *   
     * @param board
     * @return 配置から得られたリスト
     */
    private List<Integer> getNumberList(Board board) {
        int maxPx = board.getMaxPx();
        int maxPy = board.getMaxPy();
        list = new LinkedList<Integer>();
        
        int index = 0;
        int number;
        
        // 行の開始が左から始まる場合は true
        boolean isLeftStart;
        for (int py = 0; py < maxPy; py ++) {
            // maxPyが奇数の場合、1行目は左から始める
            // 偶数の場合は、右から始まり、右下のカドが
            // 最後になるようにする
            if ((maxPy + 1 + py) % 2 == 0) {
                isLeftStart = true;
            } else {
                isLeftStart = false;
            }

            for (int px = 0; px < maxPx; px ++) {
                if (isLeftStart) {
                    number = board.getNumber(px, py);
                } else {
                    number = board.getNumber((maxPx - 1) - px, py);
                }
                if (number != Board.TILE_EMPTY) {
                    list.add(number);
                }
                index ++;
            }
        }
        return list;
    }
}			


HomeBack