ボタンを押すとそのボタンと周囲4近傍のボタンの ON/OFF が反転して，全てのボタンを ON にすればクリアのあのゲームを解くやつ

buttonpuzzle.cpp

#include <iostream>
#include <queue>
#include <vector>
#include <array>
#include <map>
#include <bitset>
#include <utility>
#include <algorithm>
const int inf = 1e9;
using state = std::pair<int, int>;

int main (void) {
  const int start = 0b000000000; // 初期状態
  const int goal  = 0b111111111; // ゴール
  const std::array<int, 9> revbits{
    0b110100000,
    0b111010000,
    0b011001000,
    0b100110100,
    0b010111010,
    0b001011001,
    0b000100110,
    0b000010111,
    0b000001011
  };

  std::priority_queue<state, std::vector<state>, std::greater<state>> q;
  q.push(std::make_pair(0, start));

  std::map<int, int> previous;
  for (int st = 0; st < (1 << 10) - 1; ++st)
    previous[st] = -1;

  std::map<int, int> distance;
  for (int st = 0; st < (1 << 10) - 1; ++st)
    distance[st] = inf;
  distance[start] = 0;

  std::map<int, int> te;

  while (!q.empty()) {
    const auto p = q.top();
    q.pop();

    int cost, now;
    std::tie(cost, now) = p;

    if (now == goal)
      break;

    for (unsigned int i = 0; i < revbits.size(); ++i) {
      const int next = now ^ revbits[i];
      const int newcost = cost + 1;

      if (distance[next] > newcost) {
        distance[next] = newcost;
        previous[next] = now;
        te[next] = i;
        q.push(std::make_pair(newcost, next));
      }
    }
  }

  std::cout << distance[goal] << std::endl;

  int now = goal;
  while (now != start) {
    const int nowte = te[now];
    std::cout << nowte % 3 << "," << nowte / 3 << std::endl;
    now = previous[now];
  }

  return 0;
}