X-Git-Url: http://git.scottworley.com/slidingtile/blobdiff_plain/e86755d75f4040ae6619702a6501325ea81b03e1..8e3c9cff3a9dbe44519dcea244d528809cc45821:/sliding_tile_lib.h diff --git a/sliding_tile_lib.h b/sliding_tile_lib.h index 7b16a51..f0753fc 100644 --- a/sliding_tile_lib.h +++ b/sliding_tile_lib.h @@ -1,20 +1,50 @@ +#ifndef _SLIDING_TILE_LIB_H +#define _SLIDING_TILE_LIB_H + +#include +#include +#include +#include +#include + const int BOARD_DIM = 4; const int BOARD_SIZE = BOARD_DIM * BOARD_DIM; -signed char adjacent[BOARD_SIZE][5] = { - 1, 4, -1, -1, -1, - 0, 2, 5, -1, -1, - 1, 3, 6, -1, -1, - 2, 7, -1, -1, -1, - 0, 5, 8, -1, -1, - 1, 4, 6, 9, -1, - 2, 5, 7, 10, -1, - 3, 6, 11, -1, -1, - 4, 9, 12, -1, -1, - 5, 8, 10, 13, -1, - 6, 9, 11, 14, -1, - 7, 10, 15, -1, -1, - 8, 13, -1, -1, -1, - 9, 12, 14, -1, -1, - 10, 13, 15, -1, -1, - 11, 14, -1, -1, -1, + +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 prev); + ~Step(); + + Board board; + std::shared_ptr prev; + + std::vector> successors(std::shared_ptr 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 find_path(const std::string& start, const std::string& goal, unsigned max_frontier); +std::shared_ptr find_path(const Board& start, const Board& goal, unsigned max_frontier); + +#endif /* _SLIDING_TILE_LIB_H */