Пасьянс Peg - проверка колышков против проверки отверстий при поиске в глубину вперед

Я пытаюсь разложить пасьянс Peg Solitaire с помощью алгоритма поиска по глубине - это должно быть возможно, поскольку "современные компьютеры могут легко изучить все игровые позиции за разумное время" ... должно быть возможно решить игру, поскольку "современные компьютеры могут легко изучить все игровые позиции за разумное время". Даже спустя 23 часа алгоритм не нашел никакого решения. Я провел поиск в Интернете и нашел статью "Depth-first search solves peg solitaire". Я попробовал программу на языке Си из этой статьи и первое решение было найдено сразу после запуска программы. Я сравнил алгоритмы. Основное различие между алгоритмами заключается в том, как они находят возможные переходы через колышки. В то время как мой алгоритм ищет на доске отверстия сверху слева направо и снизу вверх (каждое отверстие проверяется на наличие возможных прыжки), бумажный алгоритм ищет на доске колышки сверху слева вниз справа сверху вниз (каждый колышек проверяется на возможность прыжков). Оба алгоритма перебирают переходы в том порядке, в котором они были найдены. Чтобы подчеркнуть разницу:

• Анализ отверстий: Время выполнения 23 часа, ни одного решения
• Анализ колышков: Время выполнения 10 секунд, 2940 решений

Вопрос: Почему существует такая гигантская (не решаемая / сразу решаемая) разница в том, как искать переходы на доске? Почему лучше проверять колышки вместо того, чтобы проверять отверстия на наличие возможных переходов?

Вы можете попробовать алгоритм с помощью следующей программы на C++. Для компактности я удалил менее важные части (печать доски, генерация начальной битовой доски, ...).

#include 
#include 
#include 
#include 
#include 

typedef unsigned __int64 ui64;
typedef std::vector > vecjumps; // first=from, second=to
ui64 moves = 0;    // Number of moves made so far
int solutions = 0; // Number of solutions found so far
clock_t start;     // To measure time

//          Bitboard
//   Board            Bits         
//  ------------------------------
//    ***           02 03 04      
//    ***           10 11 12      
//  *******   16 17 18 19 20 21 22
//  ***o***   24 25 26 27 28 29 30
//  *******   32 33 34 35 36 37 38
//    ***           42 43 44      
//    ***           50 51 52      
const ui64 bitboard = 0x001c1c7f7f7f1c1c; // 1ULL << 2 | 1ULL << 3 | ...
ui64 board = bitboard & ~(1ULL << 27);    // Initial Board: Bit 27 <=> Hole

// To try the hole-version: Swap Commented and Uncommented parts
vecjumps getMoves(ui64 b)
{
    // Find the possible jumps through bit-shift operations. mr <=> right jump
    // possibilities. The inverted Board represents the Holes. Shifting the
    // board by 16 right/left --> moving all pegs up/down. Shifting the board
    // by 1 --> moving all pegs left/right
    //ui64 mr = (((b >> 1) & b) <<  2) & ~b & bitboard;
    //ui64 md = (((b >> 8) & b) << 16) & ~b & bitboard;
    //ui64 ml = (((b >> 1) & b) >>  1) & ~b & bitboard;
    //ui64 mu = (((b >> 8) & b) >>  8) & ~b & bitboard;
    ui64 mr = ((((b >> 1) & b) <<  2) & ~b & bitboard) >>  2;
    ui64 md = ((((b >> 8) & b) << 16) & ~b & bitboard) >> 16;
    ui64 ml = ((((b >> 1) & b) >>  1) & ~b & bitboard) <<  2;
    ui64 mu = ((((b >> 8) & b) >>  8) & ~b & bitboard) << 16;

    vecjumps jumps;
    jumps.reserve(12);
    for (int i = 2; i < 53; i++)
    {
        //if (mr & (1ULL << i)) jumps.push_back(std::make_pair(i -  2, i));
        //if (md & (1ULL << i)) jumps.push_back(std::make_pair(i - 16, i));
        //if (ml & (1ULL << i)) jumps.push_back(std::make_pair(i +  2, i));
        //if (mu & (1ULL << i)) jumps.push_back(std::make_pair(i + 16, i));
        if (mr & (1ULL << i)) jumps.push_back(std::make_pair(i, i + 2));
        if (md & (1ULL << i)) jumps.push_back(std::make_pair(i, i + 16));
        if (ml & (1ULL << i)) jumps.push_back(std::make_pair(i, i - 2));
        if (mu & (1ULL << i)) jumps.push_back(std::make_pair(i, i - 16));
    }
    return jumps;
}

void makeMove(ui64& b, int from, int to)
{
    // Through a xor-instruction, a jump from 11 to 27 includes 19
    // 19 = (11 + 27) / 2
    b ^= 1ULL << from | 1ULL << (from + to) / 2 | 1ULL << to;
    moves++;
    if (moves % 10000000 == 0)
        printf("(%8d, %14llu moves, %lf)\n", 
            solutions, moves, (double)(clock() - start) / CLOCKS_PER_SEC);
}

// Depth First Search Algorithm
bool findSolution(int depth)
{
    if (!depth) return ((1ULL << 27) & board);
    vecjumps jumps = getMoves(board);
    for (vecjumps::const_iterator cit = jumps.begin(); cit != jumps.end();
         ++cit)
    {
        ui64 copy = board;
        makeMove(board, (*cit).first, (*cit).second);
        if (findSolution(depth - 1)) solutions++;
        board = copy;
    }
    return false;
}

int main()
{
    start = clock();
    findSolution(31);   
    printf("(%8d, %14llu moves, %lf)\n", 
        solutions, moves, (double)(clock() - start) / CLOCKS_PER_SEC);
    return 0;
}