ansiwen

octogram

Nov 28th, 2011
5,403
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

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×