Peg Solitaire - check pins and check holes to find depth

Question

I am trying to solve Peg Solitaire using the depth search algorithm - it should be possible to solve the game, since "modern computers can easily learn all the game positions in a reasonable amount of time . " Even after 23 hours, the algorithm did not find any solution. I did a web search and found the paper "Deep search allows solitaire . " I tried a c-program from paper and the first solution was found immediately after starting the program. I compared the algorithms. The main difference between the algorithms is how they find possible jumping-jumping. Although my algorithm looks for a board for holes from top to left to right (each hole is checked if jumps are possible), the paper algorithm searches for a board for pegstop left right (each binding is checked if jumping is possible). Both algorithms trying to jump in the order in which they are found. To emphasize the difference:

• Hole Analysis: Runtime 23 hours without solution
• Code Analysis: Runtime 10 seconds, 2940 solutions

Question: Why is there such a gigantic (not solvable / immediately resolved) difference in how to look for a jumping board? Why is it better to check the pins instead of checking the holes for possible jumps?

You can try the algorithm with the following C ++ program. To keep it compact, I deleted the less important parts (printing the board, creating the initial bit board ...).

#include <iostream>
#include <ctime>
#include <vector>
#include <utility>
#include <ctime>

typedef unsigned __int64 ui64;
typedef std::vector<std::pair<int, int> > 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;
}

Answer 1

- , , (). , , .

, : , , : http://www.durangobill.com/Peg33.html