AOJ0190 Eleven Puzzle

問題リンク Eleven Puzzle

• 解法

素直に20ステップまで幅優先探索を行うと状態数が多すぎて死んでしまいます。
なので両側探索を使いました。
ゴールの状態から20の半分の10ステップ以内で辿りつける状態を予め調べておきます。これをmとします。
そして、与えられた初期状態から10ステップ分幅優先探索をします。この探索中で得られたパズルの状態がmに含まれていたら、初期状態からのステップ数+mの値でゴールにたどり着けることが分かります。逆に初期状態から10ステップで辿りつける状態全てがmに含まれていなかったらどう頑張っても20ステップ以内にゴールできません。

次に自分がどうパズルの状態を管理したかを説明します。
まず、パズルのマスに上から番号付けを行います。0〜12までのインデックスが付けられます。そしてそこにはまっているピースはcharの文字で表現します。空きマスは'0'で、数字が入っていたらA〜Kで表します。パズルのある状態は長さ13の文字列で表現するということです。例えば、ゴールの状態は"0ABCDEFGHIJK0"となります。
ピースを動かすという処理を簡単にするために、どの番号のマスはどこの番号と隣接しているかを表す情報を作っておくと楽だと思います。2番のマスは{0,1,3,6}のマスと隣接している...etc

• ソース

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;

//Eleven Puzzle
public class AOJ0190 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int[][] adj = {
				{2},
				{2,5},
				{0,1,3,6},
				{2,7},
				{5},
				{1,4,6,9},
				{2,5,7,10},
				{3,6,8,11},
				{7},
				{5,10},
				{6,9,11,12},
				{7,10},
				{10}
		};
		final String g = "0ABCDEFGHIJK0";
		Map<String, Integer> m = new HashMap<String, Integer>();
		List<String> l = new ArrayList<String>();
		int step = 1;
		l.add(g);
		m.put(g, 0);
		while(!l.isEmpty()&&step<=10){
			List<String> next = new ArrayList<String>();
			for(String s:l){
				char[] c = s.toCharArray();
				for(int i=0;i<13;i++){
					if(c[i]=='0'){
						for(int j=0;j<adj[i].length;j++){
							char u = c[adj[i][j]];
							c[adj[i][j]] = '0';
							c[i] = u;
							String n = new String(c);
							if(!m.containsKey(n)){
								m.put(n, step);
								next.add(n);
							}
							c[adj[i][j]] = u;
							c[i] = '0';
						}
					}
				}
			}
			step++;
			l = next;
		}
		while(true){
			int p = sc.nextInt();
			if(p==-1)break;
			char[] cc = new char[13];
			cc[0] = p==0?'0':(char)(p-1+'A');
			for(int i=1;i<13;i++){
				p = sc.nextInt();
				cc[i] = p==0?'0':(char)(p-1+'A');
			}
			String st = new String(cc);
			l = new ArrayList<String>();
			step = 0;
			l.add(st);
			String ans = "NA";
			Set<String> set = new HashSet<String>();
			while(!l.isEmpty()&&step<=10){
				List<String> next = new ArrayList<String>();
				for(String s:l){
					if(m.containsKey(s)){
						ans = (step+m.get(s))+"";
						next.clear();
						break;
					}
					char[] c = s.toCharArray();
					for(int i=0;i<13;i++){
						if(c[i]=='0'){
							for(int j=0;j<adj[i].length;j++){
								char u = c[adj[i][j]];
								c[adj[i][j]] = '0';
								c[i] = u;
								String n = new String(c);
								if(!set.contains(n)){
									set.add(n);
									next.add(n);
								}
								c[adj[i][j]] = u;
								c[i] = '0';
							}
						}
					}
				}
				step++;
				l = next;
			}
			System.out.println(ans);
		}
	}
}