查找节点滑动块的所有邻居

Question

所以我有一些代码可以找到某个国家的邻居。因此，空白瓷砖(在我的代码中表示为0)的位置可以移动。

我正在做3x3瓷砖拼图。目标状态表示如下：

1 2 3
4 5 6
7 8 0

假设我有一个问题状态，那就是：

8 5 1 
3 4 7 
0 6 2

我会在这个状态上调用findNeighbours()方法，它应该返回两个这样的状态。

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 

我在这里发布的原因是因为我没有得到我所希望的性能，而且我假设这个findNeighbours()是问题所在，至少可以说代码很笨拙！我还应该指出，状态是一个类似于state = {1,2,3,4,5,6,7,8,0}的数组，而neighbours是一个ArrayList，我将每个州都添加到其中。

   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;
            }
        }
    }

Answer 1

你的代码真的很难读懂。我建议如下：

1. 有四种方法：slideUp、slideDown、slideLeft、slideRight，每个方法都复制this并应用幻灯片操作。
2. 在邻区生成例程中，只需检查所有的四个，其中任何一个返回一个非空结果，添加到列表中；最后，返回列表。
3. 缓存零平铺的索引。

我心里想的是：

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;
            }
        }
    }
}

希望这能帮上忙。