Я пытаюсь решить Peg Solitaire с помощью алгоритма поиска в глубину - это
должно быть возможно решить игру, поскольку "современные компьютеры могут легко исследовать
все игровые позиции за разумное время ". Даже после 23 часов
алгоритм не нашел никакого решения. Я сделал поиск в Интернете и нашел газету
"Поиск в глубину решает пасьянс" . Я попробовал 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;
}