project01.java

8puzzle game by Java This program can automatically solve 8 puzzle games with Manhattan approach

    }
//---------------------------------------------------------------------------------
    public int[] up() { return up(pieces);}
//---------------------------------------------------------------------------------
    public int[] down() { return down(pieces);}
//---------------------------------------------------------------------------------
    public int[] left() { return left(pieces);}
//---------------------------------------------------------------------------------
    public int[] right() {return right(pieces);}
//---------------------------------------------------------------------------------
} // end class Pazzle
///////////////////////////////////////////////////////////////////////////////////////////////////////////////
class Solver
{
    private int cost = 0;
    private Vector usedList;
    private Vector fringeList;
    private Puzzle p;
//---------------------------------------------------------------------------------
    public Solver(int depth)
    {
        usedList = new Vector();
        fringeList = new Vector();
        p = new Puzzle(depth);
        fringeList.add(p);
    }
//---------------------------------------------------------------------------------
    public Solver(Puzzle puzzle)
    {
        usedList = new Vector();
        fringeList = new Vector();
        p = new Puzzle(puzzle);
        fringeList.add(p);
    }
//---------------------------------------------------------------------------------
    public void solve()  {while (expandNodes(p)) {p=findBestNode();}}
//---------------------------------------------------------------------------------
    public int getCost() {return (usedList.size() + fringeList.size());}
//---------------------------------------------------------------------------------
    // Finds the best node in the list
    private Puzzle findBestNode()
    {
        Puzzle best;
        Puzzle test;
        // If the fringe is empty, grab the only node
        if (fringeList.size()==0)
            best = (Puzzle)usedList.elementAt(0);
        // Otherwise grab the first fringe node, set it for comparison.
        else
            best = (Puzzle)fringeList.elementAt(0);
        for (int i=1; i<fringeList.size();i++)
        {
            test = (Puzzle)fringeList.get(i);
            // Get Heuristic Value for Node
            int bestH = best.getDepth() + best.getH();
            int testH = test.getDepth() + test.getH();
            // If it is lower, change "Best"
            if (testH < bestH)
                best = test;
        }
        return best;
    }
//---------------------------------------------------------------------------------
    private boolean expandNodes(Puzzle p)
    {
        int[] test;
        Puzzle temp;
        // take Node off of fringe
        fringeList.remove(p);
        // add it to used list, for GRAPH-SEARCH
        int parentID = usedList.size();
        usedList.add(p);
        // if Heuristic is 0, done
        if (p.getH() == 0)
            return false;
        // else test all directions
        test = p.up();
        temp = new Puzzle(test, p.isManhattan(), p.getDepth(), parentID);
        addToFringe(temp);
        test = p.down();
        temp = new Puzzle(test, p.isManhattan(), p.getDepth(), parentID);
        addToFringe(temp);
        test = p.left();
        temp = new Puzzle(test, p.isManhattan(), p.getDepth(), parentID);
        addToFringe(temp);
        test = p.right();
        temp = new Puzzle(test, p.isManhattan(), p.getDepth(), parentID);
        addToFringe(temp);
        return true;
    }
//---------------------------------------------------------------------------------
    private void addToFringe(Puzzle p)
    {
        // no repeat nodes
        if (!nodeRepeated(p))
        {
            p.addMove();
            fringeList.add(p);
        }
    }
//---------------------------------------------------------------------------------
    private boolean nodeRepeated (Puzzle node)
    {
        for (int i=0; i<usedList.size(); i++)
        {
            if (node.equals((Puzzle)usedList.get(i)))
                return true;
        }
        return false;
    }
//---------------------------------------------------------------------------------
    public void print()
    {
        Vector list = new Vector();
        // get solution
        Puzzle node = getPuzzleSolution();
        // add to answer list
        list.add(node);
        // find parent node
        int parentID = node.getParentID();
        while (parentID != -1)
        {
            node = (Puzzle)usedList.elementAt(parentID);
            list.add(node);
            parentID = node.getParentID();
        }

        for (int i = 1; i <= list.size();  i++)
        {
			if (i ==1)
			{
				System.out.println("Original:");
				System.out.println((Puzzle)list.elementAt(list.size()-i));
			}
			else
			{
				System.out.println("Step " + ( i -1)+ ":");
				System.out.println((Puzzle)list.elementAt(list.size()-i));
			}
	    }
        System.out.println("\nSolution with "+getPuzzleSolution().getDepth()+" step(s).");
    }
//---------------------------------------------------------------------------------
    public Puzzle getPuzzleSolution()
    {
        return (Puzzle)usedList.lastElement();
    }
//---------------------------------------------------------------------------------
} // end class Solver
///////////////////////////////////////////////////////////////////////////////////////////////////////////////
class Project01
{
//---------------------------------------------------------------------------------
    public static void main(String[] args)
    {
        Solver puzzle = new Solver(25);
        puzzle.solve();
        puzzle.print();
    }
//---------------------------------------------------------------------------------
} // end class Project01
///////////////////////////////////////////////////////////////////////////////////////////////////////////////
//For complexity Computation

class Computation
{
    private int[] counter;                   // Array to track each depth count
    private int[] timer;
    private int[] cost;
    private int max;                          // max depth
    private int min = 0;                    // min depth
    private int num = 10;                 // # of each solution to get
    private int size = 75;                 // Base size to randomize by
//---------------------------------------------------------------------------------
    public Computation(int max)
    {
        this.max = max;
        counter = new int[max];
        timer = new int[max];
        cost = new int[max];
    }
//---------------------------------------------------------------------------------
    public Computation(int min, int max)
    {
        this.max = max;
        this.min = min;
        counter = new int[max];
        timer = new int[max];
        cost = new int[max];
    }
//---------------------------------------------------------------------------------
    // Runs enough puzzles to meet requirements
    public void run()
    {
        int i;
        do
        {
            Solver p = new Solver(size);
            Timer t = new Timer();
            t.start();
            p.solve();
            long time = t.end();
            Puzzle solution = p.getPuzzleSolution();

            if (solution.getDepth() <= max && (solution.getDepth()-min) > 0)
            {
                if (counter[(solution.getDepth()-1)-min] < num)
                {
                    counter[(solution.getDepth()-1)-min]++;
                    timer[(solution.getDepth()-1)-min] += time;
                    cost[(solution.getDepth()-1)-min] += p.getCost();
                }
            }
        } while (!checkCounter());
        System.out.println("Depth\tCost\tTime to Execute");
        for (i=0; i<(max-min); i++)
            System.out.println((i+1)+min+"\t"+(cost[i]/num)+"\t"+timer[i]/num);
    }
//---------------------------------------------------------------------------------
    // Returns true if Data is complete
    public boolean checkCounter()
    {
        int count = 0;
        for (int i=0; i<(max-min); i++)
        {
            count += counter[i];
        }
        return (count == ((max-min)*num));
    }
} // end class Computation
///////////////////////////////////////////////////////////////////////////////////////////////////////////////
class Timer
{
    Date now;
    long start;
//---------------------------------------------------------------------------------
    public Timer() {}
//---------------------------------------------------------------------------------
    // Start timer
    public void start()
    {
        now = new Date();
        start = now.getTime();
    }
//---------------------------------------------------------------------------------
// End Timer
    public long end()
    {
        now = new Date();
        long end = now.getTime();
        return ((end-start));
    }
} // end class Timer
///////////////////////////////////////////////////////////////////////////////////////////////////////////////