如何让骑士巡游程序中的骑士在棋盘上随机移动？

Hey there! Let's get your knight tour program working with random moves instead of that fixed sequence of checking possible moves. I'll walk you through fixing the existing code and implementing the random logic step by step.

First, Let's Fix the Missing Pieces in Your Code #

Your current code has a few gaps that need addressing first:

• You haven't declared the chessboard2 array as a member variable in the Knight class
• The solve() method calls move() with missing parameters
• The print() method tries to join int values directly, which won't work
• Creating a new Random object every time move() runs is inefficient

Modified Code with Random Moves #

Here's the updated version of your code with all fixes and the random move logic implemented:

package assignment3;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;
import java.util.Arrays;

/*
 * knows its current position (row and column)
 * knows the eight types of moves it can make
 * can tell you it’s current row and column
 * can determine whether a move of a given type is legal or not
 * can move
 */
public class Knight {
    private int boardSize = 8;
    private int[] rowMoves = {-1, -2, -2, -1, 1, 2, 2, 1};
    private int[] colMoves = {2, 1, -1, -2, -2, -1, 1, 2};
    private int[][] chessboard2; // Added board as member variable
    private Random rand = new Random(); // Reuse single Random instance

    public Knight() {
        // Constructor can stay empty, we'll initialize board in solve()
    }

    public void InitializeBoard() {
        // Initialize board with correct size
        chessboard2 = new int[boardSize][boardSize];
        for (int i = 0; i < boardSize; i++)
            Arrays.fill(chessboard2[i], Integer.MIN_VALUE); // Mark unvisited squares
    }

    /**
     * Modified to use random valid moves instead of fixed order
     */
    public boolean move(int moveNum, int x, int y, int[][] chessboard2) {
        // All squares visited successfully
        if (moveNum == 64) {
            System.out.println("Success! All 64 squares visited.");
            return true;
        }

        // Collect all valid, unvisited moves first
        List<Integer> validMoveIndices = new ArrayList<>();
        for (int i = 0; i < rowMoves.length; i++) {
            int nextRow = x + rowMoves[i];
            int nextCol = y + colMoves[i];
            if (canMove(nextRow, nextCol) && chessboard2[nextRow][nextCol] == Integer.MIN_VALUE) {
                validMoveIndices.add(i);
            }
        }

        // No valid moves left, backtrack
        if (validMoveIndices.isEmpty()) {
            return false;
        }

        // Shuffle the valid moves to get random order
        Collections.shuffle(validMoveIndices);

        // Try each random valid move
        for (int moveIndex : validMoveIndices) {
            int nextRow = x + rowMoves[moveIndex];
            int nextCol = y + colMoves[moveIndex];

            // Mark the square as visited with current move number
            chessboard2[nextRow][nextCol] = moveNum + 1;

            // Recursively attempt the next move
            if (move(moveNum + 1, nextRow, nextCol, chessboard2)) {
                return true;
            }

            // Backtrack: unmark the square if this path fails
            chessboard2[nextRow][nextCol] = Integer.MIN_VALUE;
        }

        // All random paths from this point failed
        return false;
    }

    /**
     * Checks if a move stays within board boundaries
     */
    public boolean canMove(int x, int y) {
        return(x >= 0 && x < boardSize && y >= 0 && y < boardSize);
    }

    /**
     * Formats and prints the board neatly
     */
    public void print() {
        for (int i = 0; i < boardSize; i++) {
            String[] rowStrings = new String[boardSize];
            for (int j = 0; j < boardSize; j++) {
                // Format numbers to 2 digits for alignment
                rowStrings[j] = String.format("%2d", chessboard2[i][j]);
            }
            System.out.println(String.join(" ", rowStrings));
        }
    }

    public void solve() {
        InitializeBoard(); // Initialize the board first
        chessboard2[0][0] = 1; // Start knight at top-left corner (move 1)
        if (move(1, 0, 0, chessboard2)) {
            print();
        } else {
            System.out.println("No solution found with this random attempt. Try running again!");
        }
    }
}

public class TesterMain {
    public static void main(String[] args) {
        Knight test = new Knight();
        test.solve();
    }
}

Key Changes Explained #

• Random Move Logic: Instead of checking moves in a fixed order, we first collect all valid, unvisited moves, shuffle them, then try each one randomly. This ensures the knight doesn't follow the same path every time.
• Fixed Board Initialization: The chessboard2 array is now properly declared and initialized before use.
• Efficient Random Usage: A single Random instance is reused instead of creating a new one each time move() is called.
• Neat Board Printing: The print() method now formats numbers to align neatly in the console.

Important Note #

Since this uses a random backtracking approach, it might not find a solution on every run—sometimes the knight will hit a dead end early. Just rerun the program, and it'll try a new random path! If you want a more reliable solution, you could look into the Warnsdorff's algorithm (a heuristic that prioritizes moves to squares with the fewest valid next moves), but that's a different approach from pure randomness.

内容的提问来源于stack exchange，提问作者Straightup 0