如何在一维数组Java中上下左右搜索

Question

我正在研究3x3拼图滑块游戏，该游戏使用广度优先搜索来找到从initial_state到Goal_state的最佳解决方案。目前，gamestate方法“ possibleMoves（）”不会向上，向下，向左和向右搜索。在我更改之前，它仅搜索左右移动：对于（int i = 0; i <9; i ++）进入对于（int i = 0; i <3; i ++）{for（int j = 0; j <3; j ++）{..

如何调整当前代码以执行正确的搜索？

import java.util.ArrayList;

public class GameState {
    final char[] board;
    private int spacePos;
    static final char[] INITIAL_BOARD = { '2', '3', '5', '4', '6', '8', '7', '1', ' ' };
    static final char[] GOAL_BOARD = { '1', '2', '3', '4', '5', '6', '7', '8', ' ' };

    /*
     * GameState is a constructor that takes a char array holding a board
     * configuration as argument.
     */
    public GameState(char[] board) {
        this.board = board;
        for (int j = 0; j < 9; j++) {
            if (board[j] == ' ') {
                this.spacePos = j;
                break;
            }
        }
    }

    /*
     * clone returns a new GameState with the same board configuration as the
     * current GameState.
     */
    public GameState clone() {
        char[] clonedBoard = new char[9];
        System.arraycopy(this.board, 0, clonedBoard, 0, 9);
        return new GameState(clonedBoard);
    }

    public int getSpacePos() {
        return spacePos;
    }

    /*
     * toString returns the board configuration of the current GameState as a
     * printable string.
     */
    public String toString() {
        String s = "[";
        for (char c : this.board)
            s = s + c;
        return s + "]";
    }

    /*
     * isGoal returns true if and only if the board configuration of the current
     * GameState is the goal configuration.
     */
    public boolean isGoal() {
        for (int j = 0; j < 9; j++) {
            if (this.board[j] != GOAL_BOARD[j])
                return false;
        }
        return true;
    }

    /*
     * sameBoard returns true if and only if the GameState supplied as argument has
     * the same board configuration as the current GameState.
     */
    public boolean sameBoard(GameState gs) {
        for (int j = 0; j < 9; j++) {
            if (this.board[j] != gs.board[j])
                return false;
        }
        return true;
    }

    /*
     * possibleMoves returns a list of all GameStates that can be reached in a
     * single move from the current GameState.
     */
    public ArrayList<GameState> possibleMoves() {
        ArrayList<GameState> moves = new ArrayList<GameState>();
        for (int i = 0; i < 3; i++) {
            for(int j = 0; j < 3; j++) {
            if (i != this.spacePos) {
                int distance = Math.abs(this.spacePos - i);
                if (distance <= 3) {
                    GameState newState = this.clone();
                    newState.board[this.spacePos] = this.board[i];
                    newState.board[i] = ' ';
                    newState.spacePos = i;
                    moves.add(newState);
                }
            }
        }
        }
        return moves;
    }

}

Answer 1

假设拼图滑块只有1个开放空间，那么您进行莫桑比克移动的方法不是正确的方法。您应该创建moveFromTheLeft，moveFromTheRight，moveFromTheTop，moveFromTheBottom，并将通过调用这四个方法创建的板添加到队列中

Answer 2

要在3x3游戏板上从左到右搜索，公式如下：

up_i = i - 3
down_i = i + 3
left_i = i - 1
right_i = i + 1

对于更一般的NxN游戏板，您只需将上/下公式中的3替换为N。