最終更新日: 2012年 3月15日
スライドパズルの配置の判定方法 のサンプルプログラムです。
3x3（8パズル）や4x4（15パズル）だけでなく、3x2や、4x5などの縦横のマス目がそろっている長方形型（？）のスライドパズルで、現在の配置からゴールすることが可能か不可能かをチェックするプログラムのサンプルです。 このサンプルプログラムではBoardというクラスを利用しています。
サンプルプログラムでは、Boardというクラスを利用しています。このBoardは配置情報を内部にもつクラスで、メソッド getNumber(x, y) で指定の位置の番号を取り出せます。
また、メソッドgetMaxPx()で横のマス目の数を、getMaxPy()で縦のマス目の数を取得できます。
board.getMaxPx() => 3 board.getMaxPy() => 4 getNumber(0, 0) が左上のカドの番号を返し、 getNumber(2, 3) が右下のカドの番号を返します。
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 から１つずつ増えていく
// 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の２つのループを抜けて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;
}
}