尝试使用java队列解决8个难题
我试图解决8字谜问题,首先将电路板添加到队列中,然后以最小汉明距离将一个状态退出队列。我有相应的函数,但我无法找到它们是否有效,因为我在第26行得到了一个空指针异常
package ai8puzzle;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
/**
*
* @author Dell Inspiron
*/
public class My8Puzzle {
static int[] board={0,1,3,4,2,5,7,8,6};
static int[] goal={1,2,3,4,5,6,7,8,0};
public static void main(String[] args){
int h;
h = CalcHamming(board, goal);
int prev_h = getHole();
PriorityQueue<int[]> q = null;
int[] b= {0,1,3,4,2,5,7,8,6};
q.add(b); //null pointer exception here
while(h!=0){
ArrayList<int[]> g;
g = genSuccessors();
for (int i=0; i<g.size(); i++){
if(!q.contains(g.get(i)))
q.offer(g.get(i));
}
System.out.println("board: "+Arrays.toString(q.poll()));
}
}
public static ArrayList<int[]> genSuccessors()
{
ArrayList<int[]> successors = new ArrayList<>();
int hole = getHole();
// try to generate a state by sliding a tile leftwise into the hole
// if we CAN slide into the hole
if (hole != 0 && hole != 3 && hole != 6)
{
/*
* we can slide leftwise into the hole, so generate a new state for
* this condition and throw it into successors
*/
swapAndStore(hole - 1, hole, successors);
}
// try to generate a state by sliding a tile topwise into the hole
if (hole != 6 && hole != 7 && hole != 8)
{
swapAndStore(hole + 3, hole, successors);
}
// try to generate a state by sliding a tile bottomwise into the hole
if (hole != 0 && hole != 1 && hole != 2)
{
swapAndStore(hole - 3, hole, successors);
}
// try to generate a state by sliding a tile rightwise into the hole
if (hole != 2 && hole != 5 && hole != 8)
{
swapAndStore(hole + 1, hole, successors);
}
return successors;
}
/*
* Switches the data at indices d1 and d2, in a copy of the current board
* creates a new state based on this new board and pushes into s.
*/
public static void swapAndStore(int d1, int d2, ArrayList<int[]> s)
{
int[] cpy = copyBoard(board);
int temp = cpy[d1];
cpy[d1] = board[d2];
cpy[d2] = temp;
s.add(cpy);
}
public static int[] copyBoard(int[] state)
{
int[] ret = new int[9];
System.arraycopy(state, 0, ret, 0, 9);
return ret;
}
private static int CalcHamming(int[] b, int[] g) {
int h=0;
for(int j=0; j<9; j++){
if(b[j]!=g[j]){
h++;
}
}
return h; //To change body of generated methods, choose Tools | Templates.
}
private static int getHole() {
int h=0;
for(int j=0; j<3; j++){
if(board[j]==0){
h=j;
}
}
return h;
}
}
任何帮助都将不胜感激
# 1 楼答案
在向其添加元素之前,必须初始化
PriorityQueue<int[]> q
:如果
PriorityQueue
是一个接口,则必须使用兼容的实现进行初始化