Как искать вверх-вниз-влево-вправо в одномерном массиве Java

Question

Я работаю над головоломкой 3x3, в которой используется поиск в ширину, чтобы найти оптимальное решение от initial_state до goal_state. На данный момент метод gamestate "possibleMoves()" не выполняет поиск вверх, вниз, влево и вправо. Он только искал ходы влево и вправо, прежде чем я изменил: for (int i = 0; i < 9; i++) into for (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

Чтобы определить, можете ли вы перемещаться вверх, вниз, влево и вправо для игровой доски 3x3, вам нужно добавить следующие методы:

// The space directly above, if it is not in the first row
// Is i - 3
boolean canGoUp(i) {
  return (i - 3 >= 0) ? true : false;
}

// The space directly below, if it is not in the last row
// Is i + 3
boolean canGoDown(i) {
  return (i + 3 < 9) ? true : false;
}

// The space to the left, if not in the first column
// Is i - 1
boolean canGoLeft(i) {
  return (i % 3 != 0) ? true : false;
}

// The space to the right, if not in the last column
// Is i + 1
boolean canGoRight(i) {
  return ((i + 1) % 3 != 0) ? true : false;
}

Для более общей игровой доски NxN вы можете просто заменить 3 и 9 в формулах на N и N*N соответственно.

Answer 2

Предполагая, что ползунок головоломки имеет только одно открытое пространство, то, как вы делаете possibleMoves, не является правильным. Вы должны создать moveFromTheLeft, moveFromTheRight, moveFromTheTop, moveFromTheBottom и добавить доски, созданные в результате вызова этих четырех методов, в вашу очередь.