Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: 0, Size: 0

Question

I am trying to write a program which can solve the 8-Puzzle problem.I am using the A* algorithm to find the solution. I have reviewed my code many times and also tried making some changes. Even my friends tried to help me find the bug,but they couldn't. I still don't understand where i went wrong.I used javadocs to see if I did something wrong,even that din't solve my problem. I have created three classes to solve this problem.

import java.util.*;
public class Solver implements Iterable<State>
{
    ArrayList<State> queue,solQueue;
    public int sol[][] = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 0 } };
    int temp[][],i;
    int moves;
    int leastPriority,removeIndex;
    State removeTemp;
    public Solver(State initial)
    {
        queue = new ArrayList<State>();
        solQueue = new ArrayList<State>();
        queue.ensureCapacity(16);
        solQueue.ensureCapacity(16);
        temp = new int[3][3];
    i=1;
    leastPriority = 100;
    removeTemp=initial;
    queue.add(removeTemp);
    Iterator<State> qu = queue.iterator();
    while(removeTemp.m!=sol)
    {
        leastPriority = 100;
        i=0;
        queue.iterator();
        for (State s : queue) 
        {
            if((s.mh + s.count) <leastPriority)
            {
                leastPriority = (s.mh + s.count);
                removeIndex = i;
            }
            if(qu.hasNext())
                i++;
        }
        for(State s : removeTemp.neighbours() )
        {
            queue.add(s);
        }
        removeTemp=queue.remove(removeIndex);
        solQueue.add(removeTemp);
    }
    this.moves();
    this.solution();
}
public int moves() 
{
    System.out.print("Solution found out in "+ moves+" moves");
    moves = removeTemp.count;
    return moves;
}
public Iterable<State> solution() 
{
    for(State s : solQueue)
    {
        System.out.println(s.m);
        System.out.println("");
    }
    return solQueue;
}
@SuppressWarnings({ "unchecked", "rawtypes" })
@Override
public Iterator iterator() {
    return null;
}
}

And the JVM is throwing an exception.

     Exception in thread "main" java.lang.IndexOutOfBoundsException: Index:  0,Size: 0
     at java.util.ArrayList.rangeCheck(Unknown Source)
     at java.util.ArrayList.get(Unknown Source)
     at Solver.<init>(Solver.java:41)
     at Main.main(Main.java:13)

What i don't understand is that how can the size of the ArrayList be 1 when i have explicitly state it as 16.

The State Class has the heuristic function which is suppose to make the algorithm efficient.The following is the State Class.

  import java.util.ArrayList;
  import java.util.Iterator;

  public class State implements Iterable<State>
  {
   public int sol[][] = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 0 } };
   int m[][], bi, bj, count, priority, si, sj;
   int i,j,tempm[][];
   int mh = 0;
   boolean isInitialState, isRepeatedState;
   State previousState, tempState;
   ArrayList<State> neighbourStates;

   public State(State s, int c, int[][] array) 
{
    neighbourStates = new ArrayList<State>();
    neighbourStates.ensureCapacity(16);

    tempState =this;
    m = new int[3][3];
    m=array;

    if (s == null) 
    {
        isInitialState = true;
        count = 0;
        previousState =null;
    } 
    else 
    {
        previousState = s;
        count = c+1;
    }

    this.findZero();
    this.manhattanHeuristic();
}

private void findZero() 
{
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++)
        {
            if(m[i][j]==0)
            {
                bi=i;
                bj=j;
            }
        }
}

private void manhattanHeuristic() {
    int n = 1;
    mh = 0;
    for (int i = 0; i < 3; i++)
        Z: for (int j = 0; j < 3; j++) {
            if ((i == bi) && (j == bj)) {
                continue Z;
            }

            else if (m[i][j] == n) {
                n++;
            }

            else {
                this.getSolutionIndex();
                mh = mh + Math.abs(i - si) + Math.abs(j - sj);
            }

        }
}

void getSolutionIndex() {
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++) {
            if (m[i][j] == 0) {
                si = i;
                sj = j;
            }
        }

}

public Iterable<State> neighbours()
{
    tempm = m;
    this.up();
    if(!(equals(tempm)))
    {
        tempState = new State(this,count,tempm);
        neighbourStates.add(tempState);
    }

    this.down();
    if(!(equals(tempm)))
    {
        tempState = new State(this,count,tempm);
        neighbourStates.add(tempState);
    }

    this.left();
    if(!(equals(tempm)))
    {
        tempState = new State(this,count,tempm);
        neighbourStates.add(tempState);
    }

    this.right();
    if(!(equals(tempm)))
    {
        tempState = new State(this,count,tempm);
        neighbourStates.add(tempState);
    }

    return neighbourStates;     

}

public boolean equals(int s[][])
{
    if((isInitialState==false)&&(previousState.m == s))
        return true;
    else
        return false;

}

@Override
public Iterator<State> iterator() {
    // TODO Auto-generated method stub
    return null;
}

public void up()
{
    if ((bi > 1) && (bi < 2) && (bj < 3)&& (bj > 1))
    {
        i = bi;
        i = i + 1;
        this.move(i,bj);
    }

}

public void  down()
{
    if ((bi > 2) && (bi < 3) && (bj < 3) && (bj > 1)) 
    {
        i = bi;
        i = i - 1;
        this.move(i,bj);
    }
}

public void left()
{
    if ((bi > 1) && (bi < 3) && (bj < 2)&& (bj > 1)) {
        j = bj;
        j = j + 1;
        this.move(bi, j);
    }
}

public void right()
{
    if ((bi > 1) && (bi < 3) && (bj < 3) && (bj > 2)) {
        j = bj;
        j = j - 1;
        this.move(bi, j);

    }

}

public void move(int x, int y) {
    {
        tempm = m;
    }
    if ((tempm[x + 1][y] == 0) || (tempm[x - 1][y] == 0) || (tempm[x][y + 1] == 0)|| (tempm[x][y - 1] == 0)) {
        tempm[bi][bj] = tempm[x][y];
        tempm[x][y] = 0;
        bi = x;
        bj = y;



    }
}

}

And the finally the class with the main function.

  import java.util.Scanner;
  public class Main {
  public static void main(String[] args) 
  {
     @SuppressWarnings("resource")
     Scanner sc = new Scanner(System.in);
     int[][] tiles = new int[3][3];
     System.out.println("Enter the elements");
     for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++)
            tiles[i][j] = sc.nextInt();
     State initial = new State(null,0,tiles);
     Solver solver = new Solver(initial);
     solver.solution();

     System.out.println("Minimum number of moves = " + solver.moves());

     }

}

Answer 1

please try the below code in Solver.java

if(!queue.isEmpty()) removeTemp=queue.remove(removeIndex); else break;

Answer 2

What i don't understand is that how can the size of the ArrayList be 1 when i have explicitly state it as 16.

You did not set the size of the ArrayList to 16. You've set the capacity:

queue.ensureCapacity(16);
solQueue.ensureCapacity(16);

This does not make the ArrayList have a size of 16.

An ArrayList has an array to hold its data. When you add more elements to the ArrayList and its internal array is full, it will have to allocate a larger array and copy the content of what it currently holds plus the new element.

The capacity of the ArrayList is the minimum size that the internal array has. You can use ensureCapacity to make sure that the ArrayList doesn't have to resize too often (resizing and copying the content is an expensive operation). So, ensureCapacity is a call you make to make it work effiently.

It does not make the ArrayList have 16 elements; it only makes sure that the ArrayList has room for at least 16 elements.

If you want the ArrayList to have 16 elements, you'll have to add those elements one by one.

Answer 3

Size of the collection and the capacity are 2 different concepts.

• capacity represents the maximum size of items a collection can hold without a reallocation.
• size represents the current number of items in the collection.

IndexOutOfBoundsException is saying that you are trying to access an item with index that does not exist in the collection.