5
\$\begingroup\$

So I have some code which finds neighbours of a given State. So the positions the blank tile (which is represented as 0 in my code) can be moved.

I am doing the 3x3 tile puzzle. The goal state is represented like this :

1 2 3
4 5 6
7 8 0

Say I have a problem state which is:

8 5 1 
3 4 7 
0 6 2

I would call the findNeighbours() method on this State and it should return two states like this .

8 5 1                             8 5 1 
3 4 7   (This is a right move)    0 4 7  (This is an up move)     
6 0 2                             3 6 2 

The reason I'm posting here is because I'm not getting the performance I'd hoped for and I'm assuming this findNeighbours() is the issue as the code is clunky to say the least! I should also point out that state is an array which looks something like state = {1,2,3,4,5,6,7,8,0} and neighbours is an ArrayList which I am adding every State to

   public void findNeighbours() {
        for (int i = 0; i < state.length; i++) {
            if (state[i] == 0) {
                if (i % 3 != 0) {
                    int[] left = new int[9];
                    System.arraycopy(state, 0, left, 0, left.length);
                    int temp = left[i];
                    left[i] = left[i - 1];
                    left[i - 1] = temp;
                    State newState = new State(left,this, "left");
                    this.neighbours.add(newState);

                }
                if (i % 3 != 2) {
                    int[] right = new int[9];
                    System.arraycopy(state, 0, right, 0, right.length);
                    int temp = right[i];
                    right[i] = right[i + 1];
                    right[i + 1] = temp;
                    State newState = new State(right, this, "right");
                    this.neighbours.add(newState);
                }
                if (i > 3) {
                    int[] up = new int[9];
                    System.arraycopy(state, 0, up, 0, up.length);

                    int temp = up[i];
                    up[i] = up[i - 3];
                    up[i - 3] = temp;
                    State newState = new State(up, this, "up");
                    this.neighbours.add(newState);
                }
                if (i < 6) {
                    int[] down = new int[9];
                    System.arraycopy(state, 0, down, 0, down.length);
                    int temp = down[i];
                    down[i] = down[i + 3];
                    down[i + 3] = temp;
                    State newState = new State(down,  this, "down");
                    this.neighbours.add(newState);
                }
                break;
            }
        }
    }
\$\endgroup\$
2
\$\begingroup\$

Your code is really hard to read. I suggest the following:

  1. Have four methods slideUp, slideDown, slideLeft, slideRight, each copying the this and applying the slide operation.
  2. In the neighbour generation routine just check all the four, and whichever of them return a non-null result add to the list; finally, return the list.
  3. Cache the index of the zero tile.

I had this in mind:

import java.util.ArrayList;
import java.util.Collection;
import java.util.List;
import java.util.Scanner;

public class SlidingTilePuzzleNode {

    private int[] state = new int[9];

    private int zeroTileIndex;

    public SlidingTilePuzzleNode() {
        for (int i = 0; i < state.length - 1; ++i) {
            state[i] = i + 1;
        }

        zeroTileIndex = state.length - 1;
    }

    private SlidingTilePuzzleNode(int[] state, int zeroTileIndex) {
        this.state = state.clone();
        this.zeroTileIndex = zeroTileIndex;
    }

    public SlidingTilePuzzleNode slideUp() {
        int x = getX(zeroTileIndex);
        int y = getY(zeroTileIndex);

        if (y == 0) {
            return null;
        }

        int nextx = x;
        int nexty = y - 1;
        int nextIndex = xyToIndex(nextx, nexty);
        SlidingTilePuzzleNode node = new SlidingTilePuzzleNode(state,   
                                                               nextIndex);
        int tmp = node.state[nextIndex];
        node.state[nextIndex] = node.state[zeroTileIndex];
        node.state[zeroTileIndex] = tmp;
        return node;
    }

    public SlidingTilePuzzleNode slideDown() {
        int x = getX(zeroTileIndex);
        int y = getY(zeroTileIndex);

        if (y == 2) {
            return null;
        }

        int nextx = x;
        int nexty = y + 1;
        int nextIndex = xyToIndex(nextx, nexty);
        SlidingTilePuzzleNode node = new SlidingTilePuzzleNode(state,   
                                                               nextIndex);
        int tmp = node.state[nextIndex];
        node.state[nextIndex] = node.state[zeroTileIndex];
        node.state[zeroTileIndex] = tmp;
        return node;
    }

    public SlidingTilePuzzleNode slideLeft() {
        int x = getX(zeroTileIndex);
        int y = getY(zeroTileIndex);

        if (x == 0) {
            return null;
        }

        int nextx = x - 1;
        int nexty = y;
        int nextIndex = xyToIndex(nextx, nexty);
        SlidingTilePuzzleNode node = new SlidingTilePuzzleNode(state,   
                                                               nextIndex);
        int tmp = node.state[nextIndex];
        node.state[nextIndex] = node.state[zeroTileIndex];
        node.state[zeroTileIndex] = tmp;
        return node;
    }

    public SlidingTilePuzzleNode slideRight() {
        int x = getX(zeroTileIndex);
        int y = getY(zeroTileIndex);

        if (x == 2) {
            return null;
        }

        int nextx = x + 1;
        int nexty = y;
        int nextIndex = xyToIndex(nextx, nexty);
        SlidingTilePuzzleNode node = new SlidingTilePuzzleNode(state, 
                                                               nextIndex);
        int tmp = node.state[nextIndex];
        node.state[nextIndex] = node.state[zeroTileIndex];
        node.state[zeroTileIndex] = tmp;
        return node;
    }

    public Collection<SlidingTilePuzzleNode> getNeighbors() {
        List<SlidingTilePuzzleNode> neighborList = new ArrayList<>(4);
        SlidingTilePuzzleNode node = slideUp();

        if (node != null) {
            neighborList.add(node);
        }

        node = slideDown();

        if (node != null) {
            neighborList.add(node);
        }

        node = slideLeft();

        if (node != null) {
            neighborList.add(node);
        }

        node = slideRight();

        if (node != null) {
            neighborList.add(node);
        }

        return neighborList;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        int index = 0;

        for (int y = 0; y < 3; ++y) {
            for (int x = 0; x < 3; ++x) {
                sb.append(state[index++]);
            }
            sb.append("\n");
        }

        return sb.toString();
    }

    private static int getX(int index) {
        return index % 3;
    }

    private static int getY(int index) {
        return index / 3;
    }

    private static int xyToIndex(int x, int y) {
        return y * 3 + x;
    }

    public static void main(String[] args) {
        SlidingTilePuzzleNode node = new SlidingTilePuzzleNode();
        SlidingTilePuzzleNode tmpNode;
        Scanner scanner = new Scanner(System.in);

        while (true) {
            System.out.println(node);

            String cmd = scanner.nextLine().trim().toLowerCase();

            switch (cmd) {
                case "quit":
                case "exit":
                    System.exit(0);

                case "up":
                    tmpNode = node.slideUp();

                    if (tmpNode != null) {
                        node = tmpNode;
                    }

                    break;

                case "down":
                    tmpNode = node.slideDown();

                    if (tmpNode != null) {
                        node = tmpNode;
                    }

                    break;

                case "left":
                    tmpNode = node.slideLeft();

                    if (tmpNode != null) {
                        node = tmpNode;
                    }

                    break;

                case "right":
                    tmpNode = node.slideRight();

                    if (tmpNode != null) {
                        node = tmpNode;
                    }

                    break;
            }
        }
    }
}

Hope that helps.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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