Bound the frontier. I.e., do beam search.

[slidingtile] / sliding_tile_lib.h

#ifndef _SLIDING_TILE_LIB_H
#define _SLIDING_TILE_LIB_H

#include <istream>
#include <memory>
#include <ostream>
#include <string>
#include <vector>

const int BOARD_DIM = 4;
const int BOARD_SIZE = BOARD_DIM * BOARD_DIM;

struct InvertedBoard {
  signed char pos[BOARD_SIZE];
};

struct Board {
  signed char board[BOARD_SIZE];
  bool is_valid() const;
  signed char hole() const;
  InvertedBoard invert() const;
  int distance(const Board& o) const;
  int distance(const InvertedBoard& invo) const;
  bool operator==(const Board& o) const;
  bool operator!=(const Board& o) const;
  bool operator<(const Board& o) const;
};
std::istream& operator>>(std::istream& is, Board& board);
std::ostream& operator<<(std::ostream& os, const Board& board);

struct Step {
  Step(Board board, std::shared_ptr<Step> prev);
  ~Step();

  Board board;
  std::shared_ptr<Step> prev;

  std::vector<std::shared_ptr<Step>> successors(std::shared_ptr<Step> shared_this) const;
  int length() const;
  int cost(const InvertedBoard& invgoal) const;

  static signed char adjacent[BOARD_SIZE][5];
  static int count;
};
std::ostream& operator<<(std::ostream& os, const Step& step);

std::shared_ptr<Step> find_path(const std::string& start, const std::string& goal, unsigned max_frontier);
std::shared_ptr<Step> find_path(const Board& start, const Board& goal, unsigned max_frontier);

#endif /* _SLIDING_TILE_LIB_H */