时间戳

首页 > 解决方案 > java - 如何确定骑士在Java中到达棋盘上的任何位置需要多少步

java - java - 如何确定骑士在Java中到达棋盘上的任何位置需要多少步

问题描述

我正在尝试创建一个程序，当给定国际象棋骑士的位置和目的地时，所有这些都以国际象棋符号标记，以返回骑士从目的地位置获得的移动次数。在使用该算法计算列表中的每一个可能性之前，我已经尝试过，但它非常慢并且有点问题。这是我的代码：

private static int translateChessNotation(String chess) {
        int returned = 8 * (Integer.valueOf(String.valueOf(chess.charAt(1)))- 1);
        return returned + (convertAlphabet(chess.charAt(0))); // File
}

public static int knight(String start, String finish) {
    int knightPosition = translateChessNotation(start), end = translateChessNotation(finish), i = 0;
    ArrayList<Integer> currentPossibleKnightPositions = new ArrayList<>();
    currentPossibleKnightPositions.add(knightPosition);
    for (; i < 8; i++) {
        ArrayList<Integer> newList = new ArrayList<>();
        for (int position : currentPossibleKnightPositions) {
            newList.add(position + 17);
            newList.add(position + 15);
            newList.add(position + 10);
            newList.add(position + 6);
            newList.add(position - 6);
            newList.add(position - 10);
            newList.add(position - 15);
            newList.add(position - 17);
        }
        ArrayList<Integer> removed = new ArrayList<>();
        for (int j : newList) {if (j < 1 || j > 64) {removed.add(j);}}
        newList.removeAll(removed);
        currentPossibleKnightPositions.clear();
        currentPossibleKnightPositions.addAll(newList);
        for (int n : currentPossibleKnightPositions) {
            if (n == end) {return i + 1;}
        }
    }
    return -1;
}

非常感谢您的帮助！

标签： javaalgorithmpath-finding

解决方案

这里有一个小 Proggy 来解决所谓的 Knights-Tour 问题，从特定位置开始访问棋盘上的所有方格，因此您可以调整它以将特定的目标位置设置为您的结束条件。

它只是蛮力，尝试所有可能的组合并需要大约 50 分钟才能找到每个完整的 Knights-Tour 解决方案。

如果这有帮助，我很荣幸收到您的投票。

import java.util.concurrent.atomic.AtomicInteger;
import java.util.stream.IntStream;

public class KnightMove {

    @SuppressWarnings("serial")
    private static final class KnightMoveSolvedException extends RuntimeException {

        private final byte[][] solution;

        private KnightMoveSolvedException(final byte[][] solution) {
            this.solution = solution;
        }
    }

    private static final int      SIZE_X       = 8;
    private static final int      SIZE_Y       = 8;
    private static final int      SIZE_X_Y     = SIZE_X * SIZE_Y; // Max 127! (=0x7F)

    private static final int [][] KNIGHT_MOVES = new int[8][];
    /**/    static {     
        final AtomicInteger moveIndex = new AtomicInteger();

        IntStream.of(2, -2).forEach(deltaX ->
        IntStream.of(1, -1).forEach(deltaY -> {
            /*
             * Mirror the 4 combinations above to get all 8 possible Knight moves...
             */
            KNIGHT_MOVES[moveIndex.getAndIncrement()] = new int[] {deltaX, deltaY};
            KNIGHT_MOVES[moveIndex.getAndIncrement()] = new int[] {deltaY, deltaX};  
        }));
    }

    private static void nextMoveToXY(int moveCount, final int x, final int y, final byte[][] board) {
        moveCount++;

        board[x][y] = (byte) moveCount;

        if (moveCount >= SIZE_X_Y) {

            System.out.println("Solved!.....: count=" + moveCount);

            for (    final byte[] column : board ) {
                for (final byte   square : column) {
                    System.out.print(square + "\t");
                }
                System.out.println();
            }
            return;  // (Back up & keep looking for next solution)
            /*
             * If 1 solution is enough, just throw the Exception...
             */
//          throw new KnightMoveSolvedException(board);
        }

        for (final int[] knightMove : KNIGHT_MOVES) {

            final int newX = x + knightMove[0];  if (newX < 0 || newX >= SIZE_X) {continue;}
            final int newY = y + knightMove[1];  if (newY < 0 || newY >= SIZE_Y) {continue;}

            if (board[newX][newY] == 0) {
                /*
                 * Target Square is vacant, so try this move recursively...
                 */
                nextMoveToXY(moveCount, newX, newY, deepPrimitive2DArrayClone(board));
            }
        }
    }

    /**
     * {@link Object#clone()} can create a Deep Clone of a 1D array of Primitives
     * but will <b>not</b> deliver the desired result with 2D,
     * so we have to wrap the rest by hand...
     */
    private static byte[][] deepPrimitive2DArrayClone(final byte[][] source) {

        final byte[][] clone = new byte[source.length][];
        /**/  int      cix   = 0;

        for (final byte[]  col : source) {
            clone[cix++] = col.clone();
        }
        return clone;
    }

    public static void main(final String[] args) throws Exception {

        IntStream.range(0, SIZE_X).forEach(x ->
        IntStream.range(0, SIZE_Y).forEach(y -> {
            try {
                System.out.println("Solve starting at X/Y.: " + x +"/" + y);

                nextMoveToXY(0, x, y, new byte[SIZE_X][SIZE_Y]);
            }
            catch (final KnightMoveSolvedException e) {
                System.out.println(e.solution);
            }
        }));
    }
}

推荐阅读