5
\$\begingroup\$

I am a CS student about to enter my junior year. I am attempting to get better and better at programming and thought that this would be a good place to toss my code out there to see if some of you could give me some tips on how to make it better.

If you've got tips as to different websites I could go to for this sort of thing, please don't hesitate to tell me.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

/*************************************************************************
 * Compilation: javac EightPuzzle.java Execution: java EightPuzzle Dependencies:
 * MinPQ.java
 * 
 * AI solution to N-by-N slider puzzle using heuristic function which is depth
 * in tree plus number of tiles out of position.
 * 
 * Note: integer 0 corresponds to blank cell
 * 
 * Goal state is of the following form and is hardwired into the dist() and
 * manhattan() methods.
 * 
 * 1 2 3 4 5 6 7 8
 * 
 *************************************************************************/

public class EightPuzzle implements Comparable<EightPuzzle> {

    private final static int N = 3;
    private final static String[] names = { "   ", "  1", "  2", "  3", "  4",
            "  5", "  6", "  7", "  8" };
    private static int totalEnqueued;
    private final static int[][] solved = { { 1, 2, 3 }, { 4, 5, 6 },
            { 7, 8, 0 } };
    private int moves;
    private int[][] tiles;
    private EightPuzzle parent;
    private int priority;
    private int distance;
    int zeroLocX = 0;
    int zeroLocY = 0;

    // allocate separate memory for new tiles array
    EightPuzzle(int[][] tiles) {
        this.tiles = new int[N][N];
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                this.tiles[i][j] = tiles[i][j];

    }

    EightPuzzle(int[][] tiles, EightPuzzle parent, int moves) {
        this.tiles = new int[N][N];
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                this.tiles[i][j] = tiles[i][j];
        this.parent = parent;
        this.moves = moves;
        priority();
    }

    // priority
    /**
     * @return
     */
    public int priority() {
        int manhatDist = 0;
        for (int x = 0; x < N; x++)
            for (int y = 0; y < N; y++) {
                switch (tiles[x][y]) {

                case 1:
                    manhatDist += posDiff(x, y, 0, 0);
                    break;
                case 2:
                    manhatDist += posDiff(x, y, 0, 1);
                    break;
                case 3:
                    manhatDist += posDiff(x, y, 0, 2);
                    break;
                case 4:
                    manhatDist += posDiff(x, y, 1, 0);
                    break;
                case 5:
                    manhatDist += posDiff(x, y, 1, 1);
                    break;
                case 6:
                    manhatDist += posDiff(x, y, 1, 2);
                    break;
                case 7:
                    manhatDist += posDiff(x, y, 2, 0);
                    break;
                case 8:
                    manhatDist += posDiff(x, y, 2, 1);
                    break;
                case 0:
                    manhatDist += posDiff(x, y, 2, 2);
                    break;
                default:
                    break;
                }

            }
        this.priority = manhatDist + moves;
        return priority;
    }

    private int posDiff(int xPos, int yPos, int xGoal, int yGoal) {
        int diff = Math.abs(xPos - xGoal);
        diff += Math.abs(yPos - yGoal);

        return diff;
    }

    // which board position is closer to the goal board position
    /**
     * (non-Javadoc) see java.lang.Comparable#compareTo(java.lang.Object)
     */
    @Override
    public int compareTo(EightPuzzle b) {
        if (b.distance() == distance()) {
            for (int i = 0; i < N; i++) {
                if (!(Arrays.equals(b.getBoard()[i], this.getBoard()[i]))) { //if any elements are different, we know the arrays are not equal
                    if (b.priority() > priority()) //but we still need to know whether to return a -1 or 1
                        return -1;
                    return 1;
                }
            }
            return 0; //if we make it here they are equal
        } else if (b.priority() > priority()) //if the distances are different 
            return -1;
        else
            return 1;
    }

    /**
     * @return
     */
    public int[][] getBoard() {
        return tiles;
    }

    // does board position equal goal position?
    /**
     * @return
     */
    public boolean isSolved() {
        // your implementation
        for (int i = 0; i < N; i++) {
            if (!(Arrays.equals(tiles[i], solved[i]))) {
                return false;
            }

        }
        return true;
    }

    //for NxN expansion...not quite complete yet.
    public int[][] findGoalState() {
        int[][] solved = new int[N][N];
        int nums = 1;

        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++) {
                solved[i][j] = nums;
                nums++;
                if (nums == (N * N)) {
                    solved[N - 1][N - 1] = 0;
                    break;
                }
            }
        return solved;
    }

    // return sum of Manhattan distances of tiles to their proper position
    private int distance() {
        this.distance = priority() - moves;
        return this.distance;
    }

    private int getZeroXLoc() {
        for (int x = 0; x < N; x++)
            for (int y = 0; y < N; y++)
                if (tiles[x][y] == 0) {
                    zeroLocX = x; //finding our zero so we can begin moving tiles
                    zeroLocY = y;
                }
        return zeroLocX;
    }

    private int getZeroYLoc() {
        getZeroXLoc();
        return zeroLocY;
    }

    private void assignZeroLoc() {
        getZeroYLoc();
    }

    // return the neighboring board positions
    /**
     * @return
     */
    public EightPuzzle[] neighbors() {
        ArrayList<EightPuzzle> tempneighbors = new ArrayList<EightPuzzle>();

        assignZeroLoc(); //determines both x and y loc's of the zero

        for (int i = -1; i < 2; i++) { //creating all surrounding x coordinates
            int p = zeroLocX + i; //current array being looked at
            if (p < 0 || p > N - 1)
                continue; //meaning these squares are out of bounds
            for (int j = -1; j < 2; j++) {
                int q = zeroLocY + j; //current index in current array
                if (q < 0 || q > N - 1 || (p == zeroLocX && q == zeroLocY) || //if we are out of bounds or at the same square
                        ((Math.abs(zeroLocX - p) + Math.abs(zeroLocY - q))) > 1) //or if delta x + delta y is greater than 1, aka at a diagonal space
                    continue; //skip this iteration

                int[][] temptiles = new int[N][N];

                for (int m = 0; m < N; m++)
                    temptiles[m] = Arrays.copyOf(tiles[m], N); //copy the original board

                int tempQ = temptiles[p][q]; //store the value of the value to swap
                temptiles[p][q] = 0; //place the 0 in a valid location
                temptiles[zeroLocX][zeroLocY] = tempQ; //place the stored value to swap where the 0 was
                EightPuzzle neighbor = new EightPuzzle(temptiles, this,
                        this.moves + 1); //create a new 8 puzzle 
                tempneighbors.add(neighbor); //add it to the arraylist
                totalEnqueued++;

            }

        }

        EightPuzzle[] neighbors = new EightPuzzle[tempneighbors.size()];

        return tempneighbors.toArray(neighbors);
    }

    // print parents in reverse order
    /**
 * 
 */
    public void showPath() {
        if (parent != null)
            parent.showPath();
        System.out.println("Move #" + moves + " Priority = " + priority);
        System.out.println(toString());
    }

    // print details of puzzle
    /**
     * (non-Javadoc)
     * 
     * @see java.lang.Object#toString()
     */
    @Override
    public String toString() {
        String s = "";
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++)
                s += names[tiles[i][j]] + " ";
            s += "\n";
        }
        return s;
    }

    /**
     * @return
     */
    public boolean isSolvable() {
        int[] row = new int[(N * N) - 1];
        int rowIndex = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (tiles[i][j] != 0) {
                    row[rowIndex] = tiles[i][j];
                    rowIndex++;
                }
            }
        }

        int inversions = 0;
        for (int x = 0; x < row.length; x++) {
            for (int y = x; y < row.length; y++)
                if (row[x] > row[y])
                    inversions++;
        }
        return inversions % 2 == 0;
    }

    /***********************************************************************
     * Test routine.
     **********************************************************************/
    public static void main(String[] args) {

        // 6 moves
        int[][] easy0 = { { 1, 2, 3 }, { 7, 0, 5 }, { 8, 4, 6 } }; //<1 second
        int[][] hard0 = { { 0, 8, 7 }, { 2, 5, 1 }, { 3, 6, 4 } }; //5.5 minutes
        int[][] hard1 = { { 4, 5, 0 }, { 6, 8, 7 }, { 1, 2, 3 } }; //5.5 minutes
        int[][] medium0 = { { 2, 3, 1 }, { 7, 0, 8 }, { 6, 5, 4 } }; //1 second
        int[][] medium1 = { { 1, 2, 3 }, { 8, 0, 4 }, { 7, 6, 5 } }; //1 second
        int[][] medium2 = { { 1, 2, 3 }, { 7, 0, 4 }, { 8, 6, 5 } }; //2 seconds
         int[][] twentytwo = { {4, 8, 2},
                 {3, 6, 5},
                 {1, 7, 0} };

        System.out
                .println("Please enter the 3x3 grid in the format \n\"XXX \n XXX  \n XXX\" where X is a number between 0 and 8");
        Scanner scan = new Scanner(System.in);
        int userEntered = 0;
        int[][] userIn = new int[N][N];
        try {
            while (userEntered < 3) {
                String line = scan.nextLine().trim();

                for (int i = 0; i < N; i++) {
                    userIn[userEntered][i] = Integer.parseInt(Character
                            .toString((line.charAt(i))));

                }
                userEntered++;
            }
        } catch (Exception e) {
            System.out
                    .println("Please restart the program and enter the gridin the correct format");
            System.exit(0);
        }

        EightPuzzle x = new EightPuzzle(userIn);
        System.out.println(x);

        MinPQ<EightPuzzle> pq = new MinPQ<EightPuzzle>();
        pq.insert(x);

        int nodes = 0;
        ArrayList<EightPuzzle> seen = new ArrayList<EightPuzzle>();
        //      Stopwatch sw = new Stopwatch();
        while (!pq.isEmpty()) {
            x = pq.delMin(); //get the minimum key
            if (nodes == 0) {
                if (!x.isSolvable()) {
                    System.out                      .println("This is an unsolvable puzzle, please enter a solvable one");
                    System.exit(0);
                }
            }
            nodes++;

            //TODO:make this faster, maybe a binary search tree instead of arraylist
            for (int i = 0; i < seen.size(); i++) { //make sure we aren't back tracking.
                if (x.compareTo(seen.get(i)) == 0) {
                    x = pq.delMin();
                }
            }

            seen.add(x); //add to the nodes we've seen

            if (x.isSolved()) {
                //              System.out.println(sw.elapsedTime());
                break;
            }

            EightPuzzle[] neighbors = x.neighbors(); //find and add all neighbors
            for (int i = 0; i < neighbors.length; i++)
                if (!(x.compareTo(neighbors[i]) == 0)
                        && neighbors[i].isSolvable())
                    pq.insert(neighbors[i]);

        }
        System.out.println("Total nodes enqueued = " + totalEnqueued);
        System.out.println("Nodes expanded = " + nodes);
        x.showPath();
    }

}
\$\endgroup\$
1
  • \$\begingroup\$ MinPQ cannot be resolved to a type \$\endgroup\$
    – tb-
    Dec 17, 2012 at 14:05

1 Answer 1

3
\$\begingroup\$

In the Constructor, you manually copy an array:

for(int j = 0; j < N; j++)
{
    this.tiles[i][j] = tiles[i][j];
}

Which can be replaced with:

System.arraycopy(tiles[i], 0, this.tiles[i], 0, N);

And the entire switch in your priority() method can be replaced by:

manhatDist += posDiff(x, y, (tiles[x][y] == 0 ? 2 : (int) (tiles[x][y] / 3.5)), (tiles[x][y] + 2) % 3);

To test this code, I used:

for(int i = 0; i < 9; i++)
{
    System.out.println(i + "\t"  + (i == 0 ? 2 : (int) (i / 3.5)) + "\t" + (i + 2) % 3);
}

Which produces:

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

Which is what you're already doing manually.

Additionally, your constructor with more parameters exactly duplicates code from the smaller one, so you could replace (your newly changed!):

this.tiles = new int[N][N];
for(int i = 0; i < N; i++)
{
    System.arraycopy(tiles[i], 0, this.tiles[i], 0, N);
}

With:

this(new int[N][N]);

So the smaller constructor does that part, then continues with the additional options.

\$\endgroup\$
3
  • \$\begingroup\$ Great, thanks for the suggestions. I implemented them both and it looks like they are working well. \$\endgroup\$ Dec 16, 2012 at 2:39
  • \$\begingroup\$ Does anyone have a suggestion as to how the neighbors() method could be improved? I was playing with recursive ideas and/or a BFS but couldn't quite put my finger on it as well as I could with this iterative solution. \$\endgroup\$ Dec 16, 2012 at 2:40
  • \$\begingroup\$ My original change to your switch was wrong, I didn't notice the third parameter should change. I have updated my post to include the new code as well as the output. \$\endgroup\$
    – MrLore
    Dec 16, 2012 at 12:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.