跳棋多跳计数算法

Question

我正在做我的第一个C++项目SFML -Checker。

我该怎么做呢？我已经搜索了很多网页，都没有找到答案，所以我认为这比我想象的要容易。

EDIT#1：

if (player2.isSelected(pos_x + blockSize, pos_y + blockSize))
    if (isBoardBlockEmpty(pos_x + 2 * blockSize, pos_y + 2 * blockSize))
        return true;
if (player2.isSelected(pos_x - blockSize, pos_y + blockSize))
    if (isBoardBlockEmpty(pos_x - 2 * blockSize, pos_y + 2 * blockSize))
        return true;
if (player2.isSelected(pos_x + blockSize, pos_y - blockSize))
    if (isBoardBlockEmpty(pos_x + 2 * blockSize, pos_y - 2 * blockSize))
        return true;
if (player2.isSelected(pos_x - blockSize, pos_y - blockSize))
    if (isBoardBlockEmpty(pos_x - 2 * blockSize, pos_y - 2 * blockSize))
        return true;

Answer 1

这是一个树搜索问题的实例，其中节点是板，它们之间的边是一个特定的兵，一次跳一次。

对于给定的棋盘board和位置pos处的棋子，您可以确定它可以进行哪些跳跃：

• 如果没有可能的跳转，则多跳序列结束。如果当前跳转列表不是空的，则将其报告为序列。
• 如果可能有跳跃，请通过进行跳跃(从棋盘上移除跳过的棋子)并查看是否可以从该位置进行更多跳跃来递归地探索每个跳跃。

在伪C++中，这将如下所示。请注意，这是出于教育目的而编写的，没有考虑性能。

// Assuming types pos and board were defined earlier.
using jump_list = std::vector<pos>;

// List of moves from a given starting position and board
std::vector<pos> possible_jumps(pos start, const board& board);

// Apply a move (remove the pawn from the board, move the jumping pawn)
board apply_move(const board& board, pos start, pos move);

// I'm bundling the multi-jump calculation in a struct to easily store
// the resulting jump list.
struct multi_jump {
    std::vector<jump_list> jumps;
    multi_jump(pos start, board board) {
        explore({}, start, board);
    }

    void explore(jump_list so_far, pos start, board board) {
        auto moves = possible_jumps(start, board);
        if (moves.empty()) {
            if (!so_far.empty()) {
                jumps.push_back(so_far);
            }
        } else {
            for (const auto move : moves) {
                board new_board = apply_move(board, start, move);
                jump_list new_so_far = so_far;
                new_so_far.push_back(move);
                explore(new_so_far, move, new_board);
            }
        }
    }
};

最后，您可以从起始位置和板检索跳跃列表，如下所示：

jump_list jumps = multi_jump(start, board).jumps;