A slightly generalized optimized solver for Matt Parker's coin puzzle in C++17 https://www.think-maths.co.uk/coin-puzzle

checkers.cpp

#include <array>
#include <boost/dynamic_bitset/dynamic_bitset.hpp>
#include <future>
#include <iomanip>
#include <iostream>
#include <stdexcept>
#include <utility>
#include <vector>

enum class St { Empty, Occupied };

using Moves = std::vector<std::pair<std::size_t, std::size_t>>;
using Field = std::vector<Moves>;

using idx = std::size_t;
using state = std::size_t;
using Bitmap = boost::dynamic_bitset<>;
using NodeRef = std::pair<idx, idx>;

bool inside(idx w, idx x, idx y) {
  return x > 0 && y > 0 && y <= (w - x + 1) && x <= (w - y + 1);
}

std::size_t coordToNum(idx w, idx x, idx y) {
  return y + (w + 1) * (x - 1) - x * (x - 1) / 2 - 1;
}

#define CHECK(xm, ym)                                                          \
  if (inside(w, x + (xm), y + (ym)) &&                                         \
      inside(w, x + 2 * (xm), y + 2 * (ym))) {                                 \
    res.push_back({coordToNum(w, x + (xm), y + (ym)),                          \
                   coordToNum(w, x + 2 * (xm), y + 2 * (ym))});                \
  }

Moves moves(idx w, idx x, idx y) {
  Moves res;
  res.reserve(6);
  CHECK(1, 0);
  CHECK(-1, 0);
  CHECK(0, 1);
  CHECK(0, -1);
  CHECK(1, -1);
  CHECK(-1, 1);
  return res;
}

#undef CHECK

Field initialField(idx w) {
  Field res;
  res.resize(coordToNum(w, w, 1) + 1);
  for (idx x = 1; x <= w; ++x) {
    for (idx y = 1; y <= w; ++y) {
      if (!inside(w, x, y))
        continue;
      res[coordToNum(w, x, y)] = moves(w, x, y);
    }
  }
  return res;
}

using Res = boost::dynamic_bitset<>;

inline bool test(state st, idx i) { return (st & ((state)1 << (state)i)) != 0; }
inline state set(state st, idx i) { return (st | ((state)1 << (state)i)); }
inline state clear(state st, idx i) { return (st & ~((state)1 << (state)i)); }
inline bool testC(state st, idx w, idx x, idx y) {
  return test(st, coordToNum(w, x, y));
}
inline state setC(state st, idx w, idx x, idx y) {
  return set(st, coordToNum(w, x, y));
}
inline state clearC(state st, idx w, idx x, idx y) {
  return clear(st, coordToNum(w, x, y));
}

state flip(idx w, state n) {
  state res = 0;
  for (idx x = 1; x <= w; ++x) {
    for (idx y = 1; y <= w - x + 1; ++y) {
      if (testC(n, w, x, y))
        res = setC(res, w, y, x);
    }
  }
  return res;
}

state rot1(idx w, state n) {
  state res = 0;
  for (idx x = 1; x <= w; ++x) {
    for (idx y = 1; y <= w - x + 1; ++y) {
      if (testC(n, w, x, y))
        res = setC(res, w, y, w - x + 1 - y + 1);
    }
  }
  return res;
}

state rot2(idx w, state n) {
  state res = 0;
  for (idx x = 1; x <= w; ++x) {
    for (idx y = 1; y <= w - x + 1; ++y) {
      if (testC(n, w, x, y))
        res = setC(res, w, w - x + 1 - y + 1, x);
    }
  }
  return res;
}

void computeNext(const Field &f, Bitmap &b, Res &res, idx w, state n, idx i) {
  for (auto &move : f[i]) {
    idx removeNo = move.first;
    idx destNo = move.second;
    if (!test(n, removeNo) || test(n, destNo))
      continue;
    state newF = clear(clear(set(n, destNo), removeNo), i);
    if ((newF & (newF - 1)) == 0) { // only one bit set
      throw nullptr;
    }
    if (!b.test(newF)) {
      b.set(newF);
      b.set(flip(w, newF));
      b.set(rot1(w, newF));
      b.set(rot2(w, newF));
      b.set(flip(w, rot1(w, newF)));
      b.set(flip(w, rot2(w, newF)));
      res.set(newF);
    }
    computeNext(f, b, res, w, newF, destNo);
  }
}

void go(const Field &f, Bitmap &b, Res &res, state n, idx w) {
  for (idx i = 0; i < f.size(); ++i) {
    if (!test(n, i)) // no checker in pos
      continue;
    computeNext(f, b, res, w, n, i);
  }
}

#define SPACES "          \r"

std::size_t findPath(bool report, const Field &f, idx w,
                     const std::list<state> &ss) {
  std::size_t sz = f.size();
  std::size_t bsz = (std::size_t)1 << sz;
  Res cur_moves(bsz, false);
  Res next_moves(bsz, false);
  Bitmap bitmap(bsz, false);
  for (auto &i : ss) {
    bitmap.set(i);
    cur_moves.set(i);
  }
  auto pcur = &cur_moves;
  auto pnext = &next_moves;
  std::size_t depth = 0;
  while (pcur->any()) {
    auto &cur = *pcur;
    auto &next = *pnext;
    std::size_t cnt = cur.count();
    for (auto x = cur.find_first(); x != cur.npos; x = cur.find_next(x)) {
      if (report && (cnt & 0x1fff) == 0)
        std::cerr << SPACES << (cnt >> 13);
      cnt--;
      try {
        go(f, bitmap, next, x, w);
      } catch (std::nullptr_t) {
        if (report)
          std::cerr << SPACES;
        return depth + 1;
      }
    }
    depth++;
    if (report)
      std::cerr << SPACES;
    if (report)
      std::cerr << "depth " << depth << std::endl;
    std::swap(pcur, pnext);
    pnext->reset();
  }
  return 0;
}

const char *bg_blue = "\x1b[48;5;18m";
const char *bg_cyan = "\x1b[48;5;27m";
const char *bg_green = "\x1b[48;5;22m";
const char *bg_purple = "\x1b[48;5;54m";
const char *bg_violet = "\x1b[48;5;93m";
const char *bg_white = "\x1b[48;5;255m";
const char *fg_white = "\x1b[38;5;255m";
const char *normal = "\x1b[m";
std::array colors = {bg_green, bg_cyan, bg_blue, bg_purple, bg_violet};

void run(bool colorize, idx w, int skip) {
  Field f = initialField(w);
  std::size_t sz = f.size();
  state fullState = ((state)1 << (state)sz) - 1;
  std::list<state> initial;
  std::list<std::future<std::tuple<idx, idx, std::size_t>>> ress;
  std::size_t memory_req = 3 * ((std::size_t)1 << sz);
  std::cerr << "Required memory (GB):"
            << memory_req / (8.0 * 1024 * 1024 * 1024) << std::endl;
  bool parallel = (memory_req >> 33) <= 1;
  if (parallel) {
    std::cerr << "Will run in parallel. Progress reporting will be disabled"
              << std::endl;
  } else {
    std::cerr << "Will run serially" << std::endl;
  }
  for (idx i = 1; i <= w; ++i) {
    for (idx j = 1; j <= w - i + 1; ++j) {
      if (!(j <= i && i <= (w - j + 2) / 2))
        continue;
      if (skip > 0) {
        std::cerr << "Skipping (" << i << ", " << j << ")" << std::endl;
        skip--;
        continue;
      }
      state s = clear(fullState, coordToNum(w, i, j));
      auto policy = parallel ? std::launch::async : std::launch::deferred;
      ress.push_back(std::async(policy, [parallel, i, j, w, f, s]() {
        if (!parallel)
          std::cerr << "Starting on (" << i << ", " << j << ")" << std::endl;
        auto res = findPath(!parallel, f, w, {s});
        return std::tuple{i, j, res};
      }));
    }
  }
  std::map<NodeRef, std::size_t> map;
  std::size_t min = -1;
  for (auto &res : ress) {
    auto [i, j, p] = res.get();
    std::cout << "(" << i << ", " << j << ") :: " << p << std::endl;
    if (p > 0 && p < min)
      min = p;
    map[{i, j}] = p;
    map[{j, i}] = p;
    map[{w - i + 1 - j + 1, j}] = p;
    map[{w - i + 1 - j + 1, i}] = p;
    map[{i, w - i + 1 - j + 1}] = p;
    map[{j, w - i + 1 - j + 1}] = p;
  }
  for (idx i = w; i >= 1; --i) {
    std::cerr << std::setw(2 * (i - 1)) << "";
    for (idx j = 1; j <= w - i + 1; ++j) {
      auto n = map[{i, j}];
      if (colorize && n == 0)
        std::cerr << " " << bg_white << "  " << normal << " ";
      else if (colorize && n >= min && n - min < colors.size())
        std::cerr << " " << fg_white << colors[n - min] << std::setw(2)
                  << map[{i, j}] << normal << " ";
      else
        std::cerr << " " << std::setw(2) << map[{i, j}] << " ";
    }
    std::cerr << std::endl;
  }
}

int main(int argc, char **argv) {
  auto colorize = argc >= 2 && std::string(argv[1]) == "-c" ? true : false;
  auto s = colorize ? 1 : 0;
  if (argc < s + 2) {
    std::cerr << "Pass side length as argument" << std::endl;
    return 1;
  }
  auto w = std::atoi(argv[s + 1]);
  if (w <= 0) {
    std::cerr << "Side length needs to be greater than 0" << std::endl;
    return 1;
  }
  auto skip = argc > s + 2 ? std::atoi(argv[s + 2]) : 0;
  run(colorize, w, skip);
}