15 puzzle.cpp

#include <algorithm>
#include <cassert>
#include <cstdlib>
#include <iostream>
#include <limits>
#include <list>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <tuple>
#include <unordered_set>
#include <vector>

using namespace std;

constexpr size_t DIM = 3;
constexpr size_t SIZE = DIM * DIM;

// first, we need to mode l a board which must be 4 x 4.
struct Board {
  std::array<unsigned, SIZE> data;

  void set(uint8_t x, uint8_t y, uint8_t v) {
    const size_t index = x + y * DIM;
    assert(index < SIZE);
    data[index] = v;
  }

  uint8_t get(uint8_t x, uint8_t y) const {
    const size_t index = x + y * DIM;
    assert(index < SIZE);
    return data[index];
  }

  void move(uint8_t x, uint8_t y, uint8_t to_x, uint8_t to_y) {
    assert(get(to_x, to_y) == 0);
    // todo: disallow diagonals in assert.
    std::swap(data[x + y * DIM], data[to_x + to_y * DIM]);
  }

  tuple<size_t, size_t> find_0() const {
    for (size_t i = 0; i < SIZE; ++i) {
      if (data[i] == 0) {
        return {i % DIM, i / DIM};
      }
    }
    assert(false);
    return {0, 0};
  }
};

std::ostream &operator<<(std::ostream &os, const Board &b) {
  constexpr auto hex_chars = "0123456789ABCDEF";
  for (size_t i = 0; i < DIM; i++) {
    for (size_t j = 0; j < DIM; ++j) {
      const auto v = b.get(j, i);
      os << (v == 0 ? ' ' : hex_chars[v]);
    }
    os << "\n";
  }
  return os;
}

int state_badness(const Board &b, bool verbose = false) {
  unsigned badness = 0;

  for (size_t x = 0; x < DIM; ++x) {
    for (size_t y = 0; y < DIM; ++y) {
      auto v = b.get(x, y);
      v = v == 0 ? SIZE : v;
      size_t expected_x = (v - 1) % DIM;
      size_t expected_y = (v - 1) / DIM;

      auto diff =
          std::abs((long)(expected_x - x)) + std::abs((long)(expected_y - y));

      if (verbose) {
        cout << "value " << (int)v << " at pos " << x << ", " << y
             << " has diff " << diff << "\n";
      }
      badness += diff;
    }
  }
  return badness;
}

vector<tuple<int, int>> possible_moves(const Board &b) {
  vector<tuple<int, int>> result;
  auto [zx, zy] = b.find_0();
  if (zx > 0)
    result.emplace_back(-1, 0);
  if (zx < 2)
    result.emplace_back(+1, 0);
  if (zy > 0)
    result.emplace_back(0, -1);
  if (zy < 2)
    result.emplace_back(0, +1);
  return result;
}

struct SolutionCandidate {
  Board b;
  int badness; // todo: rename to priority

  SolutionCandidate(const Board &b, int badness) : b(b), badness(badness) {}

  bool operator>(const SolutionCandidate &s) const {
    return this->badness > s.badness;
  }
};

bool operator<(const Board &lhs, const Board &rhs) {
  return lhs.data < rhs.data;
};

bool is_solvable(const Board &b) {
  // e -- number or row of space cell (0)
  auto [_, zy] = b.find_0();
  auto e = zy + 1;

  int sum = 0;
  for (int i = 0; i < SIZE; ++i) {
    sum += b.data[i] + e;
  }

  if (sum % 2 == 1) {
    return false;
  } else {
    return true;
  }
}

// Board from_string(std::string s) {
//   assert(s.size() == 9 || s.size() == 16);
// }

Board get_sample_board() {
  Board b;
  if constexpr (DIM == 4) {
    // vector<int> p = {1, 3, 11, 7, 0, 9, 5, 4, 15, 12, 8, 10, 2, 13, 6, 14};
    // vector<int> p = {15, 2, 1, 12, 8, 5, 6, 11, 4, 9, 10, 7, 3, 14, 13, 0};
    // vector<int> p = {0, 7, 15, 12, 3, 1, 14, 5, 11, 13, 4, 2, 9, 6, 8, 10};
    // vector<int> p = {2, 1, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0};
    vector<int> p = {6, 13, 7, 10, 8, 9, 11, 0, 15, 2, 12, 5, 14, 3, 1, 4};
    copy_n(p.begin(), 16, b.data.begin());
  } else if constexpr (DIM == 3) {
    vector<int> p = {1, 2, 3, 0, 4, 6, 7, 5, 8};
    copy_n(p.begin(), 16, b.data.begin());
  }
  return b;
}

int main(int argc, char *argv[]) {
  // Default board.
  Board b;
  for (size_t i = 0; i < SIZE; ++i) {
    b.data[i] = i < SIZE - 1 ? i + 1 : 0;
  }

  if (argc == 2 && string(argv[1]) == "rand") {
    std::random_device rd;
    std::mt19937 uniform_gen(rd());
    std::shuffle(b.data.begin(), b.data.end(), uniform_gen);
  } else if (argc == 2) {
    cerr << "not implemented\n";
    return -1;
    // auto board_spec = string(argv[1]);
    // if (board_spec.size() == 16) {
    //   b = from_string(board_spec);
    //   // ..
    // } else if (board_spec.size() == 9) {
    //   // ..
    // } else {
    //   cerr << "invalid board, must be of size 3 or 4\n";
    //   return -1;
    // }
  } else {
    cout << "sample board\n";
    b = get_sample_board();
  }

  cout << "initial random state (badness: " << state_badness(b) << "):\n"
       << b << "\n";

  map<Board, int> cost_so_far;
  map<Board, Board> parent_state;
  std::priority_queue<SolutionCandidate, vector<SolutionCandidate>,
                      std::greater<SolutionCandidate>>
      frontier;
  frontier.emplace(b, state_badness(b));
  cost_so_far[b] = 0;

  ([&cost_so_far, &parent_state, &frontier]() {
    int iteration = 0;
    while (!frontier.empty()) {

      SolutionCandidate s_prime = frontier.top();
      frontier.pop();

      auto curr_cost = cost_so_far[s_prime.b];

      if (iteration++ % 100'000 == 0) {
        cout << iteration++ << ": evaluation solution of priority "
             << s_prime.badness << "(badness: " << state_badness(s_prime.b)
             << ")"
             << "\n"
             << s_prime.b << "\n";
      }

      for (auto [dx, dy] : possible_moves(s_prime.b)) {
        Board t = s_prime.b;

        auto [zx, zy] = t.find_0();
        t.move(zx + dx, zy + dy, zx, zy);

        auto new_cost = curr_cost + 1;

        if (cost_so_far.find(t) == cost_so_far.end() ||
            new_cost < cost_so_far[t]) {

          cost_so_far[t] = new_cost;
          auto t_badness = state_badness(t);
          if (t_badness == 0) {
            cout << "found target state at iteration " << iteration << ":\n"
                 << t << "\n";

            // unroll solution.
            parent_state[t] = s_prime.b;
            list<Board> stack;
            auto x = t;
            while (true) {
              if (parent_state.find(x) == parent_state.end()) {
                break;
              }
              stack.push_back(x);
              x = parent_state[x];
            }
            stack.reverse();
            for (auto s : stack) {
              cout << s << "\n";
            }
            std::exit(0);
          }
          auto priority = new_cost + t_badness;
          frontier.emplace(t, priority);
          parent_state[t] = s_prime.b;
        }
      }
    }
  })();
  cout << "solution not found\n";
}