ansiwen

octogram

Nov 28th, 2011
5,166
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //
  2. // fast octogram puzzle solver
  3. //
  4. // copyright 2011 Sven Anderson <sven@anderson.de>
  5. //
  6. //    This program is free software: you can redistribute it and/or modify
  7. //    it under the terms of the GNU General Public License as published by
  8. //    the Free Software Foundation, either version 3 of the License, or
  9. //    (at your option) any later version.
  10. //
  11. //    This program is distributed in the hope that it will be useful,
  12. //    but WITHOUT ANY WARRANTY; without even the implied warranty of
  13. //    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14. //    GNU General Public License for more details.
  15. //
  16. //    You should have received a copy of the GNU General Public License
  17. //    along with this program.  If not, see <http://www.gnu.org/licenses/>.
  18. //
  19.  
  20. #include <stdlib.h>
  21.  
  22. #include <iostream>
  23. #include <list>
  24. #include <vector>
  25.  
  26. using namespace std;
  27.  
  28. // max size of tiles
  29. const int MAX_WIDTH = 5;
  30. const int MAX_HEIGHT = 5;
  31.  
  32. // size of board
  33. const int BOARD_WIDTH = 8;
  34. const int BOARD_HEIGHT = 8;
  35.  
  36. // list of available tiles
  37. const char INIT_TILES[][MAX_HEIGHT][MAX_WIDTH] = {
  38.     {
  39.         { 1, 1, 1, 1, 1}
  40.     },
  41.     {
  42.         { 1, 1, 1, 1},
  43.         { 1 }
  44.     },
  45.     {
  46.         { 1, 1, 1},
  47.         { 1 },
  48.         { 1 }
  49.     },
  50.     {
  51.         { 1, 1, 1, 1 },
  52.         { 0, 1 }
  53.     },
  54.     {
  55.         { 1, 1 },
  56.         { 0, 1, 1 },
  57.         { 0, 1 }
  58.     },
  59.     {
  60.         { 0, 1 },
  61.         { 1, 1, 1 },
  62.         { 0, 1 }
  63.     },
  64.     {
  65.         { 1, 1, 1 },
  66.         { 1, 1 }
  67.     },
  68.     {
  69.         { 1 },
  70.         { 1, 1, 1 },
  71.         { 1 }
  72.     },
  73.     {
  74.         { 0, 1, 1 },
  75.         { 1, 1 },
  76.         { 1 }
  77.     },
  78.     {
  79.         { 1, 1 },
  80.         { 1 },
  81.         { 1, 1 }
  82.     },
  83.     {
  84.         { 0, 1, 1, 1 },
  85.         { 1, 1 }
  86.     },
  87.     {
  88.         { 0, 1, 1 },
  89.         { 0, 1 },
  90.         { 1, 1 }
  91.     },
  92.     {
  93.         { 1, 1 },
  94.         { 1, 1 }
  95.     }
  96. };
  97.  
  98. struct Position {
  99.     int x;
  100.     int y;
  101.     Position() : x(0), y(0) {}
  102.     Position(int xx, int yy) : x(xx), y(yy) {}
  103.     bool operator==(const Position &rhs) const { return (x == rhs.x && y == rhs.y); }
  104.     bool operator!=(const Position &rhs) const { return (!(*this == rhs)); }
  105.     bool operator<(const Position &rhs) const {
  106.         return ( y < rhs.y || (y == rhs.y && x < rhs.x ));
  107.     }
  108. };
  109.  
  110. class Board; // forward declaration
  111.  
  112. //
  113. // OrientedTile has a distinct orientation
  114. //
  115. class OrientedTile {
  116.     int width_;
  117.     int height_;
  118.     char sign_;                 // character used to mark board fields
  119.     vector<Position> body_;     // list of body coordinates
  120.     vector<Position> border_;   // list of border coordinates
  121. public:
  122.     OrientedTile();
  123.     OrientedTile(const char data[MAX_HEIGHT][MAX_WIDTH], const char sign);
  124.     bool operator==(const OrientedTile &rhs) const;
  125.     const vector<Position> &body() const { return body_; }
  126.     const vector<Position> &border() const { return border_; }
  127.     char sign() const { return sign_; }
  128.     OrientedTile rotated() const;
  129.     OrientedTile mirrored() const;
  130.     bool insert(Board &board, int x, int y) const;
  131.     void remove(Board &board, int x, int y) const;
  132.     void dump() const;
  133. };
  134.  
  135. //
  136. // Tile represents a tile regardless of it's orientation
  137. //
  138. class Tile {
  139.     vector<OrientedTile> orientations_; // list of all unique orientations
  140. public:
  141.     Tile(const char array[MAX_HEIGHT][MAX_WIDTH], char sign);
  142.     const vector<OrientedTile> &orientations() const { return orientations_; }
  143.     bool matches(OrientedTile oriented_tile);
  144.     void dump() const;
  145. };
  146.  
  147.  
  148. //
  149. // The board which has to be filled with tiles
  150. // it holds a list of tiles not on the board yet and a queue
  151. // of board fields that need to be filled next.
  152. //
  153. class Board {
  154.     char data_[BOARD_HEIGHT][BOARD_WIDTH];  // the board
  155.     vector<Tile> tiles_;                    // list of all available tiles
  156.     list<Tile *> unused_tiles_;             // list of tiles not on the board yet
  157.     vector<Position> queue_;                // queue of fields to fill next
  158.     vector<Position> new_seeds_;            // temporary list for new seed fields
  159.     int solutions_;                         // solutions counter
  160. public:
  161.     Board(const vector<Tile> &tiles);
  162.     int width() const { return BOARD_WIDTH; }
  163.     int height() const { return BOARD_HEIGHT; }
  164.     vector<Position> &new_seeds() { return new_seeds_; }
  165.     char &at(int x, int y) { return data_[y][x]; }
  166.     const char at(int x, int y) const { return data_[y][x]; }
  167.     void fill(int queue_position);
  168.     void fill() { queue_.push_back(Position(0, 0)); fill(0); }
  169.     void dump() const;
  170. };
  171.  
  172.  
  173. OrientedTile::OrientedTile() : width_(0), height_(0), sign_(0) {};
  174.  
  175. OrientedTile::OrientedTile(const char data[MAX_HEIGHT][MAX_WIDTH], const char sign) : width_(0), height_(0), sign_(sign) {
  176.     for (int row=0; row < MAX_HEIGHT+2; ++row) {
  177.         for (int col=0; col < MAX_WIDTH+2; ++col) {
  178.             if (row > 0 && row < MAX_HEIGHT+1
  179.                 && col > 0 && col < MAX_WIDTH+1
  180.                 && data[row-1][col-1]) {
  181.                 height_ = row+2;
  182.                 if (width_ < col+2)
  183.                     width_ = col+2;
  184.                 body_.push_back(Position(col, row));
  185.             } else
  186.             if ((row > 0 && row < MAX_HEIGHT+1 && col > 1 && data[row-1][col-2])
  187.                 || (row > 0 && row < MAX_HEIGHT+1 && col < MAX_WIDTH && data[row-1][col])
  188.                 || (col > 0 && col < MAX_WIDTH+1 && row > 1 && data[row-2][col-1])
  189.                 || (col > 0 && col < MAX_WIDTH+1 && row < MAX_HEIGHT && data[row][col-1]))
  190.                     border_.push_back(Position(col, row));
  191.         }
  192.     }
  193. }
  194.  
  195. bool OrientedTile::operator==(const OrientedTile &rhs) const {
  196.     if (width_ != rhs.width_ || height_ != rhs.height_)
  197.         return false;
  198.     if (body_.size() != rhs.body_.size())
  199.         return false;
  200.     vector<Position>::const_iterator i = body_.begin();
  201.     vector<Position>::const_iterator j = rhs.body_.begin();
  202.     for (; i != body_.end() ; ++i, ++j) {
  203.         if (*i != *j)
  204.             return false;
  205.     }
  206.     return true;
  207. }
  208.  
  209. OrientedTile OrientedTile::rotated() const {
  210.     OrientedTile rotated;
  211.     rotated.width_ = height_;
  212.     rotated.height_ = width_;
  213.     rotated.sign_ = sign_;
  214.     list<Position> tmp_list;
  215.     for (vector<Position>::const_iterator i = body_.begin(); i != body_.end(); ++i) {
  216.         tmp_list.push_back(Position(height_-1-i->y, i->x));
  217.     }
  218.     tmp_list.sort();
  219.     rotated.body_.insert(rotated.body_.end(), tmp_list.begin(), tmp_list.end());
  220.     tmp_list.clear();
  221.     for (vector<Position>::const_iterator i = border_.begin(); i != border_.end(); ++i) {
  222.         tmp_list.push_back(Position(height_-1-i->y, i->x));
  223.     }
  224.     tmp_list.sort();
  225.     rotated.border_.insert(rotated.border_.end(), tmp_list.begin(), tmp_list.end());
  226.     return rotated;
  227. }
  228.  
  229. OrientedTile OrientedTile::mirrored() const {
  230.     OrientedTile mirrored;
  231.     mirrored.width_ = height_;
  232.     mirrored.height_ = width_;
  233.     mirrored.sign_ = sign_;
  234.     list<Position> tmp_list;
  235.     for (vector<Position>::const_iterator i = body_.begin(); i != body_.end(); ++i) {
  236.         tmp_list.push_back(Position(i->y, i->x));
  237.     }
  238.     tmp_list.sort();
  239.     mirrored.body_.insert(mirrored.body_.end(), tmp_list.begin(), tmp_list.end());
  240.     tmp_list.clear();
  241.     for (vector<Position>::const_iterator i = border_.begin(); i != border_.end(); ++i) {
  242.         tmp_list.push_back(Position(i->y, i->x));
  243.     }
  244.     tmp_list.sort();
  245.     mirrored.border_.insert(mirrored.border_.end(), tmp_list.begin(), tmp_list.end());
  246.     return mirrored;
  247. }
  248.  
  249. bool OrientedTile::insert(Board &board, int x, int y) const {
  250.     if (x < 0 || y < 0 || x+width_-2 > board.width() || y+height_-2 > board.height())
  251.         return false;
  252.     --x;
  253.     --y;
  254.     for (vector<Position>::const_iterator i = body_.begin(); i != body_.end(); ++i) {
  255.         if (board.at(i->x+x, i->y+y))
  256.             return false;
  257.     }
  258.     for (vector<Position>::const_iterator i = body_.begin(); i != body_.end(); ++i) {
  259.         board.at(i->x+x, i->y+y) = sign_;
  260.     }
  261.     for (vector<Position>::const_iterator i = border_.begin(); i != border_.end(); ++i) {
  262.         int xx = i->x+x;
  263.         int yy = i->y+y;
  264.         if (xx >= 0 && xx < board.width() && yy >= 0 && yy < board.height())
  265.             board.new_seeds().push_back(Position(xx, yy));
  266.     }
  267.     return true;
  268. }
  269.  
  270. void OrientedTile::remove(Board &board, int x, int y) const {
  271.     --x;
  272.     --y;
  273.     for (vector<Position>::const_iterator i = body_.begin(); i != body_.end(); ++i) {
  274.         board.at(i->x+x, i->y+y) = 0;
  275.     }
  276. }
  277.  
  278. void OrientedTile::dump() const {
  279.     char data[MAX_HEIGHT+2][MAX_WIDTH+2] = {};
  280.     std::cout << "--- ORIENTED-TILE-DUMP ---" << endl;
  281.     for (vector<Position>::const_iterator i = body_.begin(); i != body_.end(); ++i) {
  282.         data[i->y][i->x] = '#';
  283.     }
  284.     for (vector<Position>::const_iterator i = border_.begin(); i != border_.end(); ++i) {
  285.         if (data[i->y][i->x] == '#')
  286.             std::cout << "Warning: collision of border and body!" << endl;
  287.         data[i->y][i->x] = '+';
  288.     }
  289.     for (int row=0; row < height_; ++row) {
  290.         for (int col=0; col < width_; ++col) {
  291.             char val = data[row][col];
  292.             char sign = '.';
  293.             if (val)
  294.                 sign = val;
  295.             std::cout << sign;
  296.         }
  297.         std::cout << endl;
  298.     }
  299.     std::cout << "size: " << width_ << "x" << height_ << endl;
  300. }
  301.  
  302.  
  303. Tile::Tile(const char array[MAX_HEIGHT][MAX_WIDTH], char sign) {
  304.     OrientedTile tile(array, sign);
  305.     orientations_.push_back(tile);
  306.     tile = tile.rotated();
  307.     if (!matches(tile))
  308.         orientations_.push_back(tile);
  309.     tile = tile.rotated();
  310.     if (!matches(tile))
  311.         orientations_.push_back(tile);
  312.     tile = tile.rotated();
  313.     if (!matches(tile))
  314.         orientations_.push_back(tile);
  315.     tile = tile.mirrored();
  316.     if (!matches(tile))
  317.         orientations_.push_back(tile);
  318.     tile = tile.rotated();
  319.     if (!matches(tile))
  320.         orientations_.push_back(tile);
  321.     tile = tile.rotated();
  322.     if (!matches(tile))
  323.         orientations_.push_back(tile);
  324.     tile = tile.rotated();
  325.     if (!matches(tile))
  326.         orientations_.push_back(tile);
  327. }
  328.  
  329. bool Tile::matches(OrientedTile oriented_tile) {
  330.     for (vector<OrientedTile>::const_iterator i = orientations_.begin(); i != orientations_.end(); ++i) {
  331.         if (*i == oriented_tile)
  332.             return true;
  333.     }
  334.     return false;
  335. }
  336.  
  337. void Tile::dump() const {
  338.     std::cout << "****** TILE-DUMP ******" << endl;
  339.     std::cout << "Orientations: " << orientations_.size() << endl;
  340.     for (vector<OrientedTile>::const_iterator i = orientations_.begin(); i != orientations_.end(); ++i) {
  341.         i->dump();
  342.     }
  343.     std::cout << endl;
  344. }
  345.  
  346. Board::Board(const vector<Tile> &tiles) : tiles_(tiles), solutions_(0) {
  347.     for (int row=0; row < BOARD_HEIGHT; ++row) {
  348.         for (int col=0; col < BOARD_WIDTH; ++col) {
  349.             data_[row][col] = 0;
  350.         }
  351.     }
  352.     for (vector<Tile>::iterator i = tiles_.begin(); i != tiles_.end(); ++i) {
  353.         unused_tiles_.push_back(&(*i));
  354.     }
  355. }
  356.  
  357. void Board::dump() const {
  358. //    std::cout << "****** BOARD-DUMP ******" << endl;
  359.     for (int row=0; row < BOARD_HEIGHT; ++row) {
  360.         for (int col=0; col < BOARD_WIDTH; ++col) {
  361.             char val = data_[row][col];
  362.             if (!val)
  363.                 val = '.';
  364.             std::cout << val;
  365.         }
  366.         std::cout << endl;
  367.     }
  368.     std::cout << endl;
  369. }
  370.  
  371. void Board::fill(int queue_position) {
  372.     Position seed;
  373.     seed = queue_[queue_position];
  374.     while (at(seed.x, seed.y)) {
  375.         // skip check of vector size, free seed must be available
  376.         ++queue_position;
  377.         seed = queue_[queue_position];
  378.     }
  379.     // we have a free seed now
  380.     size_t number_of_tiles = unused_tiles_.size();
  381.     if (number_of_tiles == sizeof(INIT_TILES)/sizeof(INIT_TILES[0]))
  382.         number_of_tiles -= 3;
  383.     // rotate over all tiles
  384.     for (int n=0; n < number_of_tiles; ++n) {
  385.         Tile &tile = *unused_tiles_.front();
  386.         unused_tiles_.pop_front();
  387.         // iterate over all orientations
  388.         const vector<OrientedTile> &orientations = tile.orientations();
  389.         for (vector<OrientedTile>::const_iterator i = orientations.begin(); i !=orientations.end(); ++i) {
  390.             const OrientedTile &ot = *i;
  391.             // iterate over all body blocks of the oriented tile
  392.             for (vector<Position>::const_iterator j = ot.body().begin(); j != ot.body().end(); ++j) {
  393.                 const Position &offset = *j;
  394.                 int x = seed.x-offset.x+1;
  395.                 int y = seed.y-offset.y+1;
  396.                 // try to fill the seed with the given offset
  397.                 new_seeds_.clear();
  398.                 if (ot.insert(*this, x, y)) {
  399.                     bool valid_tile(true);
  400.                     // corner seeds have additional conditions to skip equivalent solutions
  401.                     if (at(width()-1, 0) && (at(width()-1, 0) < at(0, 0) // upper right must be larger than upper left
  402.                                              || (at(0, height()-1) && at(width()-1, 0) > at(0, height()-1)))) // and smaller than lower left
  403.                         valid_tile = false;
  404.                     else if (at(0, height()-1) && at(0, height()-1) < at(0, 0)) // lower left must be larger than upper left
  405.                         valid_tile = false;
  406.                     else if (at(width()-1, height()-1) && at(width()-1, height()-1) < at(0, 0)) // lower right must be larger than upper left
  407.                         valid_tile = false;
  408.                     if (valid_tile) {
  409.                         if (unused_tiles_.empty()) {
  410.                             // solution found!
  411.                             cout << "SOLUTION " << ++solutions_ << endl;
  412.                             dump();
  413.                         } else {
  414.                             size_t number_of_new_seeds = new_seeds_.size();
  415.                             if (number_of_new_seeds)
  416.                                 queue_.insert(queue_.end(), new_seeds_.begin(), new_seeds_.end());
  417.                             fill(queue_position+1);
  418.                             // remove new_seeds from queue
  419.                             if (number_of_new_seeds)
  420.                                 queue_.erase(queue_.end()-number_of_new_seeds, queue_.end());
  421.                         }
  422.                     }
  423.                     ot.remove(*this, x, y);
  424.                     //dump();
  425.                 }
  426.             }
  427.         }
  428.         unused_tiles_.push_back(&tile);
  429.     }
  430. }
  431.  
  432. int main (int argc, const char * argv[]) {
  433.     vector<Tile> tile_list;
  434.     for (int i=0; i<sizeof(INIT_TILES)/sizeof(INIT_TILES[0]); ++i) {
  435.         const Tile t(INIT_TILES[i], 'A'+i );
  436.         tile_list.push_back(t);
  437. //      t.dump();
  438.     }
  439.     Board board(tile_list);
  440.     board.fill();
  441. }
  442.  
  443.  
RAW Paste Data