Finds shortest solution for the inverse-the-square puzzle in Heroes of Hammerwatch, lol.

puzzle_solve.cxx

#include <iostream>
#include <array>
#include <vector>
#include <algorithm>
#include <span>
#include <string>
#include <optional>

using route_t    = std::array<size_t, 9>;
using field_t    = std::array<bool, 9>;
using switch_t   = std::vector<size_t>;
using switches_t = std::array<switch_t, 9>;

template <class RandomIt>
bool next_combination(RandomIt first, RandomIt n_first, RandomIt last)
{
  if(first == last || n_first == first || n_first == last)
  {
    return false;
  }

  RandomIt it_left = n_first;
  --it_left;
  RandomIt it_right = n_first;

  bool reset = false;
  while(true)
  {
    auto it = std::upper_bound(it_right, last, *it_left);

    if(it != last)
    {
      std::iter_swap(it_left, it);
      if(reset)
      {
        ++it_left;
        it_right = it;
        ++it_right;
        std::size_t left_len  = std::distance(it_left, n_first);
        std::size_t right_len = std::distance(it_right, last);
        if(left_len < right_len)
        {
          std::swap_ranges(it_left, n_first, it_right);
          std::rotate(it_right, it_right + left_len, last);
        }
        else
        {
          std::swap_ranges(it_right, last, it_left);
          std::rotate(it_left, it_left + right_len, n_first);
        }
      }
      return true;
    }
    else
    {
      reset = true;
      if(it_left == first)
      {
        break;
      }
      --it_left;
      it_right = n_first;
    }
  }
  return false;
}

void apply_switch(field_t & field, const switch_t & _switch)
{
  for(const auto idx : _switch)
    field[idx] = !field[idx];
}

bool is_field_solved(const field_t & field)
{
  for(const bool v : field)
    if(!v)
      return false;
  return true;
}

bool solve_field(const std::span<size_t> switch_seq, const field_t & initial_field, const switches_t & switches)
{
  field_t field = initial_field;

  for(const auto switch_idx : switch_seq)
    apply_switch(field, switches[switch_idx]);

  return is_field_solved(field);
}

void find_shortest_route(const field_t & initial_field, const switches_t & switches)
{
  std::vector<size_t> permutation(size(initial_field), 0);
  for(size_t i = 0; i < size(initial_field); ++i)
    permutation[i] = i;

  for(size_t perm_length = 1; perm_length <= size(initial_field); ++perm_length)
  {
    std::sort(begin(permutation), end(permutation));
    do
    {
      do
      {
        std::span<size_t> switch_sequence{begin(permutation), begin(permutation) + perm_length};
        if(solve_field(switch_sequence, initial_field, switches))
        {
          std::cout << "Found with length " << perm_length << ":\n";
          for(size_t i = 0; i < perm_length; ++i)
          {
            std::cout << permutation[i] + 1;
            if(i != perm_length - 1)
              std::cout << " -> ";
          }
          std::cout << '\n';
          return;
        }
      } while(std::next_permutation(begin(permutation), begin(permutation) + perm_length));
      std::sort(begin(permutation), begin(permutation) + perm_length);
    } while(next_combination(begin(permutation), begin(permutation) + perm_length, end(permutation)));
  }
}

std::optional<field_t> input_field(std::istream & is)
{
  std::string s;
  is >> s;
  field_t result;
  if(size(s) < size(result))
    return std::nullopt;

  for(size_t i = 0; i < size(result); ++i)
  {
    const int64_t num = s[i] - '0';
    if(num != 1 && num != 0)
      return std::nullopt;
    result[i] = num;
  }
  return result;
}

int main()
{
  const switches_t switches = {switch_t{0, 1, 3},
                               switch_t{0, 1, 2, 4},
                               switch_t{1, 2, 5},
                               switch_t{0, 3, 4, 6},
                               switch_t{1, 3, 4, 5, 7},
                               switch_t{2, 4, 5, 8},
                               switch_t{3, 6, 7},
                               switch_t{4, 6, 7, 8},
                               switch_t{5, 7, 8}};
  for(;;)
  {
    std::cout << "Enter initial field state. Example: 000111000\n>";
    const std::optional<field_t> initial_field = input_field(std::cin);
    if(!initial_field)
      continue;
    find_shortest_route(*initial_field, switches);
  }

  return 0;
}

E.g.:

Enter initial field state. Example: 000111000
>001100001
Found with length 3:
1 -> 5 -> 7