我正在尝试使用深度优先搜索算法解决Peg Solitaire问题——这个游戏应该是可以被解决的，因为“现代计算机可以在合理的时间内轻松检查所有游戏位置”。即使经过23小时，算法仍未找到任何解决方案。我进行了网络搜索，并找到了论文"Depth-first search solves peg solitaire"。我尝试了该论文中的C程序，程序刚开始就立即找到了第一个解决方案。我比较了两种算法。两种算法的主要区别在于它们如何寻找可能的跳棋。我的算法从左上角到右下角“搜索空洞”（检查每个空洞是否有可能的跳棋），而论文算法从左上角到右下角“搜索棋子”（检查每个棋子是否有可能的跳棋）。两种算法都按照它们发现的顺序尝试跳棋。为了强调差异：
- 分析空洞：运行时间23小时无解
- 分析钉子：运行时间10秒，2940个解决方案
问题：为什么在搜索跳跃方式时会有如此巨大的（无法解决/立即解决）差异？为什么检查钉子而不是检查空洞以寻找可能的跳跃更好？
您可以尝试使用以下C ++程序进行算法。为了使其紧凑，我已删除了较不重要的部分（打印板，生成初始位板，...）。
#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;
}