GDD11JP: スライドパズル答案

ええっと特に何も考えていない幅優先探索ですが、一応以下の工夫を加えています。

• 初期状態からと、ゴール状態からの両方向の探索
• オブジェクトの動的生成・破棄コストを減らすために、探査木のノードに同一オブジェクトを使い回し

Phoenom II X4 955 (3.2GHz)、メモリ8GBという環境で、1108/5000問解けています。
(何回かに分けて実行＋途中でプログラム改造しているので、実行時間は測定困難)

ソルバは以下のクラスにより構成されます。

• Board: 単一の盤面を表現するクラス
• Node: 探査木のノード
• NodeList: 探査木の葉からなるリスト
• PuzzleSolver: ソルバ本体

ソースコードは以下。実際に使用したバージョンから若干のリファクタリングを加えており、リファクタリング後はテストしていないのでこのままで動かないかもしれません。

Board.java

public class Board {
    public static int w, h; // 盤面の横サイズ、縦サイズ
    char[] board; // 盤面の状態
    int space_I, space_j; // 空白 (0) の座標
    
    public Board(String board) {
        this.board = board.toCharArray();
        int k = board.indexOf('0');
        this.space_I = k / Board.w;
        this.space_j = k % Board.w;
    }
    public Board(char[] board, int space_i, int space_j) {
        this.board = board;
        this.space_I = space_i;
        this.space_j = space_j;
    }

    public Board clone() {
        return new Board(this.board.clone(), this.space_I, this.space_j);
    }

    // 現在の盤面の文字列表現
    public String signature() {
        return new String(this.board);
    }
  
    // 現在の盤面の表示 (デバッグ用)
    public void show() {
        for(int i = 0; i < Board.h; i++) {
            for(int j = 0; j < Board.w; j++) {
                System.out.print(this.board[i * Board.w + j]);
                if (j != Board.w - 1) {
                    System.out.print(",");
                }
            }
            System.out.println();
    	}
        System.out.println("space: " + this.space_I + ", " + this.space_j);
    }

    // 与えられた移動リストを逆順に適用
    public void batchReverse(char[] list) {
    	for(int i = list.length - 1; i >= 0; i--) {
            char x = list[i];
    	    switch(x) {
    	    case 'L':
    	        this.move(0, 1);
    	        break;
            case 'R':
    	       this.move(0, -1);
    	        break;
    	    case 'U':
    	        this.move(1, 0);
    	        break;
            case 'D':
    	        this.move(-1, 0);
    	        break;
    	    }
    	}
    }
    
    // 1手順進める (移動方向をLRUDの文字で指定)
    public void move(char direction) {
        switch(direction) {
        case 'L':
            this.move(0, -1);
	    break;
        case 'R':
            this.move(0, 1);
            break;
        case 'U':
            this.move(-1, 0);
            break;
        case 'D':
            this.move(1, 0);
            break;
        }
    }

    // 1手順進める (移動方向を縦方向、横方向の差分で指定)
    public void move(int i_delta, int j_delta) {
    	int i_new = this.space_I + i_delta;
    	int j_new = this.space_j + j_delta;
    	
    	char tmp = this.board[i_new * w + j_new];
    	this.board[i_new * w + j_new] = '0';
    	this.board[this.space_I * w + this.space_j] = tmp;
    	this.space_I = i_new;
    	this.space_j = j_new;
    }

    // 現在の盤面から、指定の方向に移動可能かどうかを判別
    public boolean checkMove(int i_delta, int j_delta) {
    	int i_new = this.space_I + i_delta;
    	int j_new = this.space_j + j_delta;
    	
    	if ((i_new < 0) || (i_new >= Board.h) ||
            (j_new < 0) || (j_new >= Board.w)) {
            return false;
       	}
    	if (this.board[i_new * w + j_new] == '=') {
    	    return false;
    	}
    	return true;
    }

    // 現在の盤面から取りうる移動方向を、[L, R, U, D] の形式の配列で取得
    public boolean[] get_actions() {
    	boolean[] actions = new boolean[4];
   	actions[0] = this.checkMove(0, -1); // L
   	actions[1] = this.checkMove(0, 1);  // R
   	actions[2] = this.checkMove(-1, 0); // U
   	actions[3] = this.checkMove(1, 0);  // D
    	return actions;
    }
}

Node.java

public class Node {
    public char[] history;
    public int depth;
    public Board board = null;
	
    public Node() {
        this.history = null;
        this.depth = -1;
    }

    // ノードリストに新しいノードを追加	
    public boolean addNodeToList(NodeList list, char direction) {
        char[] newHistory = new char[this.history.length + 1];
        System.arraycopy(this.history, 0, newHistory, 0, this.history.length);
        newHistory[this.history.length] = direction;
        Board newBoard = this.board.clone();
        newBoard.move(direction);

	return list.enqueue(newHistory, this.depth + 1, newBoard);
    }
}

NodeList.java

package puzzle;

public class NodeList {
    Node[] nodeList; // ノード格納領域
    int startIndex; // nodeList中の先頭ノードのインデックス
    int size; // リストに入っているノード数
	
    public NodeList(int size) {
	this.nodeList = new Node[size];
	for(int i = 0; i < size; i++) {
	    this.nodeList[i] = new Node();
	}
	this.startIndex = 0;
	this.size = 0;
    }
	
    public boolean enqueue(char[] history, int depth, Board board) {
	Node node = null;
	if (this.size == 0) {
	    node = this.nodeList[this.startIndex];
	} else if (this.size == this.nodeList.length) {
	    return false;
	} else {
	    int index = this.startIndex + this.size;
	    if (index >= this.nodeList.length) {
		index -= this.nodeList.length;
	     }
             node = this.nodeList[index];
	}
	node.history = history;
	node.depth = depth;
	node.board = board;
	this.size++;
	return true;
    }
	
    public Node dequeue() {
	Node node = null;
	if (this.size > 0) {
	    node = this.nodeList[this.startIndex];
	    this.startIndex++;
	    if (this.startIndex == this.nodeList.length) {
		this.startIndex = 0;
	    }
	    this.size--;
	}
	return node;
    }
}

PuzzleSolver.java

import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.PrintStream;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class PuzzleSolver {
    Map<String, char[]> reverseSearchMap; // ゴールから逆順の探索結果を、盤面文字列→操作手順の形で格納
	
    public PuzzleSolver() {
        this.reverseSearchMap = new HashMap<String, char[]>();
    }

    // ゴール状態の生成
    public String finalBoard(String initial_board) {
 	StringBuffer buf = new StringBuffer(Board.h * Board.w);
   	int count = 1;
    	for(int i = 0; i < Board.h; i++) {
    	    for(int j = 0; j < Board.w; j++) {
    		if ((i == Board.h - 1) && (j == Board.w - 1)) {
    		    buf.append('0');
    		} else if (initial_board.charAt(i * Board.w + j) == '=') {
    		    buf.append('=');
    		} else if (count <= 9) {
    		    buf.append((char)('0' + count));
    		} else {
    		    buf.append((char)(55 + count));
    		}
   		count++;
   	    }
   	}
    	return buf.toString();
    }

    // 開始状態からの幅優先探索
    public char[] search(String initialBoard, int ttl) {
        Set<String> searched = new HashSet<String>(); // 探索済みの盤面状態
        NodeList nodeList = new NodeList(5000004); // 探索木の葉からなるリスト
        char[] solution = null;
        String finalBoard = this.finalBoard(initialBoard); // ゴール状態の盤面
        nodeList.enqueue(new char[0], 0, new Board(initialBoard));

	boolean stopFlag = false; // nodeListの要素数が上限に達した時点でtrue
	while(nodeList.size > 0) {
	    // 探索キューからのノード取り出し
	    Node node = nodeList.dequeue();
	    if (node == null) {
		System.err.println("cannot get an element from node_list");
		System.exit(1);
	    }

	    // ゴール到達のチェック
	    Board board = node.board;
	    String signature = board.signature();
	    if (signature.equals(finalBoard)) {
		System.out.println("completed!");
		System.out.println("history: " + new String(node.history) + ", depth = " + node.depth);
		board.show();
		solution = node.history;
		break;
            }

	    // 探索済みノードのチェック
	    if (searched.contains(signature)) {
		continue;
	    }
	    searched.add(signature);

	    // ゴール側近隣ノードのチェック
	    if (this.reverseSearchMap.containsKey(signature)) {
		char[] reverseList = this.reverseSearchMap.get(signature);
		board.batchReverse(reverseList);
		System.out.println(board.signature());
		if (board.signature().equals(finalBoard)) {
		    char[] newHistory = new char[node.history.length + reverseList.length];
		    System.arraycopy(node.history, 0, newHistory, 0, node.history.length);
		    for(int i = 0; i < reverseList.length; i++) {
			char xx = reverseList[reverseList.length - i - 1];
			char x = 'X';
			switch(xx) {
			case 'L':
			    x = 'R';
			    break;
			case 'R':
			    x = 'L';
			    break;
			case 'U':
			    x = 'D';
			    break;
			case 'D':
			    x = 'U';
			    break;
		    }
		    newHistory[node.history.length + i] = x;
	        }
		System.out.println("COMPLETED: " + new String(newHistory));
		solution = newHistory;
		break;
	    } else {
		System.err.println("FAILED");
	    }
	}
	
	// 探索深さ限界のチェック
	if (node.depth == ttl || stopFlag) {		
	    continue;
	}

	// 隣接ノードのキューへの追加
	    boolean[] actions = board.get_actions();
	    if (actions[0]) { node.addNodeToList(nodeList, 'L'); }
		if (actions[1]) { node.addNodeToList(nodeList, 'R'); }
		if (actions[2]) { node.addNodeToList(nodeList, 'U'); }
		if (actions[3]) { node.addNodeToList(nodeList, 'D'); }
	    }
            return solution;
	}
	
	// ゴールからの近隣ノード探索
	void genReverse(String initial_board, int ttl) {
	    String finalBoard = this.finalBoard(initial_board);
	    NodeList nodeList = new NodeList(5000004);
	    nodeList.enqueue(new char[0], 0, new Board(finalBoard));

	    boolean stopFlag = false;
	    while(nodeList.size > 0) {
		// キューからの先頭ノード取り出し
		Node node = nodeList.dequeue();
		if (node == null) {
		    System.err.println("cannot get a node from list");
		    System.exit(1);
		}

		if (nodeList.size >= 5000000) {
		    stopFlag = true;
		}

		String signature = node.board.signature();
			
		// 近隣ノード集合に含まれていなければ追加
		if (this.reverseSearchMap.containsKey(signature)) {
		    continue;
		}
		this.reverseSearchMap.put(signature, node.history);

		// 探索深さ限界のチェック
		if (node.depth >= ttl || stopFlag) {
		    continue;
		}
			
		// 隣接ノードのキューへの追加
		boolean[] actions = node.board.get_actions();
		if (actions[0]) { node.addNodeToList(nodeList, 'L'); }
		if (actions[1]) { node.addNodeToList(nodeList, 'R'); }
		if (actions[2]) { node.addNodeToList(nodeList, 'U'); }
		if (actions[3]) { node.addNodeToList(nodeList, 'D'); }
	    }
	}
	
	String solve(String initialBoard, int ttl, int ttl_reverse) {
	    this.genReverse(initialBoard, ttl_reverse);
		
	    char[] result = this.search(initialBoard, ttl);
	    if (result != null) {
		StringBuffer buf = new StringBuffer(result.length);
		for(char x: result) {
		    buf.append(x);
		}
	        return buf.toString();
	    }
	    return null;
	}

	public static void main(String[] args) {
	    int id = Integer.parseInt(args[0]);
            Board.w = Integer.parseInt(args[1]);
	    Board.h = Integer.parseInt(args[2]);
	    String initialBoard = args[3];
	    int ttl = Integer.parseInt(args[4]);
	    int ttl_reverse = Integer.parseInt(args[5]);

	    PuzzleSolver puzzle = new PuzzleSolver();
	    String result = puzzle.solve(initialBoard, ttl, ttl_reverse);
	    if (result == null) {
		System.out.println("cannot solve");
	    } else {
		System.out.println("solution = " + result);
	    try {
                FileOutputStream f = new FileOutputStream("log.txt", true);
		PrintStream fout = new PrintStream(f);
	        fout.println("" + id + "," + result);
	        fout.close();
	    } catch (FileNotFoundException e) {
		e.printStackTrace();
	    }
	}
    }
}