八数码难题——bfs(java)

八数码难题——bfs(java)

编号为1～8的8个正方形滑块摆成3行3列(有一个格式留空），如图所示。每次可以把与空格相邻的滑块（有公共边才算相邻）.移动到空格中，而它原来的位置就成舍了新的空格。给定葫始高面和目标局面（用0表示空格），你的任务是计算出最少的移动步数。如果无法到达局面，则输出-1。
样例输入：

2 6 4 1 3 7 0 5 8 
8 1 5 7 3 6 4 0 2

代码实现：

import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class eight_Digital {
	static int[] goal = new int[9];//目标状态数组
	static int[] fa = new int[1000000];//”父亲“编号数组
	static int[] dist = new int[1000000];//距离数组
	static int[][] st = new int[1000000][9];//过程状态数组
	static int dx[] = {-1,1,0,0};
	static int dy[] = {0,0,-1,1};
	static Set vis = new HashSet();//存放没一步结果，防止回到原来已经走过的路。
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		//3*3样例
		// 2 6 4 1 3 7 0 5 8  初始
		// 8 1 5 7 3 6 4 0 2  goal
		for (int i = 0; i < 9; i++) {
			st[1][i] = sc.nextInt();
		}	
		for (int i = 0; i < 9; i++) {
			goal[i] = sc.nextInt();
		}
		int v=0;
		for (int i = 0; i < 9; i++) v=v*10+goal[i];
		vis.add(v);//add goal
		int ans = bfs();// 分析之后，使用宽度搜索更合适
		if(dist[ans]>0) {
			System.out.println("最小步数：");
			System.out.println(dist[ans]);
			System.out.println(fa[ans]);}
		else 
			System.out.println(0);
		System.out.format("33[32;4m移动如下：%n");//%n表示换行
		
		int[][] process = new int[dist[ans]+1][9];    //本来dist[ans]为所需的步数，
													//我们第process[0][9]放起始状态，方便构造
		print(process,ans);
		
	}
	
	private static void print(int[][] process,int ans) {		
		int i=dist[ans]+1;
		while(true) {		
			process[--i] = st[ans];
			if(ans==1)
				break;
			ans = fa[ans];
		}
		for (int j = 0; j < process.length; j++) {
			System.out.format("33[32;4m第"+j+"步：%n");	
			for (int j2 = 0; j2 < 9; j2++) {
				System.out.print(process[j][j2]+"t");
				if(j2==2||j2==5) 
					System.out.println();	
			}
			System.out.println();
		}
		
	}

	private static int bfs() {
		init_lookup_table();
		int front=1,rear=2;
		
		while(front=0&&newx<3&&newy>=0&&newy<3) {
					for (int i = 0; i <9; i++) 
						st[rear][i] = s[i];
					
					st[rear][newz] =s[z];//每次只有两个位置改变
					st[rear][z] = s[newz];
					
					dist[rear] = dist[front]+1;//再栈首的基础上加一
					
					fa[rear] = front;//给任意一个 fornt，都能fornt = fa[fornt],构造过程
					if(try_to_insert(rear)==1) rear++;
				}//end if
			}// end for
			front++;
		}//end while
		return 0;
	}

	private static void init_lookup_table() {
		vis.clear();
		for (int i = 0; i < 1000000; i++) {
			dist[i] = 0;	
		}
		
	}

	private static int try_to_insert(int rear) {
		int v=0;
		for (int i = 0; i < 9; i++) v=v*10+st[rear][i];
		if(vis.contains(v)) return 0;
		vis.add(v);
		return 1;
		
	}

}

结果：


… and so on