java用栈实现骑士游历问题并输出结果

骑士游历问题是一个经典的回溯算法问题，可以用栈来实现。下面是Java代码实现：

import java.util.Stack;

public class KnightTour {
    private static final int BOARD_SIZE = 8;

    private static final int[] X_MOVES = {2, 1, -1, -2, -2, -1, 1, 2};
    private static final int[] Y_MOVES = {1, 2, 2, 1, -1, -2, -2, -1};

    private int[][] board;
    private Stack<int[]> stack;

    public KnightTour() {
        board = new int[BOARD_SIZE][BOARD_SIZE];
        stack = new Stack<>();
    }

    public void solve(int startX, int startY) {
        board[startX][startY] = 1;
        stack.push(new int[]{startX, startY});

        while (!stack.empty()) {
            int[] current = stack.peek();
            int x = current[0];
            int y = current[1];
            int nextX = -1;
            int nextY = -1;
            boolean foundNext = false;

            for (int i = 0; i < X_MOVES.length; i++) {
                nextX = x + X_MOVES[i];
                nextY = y + Y_MOVES[i];

                if (isValidMove(nextX, nextY) && board[nextX][nextY] == 0) {
                    board[nextX][nextY] = board[x][y] + 1;
                    stack.push(new int[]{nextX, nextY});
                    foundNext = true;
                    break;
                }
            }

            if (!foundNext) {
                stack.pop();
                board[x][y] = 0;
            } else if (board[nextX][nextY] == BOARD_SIZE * BOARD_SIZE) {
                printSolution();
                stack.pop();
                board[nextX][nextY] = 0;
            }
        }
    }

    private boolean isValidMove(int x, int y) {
        return x >= 0 && x < BOARD_SIZE && y >= 0 && y < BOARD_SIZE;
    }

    private void printSolution() {
        for (int[] row : board) {
            for (int cell : row) {
                System.out.print(cell + "\t");
            }
            System.out.println();
        }
        System.out.println();
    }

    public static void main(String[] args) {
        KnightTour knightTour = new KnightTour();
        knightTour.solve(0, 0);
    }
}

在这个实现中，我们使用一个二维数组 `board` 来表示棋盘，用一个栈 `stack` 来保存已经走过的位置。在开始时，我们将起始位置标记为已经访问过，并将其推入栈中。然后我们进入一个循环，每次从栈顶取出当前位置，尝试走出下一步。如果能够走到一个未访问过的位置，我们就将其标记为已经访问过，并将其推入栈中。如果无法走到下一个位置，我们就将当前位置弹出栈，并将其标记为未访问过。

当我们遍历完所有的位置时，就找到了一种解法，输出结果即可。