跳棋多跳跃计数算法

Question

我正在做我的第一个C 项目。不幸的是，我发明了递归功能，这将使我可以检查所有可能的跳跃组合，并将我返回坐标。

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

编辑＃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;