Это пример проблемы поиска по дереву, когда узлы - это доски, а ребра между ними - отдельная пешка, делающая по одному прыжку за раз.
Для данной доски 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;