git.scottworley.com Git - slidingtile/blob - sliding_tile_lib.h

   1 #ifndef _SLIDING_TILE_LIB_H
   2 #define _SLIDING_TILE_LIB_H
   3
   4 #include <istream>
   5 #include <memory>
   6 #include <ostream>
   7 #include <string>
   8 #include <vector>
   9
  10 const int BOARD_DIM = 4;
  11 const int BOARD_SIZE = BOARD_DIM * BOARD_DIM;
  12
  13 struct InvertedBoard {
  14   signed char pos[BOARD_SIZE];
  15 };
  16
  17 struct Board {
  18   signed char board[BOARD_SIZE];
  19   bool is_valid() const;
  20   signed char hole() const;
  21   InvertedBoard invert() const;
  22   int distance(const Board& o) const;
  23   int distance(const InvertedBoard& invo) const;
  24   bool operator==(const Board& o) const;
  25   bool operator!=(const Board& o) const;
  26   bool operator<(const Board& o) const;
  27 };
  28 std::istream& operator>>(std::istream& is, Board& board);
  29 std::ostream& operator<<(std::ostream& os, const Board& board);
  30
  31 struct Step {
  32   Step(Board board, std::shared_ptr<Step> prev);
  33   ~Step();
  34
  35   Board board;
  36   std::shared_ptr<Step> prev;
  37
  38   std::vector<std::shared_ptr<Step>> successors(std::shared_ptr<Step> shared_this) const;
  39   int length() const;
  40   int cost(const InvertedBoard& invgoal) const;
  41
  42   static signed char adjacent[BOARD_SIZE][5];
  43   static int count;
  44 };
  45 std::ostream& operator<<(std::ostream& os, const Step& step);
  46
  47 std::shared_ptr<Step> find_path(const std::string& start, const std::string& goal, unsigned max_frontier);
  48 std::shared_ptr<Step> find_path(const Board& start, const Board& goal, unsigned max_frontier);
  49
  50 #endif /* _SLIDING_TILE_LIB_H */