octogram

//
// fast octogram puzzle solver
//
// copyright 2011 Sven Anderson <sven@anderson.de>
//
//    This program is free software: you can redistribute it and/or modify
//    it under the terms of the GNU General Public License as published by
//    the Free Software Foundation, either version 3 of the License, or
//    (at your option) any later version.
//
//    This program is distributed in the hope that it will be useful,
//    but WITHOUT ANY WARRANTY; without even the implied warranty of
//    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
//    GNU General Public License for more details.
//
//    You should have received a copy of the GNU General Public License
//    along with this program.  If not, see <http://www.gnu.org/licenses/>.
//

#include <stdlib.h>

#include <iostream>
#include <list>
#include <vector>

using namespace std;

// max size of tiles
const int MAX_WIDTH = 5;
const int MAX_HEIGHT = 5;

// size of board
const int BOARD_WIDTH = 8;
const int BOARD_HEIGHT = 8;

// list of available tiles
const char INIT_TILES[][MAX_HEIGHT][MAX_WIDTH] = {
    {
        { 1, 1, 1, 1, 1}
    },
    {
        { 1, 1, 1, 1},
        { 1 }
    },
    {
        { 1, 1, 1},
        { 1 },
        { 1 }
    },
    {
        { 1, 1, 1, 1 },
        { 0, 1 }
    },
    {
        { 1, 1 },
        { 0, 1, 1 },
        { 0, 1 }
    },
    {
        { 0, 1 },
        { 1, 1, 1 },
        { 0, 1 }
    },
    {
        { 1, 1, 1 },
        { 1, 1 }
    },
    {
        { 1 },
        { 1, 1, 1 },
        { 1 }
    },
    {
        { 0, 1, 1 },
        { 1, 1 },
        { 1 }
    },
    {
        { 1, 1 },
        { 1 },
        { 1, 1 }
    },
    {
        { 0, 1, 1, 1 },
        { 1, 1 }
    },
    {
        { 0, 1, 1 },
        { 0, 1 },
        { 1, 1 }
    },
    {
        { 1, 1 },
        { 1, 1 }
    }
};

struct Position {
    int x;
    int y;
    Position() : x(0), y(0) {}
    Position(int xx, int yy) : x(xx), y(yy) {}
    bool operator==(const Position &rhs) const { return (x == rhs.x && y == rhs.y); }
    bool operator!=(const Position &rhs) const { return (!(*this == rhs)); }
    bool operator<(const Position &rhs) const {
        return ( y < rhs.y || (y == rhs.y && x < rhs.x ));
    }
};

class Board; // forward declaration

//
// OrientedTile has a distinct orientation
//
class OrientedTile {
    int width_;
    int height_;
    char sign_;                 // character used to mark board fields
    vector<Position> body_;     // list of body coordinates
    vector<Position> border_;   // list of border coordinates
public:
    OrientedTile();
    OrientedTile(const char data[MAX_HEIGHT][MAX_WIDTH], const char sign);
    bool operator==(const OrientedTile &rhs) const;
    const vector<Position> &body() const { return body_; }
    const vector<Position> &border() const { return border_; }
    char sign() const { return sign_; }
    OrientedTile rotated() const;
    OrientedTile mirrored() const;
    bool insert(Board &board, int x, int y) const;
    void remove(Board &board, int x, int y) const;
    void dump() const;
};

//
// Tile represents a tile regardless of it's orientation
//
class Tile {
    vector<OrientedTile> orientations_; // list of all unique orientations
public:
    Tile(const char array[MAX_HEIGHT][MAX_WIDTH], char sign);
    const vector<OrientedTile> &orientations() const { return orientations_; }
    bool matches(OrientedTile oriented_tile);
    void dump() const;
};


//
// The board which has to be filled with tiles
// it holds a list of tiles not on the board yet and a queue
// of board fields that need to be filled next.
//
class Board {
    char data_[BOARD_HEIGHT][BOARD_WIDTH];  // the board
    vector<Tile> tiles_;                    // list of all available tiles
    list<Tile *> unused_tiles_;             // list of tiles not on the board yet
    vector<Position> queue_;                // queue of fields to fill next
    vector<Position> new_seeds_;            // temporary list for new seed fields
    int solutions_;                         // solutions counter
public:
    Board(const vector<Tile> &tiles);
    int width() const { return BOARD_WIDTH; }
    int height() const { return BOARD_HEIGHT; }
    vector<Position> &new_seeds() { return new_seeds_; }
    char &at(int x, int y) { return data_[y][x]; }
    const char at(int x, int y) const { return data_[y][x]; }
    void fill(int queue_position);
    void fill() { queue_.push_back(Position(0, 0)); fill(0); }
    void dump() const;
};


OrientedTile::OrientedTile() : width_(0), height_(0), sign_(0) {};

OrientedTile::OrientedTile(const char data[MAX_HEIGHT][MAX_WIDTH], const char sign) : width_(0), height_(0), sign_(sign) {
    for (int row=0; row < MAX_HEIGHT+2; ++row) {
        for (int col=0; col < MAX_WIDTH+2; ++col) {
            if (row > 0 && row < MAX_HEIGHT+1
                && col > 0 && col < MAX_WIDTH+1
                && data[row-1][col-1]) {
                height_ = row+2;
                if (width_ < col+2)
                    width_ = col+2;
                body_.push_back(Position(col, row));
            } else
            if ((row > 0 && row < MAX_HEIGHT+1 && col > 1 && data[row-1][col-2])
                || (row > 0 && row < MAX_HEIGHT+1 && col < MAX_WIDTH && data[row-1][col])
                || (col > 0 && col < MAX_WIDTH+1 && row > 1 && data[row-2][col-1])
                || (col > 0 && col < MAX_WIDTH+1 && row < MAX_HEIGHT && data[row][col-1]))
                    border_.push_back(Position(col, row));
        }
    }
}

bool OrientedTile::operator==(const OrientedTile &rhs) const {
    if (width_ != rhs.width_ || height_ != rhs.height_)
        return false;
    if (body_.size() != rhs.body_.size())
        return false;
    vector<Position>::const_iterator i = body_.begin();
    vector<Position>::const_iterator j = rhs.body_.begin();
    for (; i != body_.end() ; ++i, ++j) {
        if (*i != *j)
            return false;
    }
    return true;
}

OrientedTile OrientedTile::rotated() const {
    OrientedTile rotated;
    rotated.width_ = height_;
    rotated.height_ = width_;
    rotated.sign_ = sign_;
    list<Position> tmp_list;
    for (vector<Position>::const_iterator i = body_.begin(); i != body_.end(); ++i) {
        tmp_list.push_back(Position(height_-1-i->y, i->x));
    }
    tmp_list.sort();
    rotated.body_.insert(rotated.body_.end(), tmp_list.begin(), tmp_list.end());
    tmp_list.clear();
    for (vector<Position>::const_iterator i = border_.begin(); i != border_.end(); ++i) {
        tmp_list.push_back(Position(height_-1-i->y, i->x));
    }
    tmp_list.sort();
    rotated.border_.insert(rotated.border_.end(), tmp_list.begin(), tmp_list.end());
    return rotated;
}

OrientedTile OrientedTile::mirrored() const {
    OrientedTile mirrored;
    mirrored.width_ = height_;
    mirrored.height_ = width_;
    mirrored.sign_ = sign_;
    list<Position> tmp_list;
    for (vector<Position>::const_iterator i = body_.begin(); i != body_.end(); ++i) {
        tmp_list.push_back(Position(i->y, i->x));
    }
    tmp_list.sort();
    mirrored.body_.insert(mirrored.body_.end(), tmp_list.begin(), tmp_list.end());
    tmp_list.clear();
    for (vector<Position>::const_iterator i = border_.begin(); i != border_.end(); ++i) {
        tmp_list.push_back(Position(i->y, i->x));
    }
    tmp_list.sort();
    mirrored.border_.insert(mirrored.border_.end(), tmp_list.begin(), tmp_list.end());
    return mirrored;
}

bool OrientedTile::insert(Board &board, int x, int y) const {
    if (x < 0 || y < 0 || x+width_-2 > board.width() || y+height_-2 > board.height())
        return false;
    --x;
    --y;
    for (vector<Position>::const_iterator i = body_.begin(); i != body_.end(); ++i) {
        if (board.at(i->x+x, i->y+y))
            return false;
    }
    for (vector<Position>::const_iterator i = body_.begin(); i != body_.end(); ++i) {
        board.at(i->x+x, i->y+y) = sign_;
    }
    for (vector<Position>::const_iterator i = border_.begin(); i != border_.end(); ++i) {
        int xx = i->x+x;
        int yy = i->y+y;
        if (xx >= 0 && xx < board.width() && yy >= 0 && yy < board.height())
            board.new_seeds().push_back(Position(xx, yy));
    }
    return true;
}

void OrientedTile::remove(Board &board, int x, int y) const {
    --x;
    --y;
    for (vector<Position>::const_iterator i = body_.begin(); i != body_.end(); ++i) {
        board.at(i->x+x, i->y+y) = 0;
    }
}

void OrientedTile::dump() const {
    char data[MAX_HEIGHT+2][MAX_WIDTH+2] = {};
    std::cout << "--- ORIENTED-TILE-DUMP ---" << endl;
    for (vector<Position>::const_iterator i = body_.begin(); i != body_.end(); ++i) {
        data[i->y][i->x] = '#';
    }
    for (vector<Position>::const_iterator i = border_.begin(); i != border_.end(); ++i) {
        if (data[i->y][i->x] == '#')
            std::cout << "Warning: collision of border and body!" << endl;
        data[i->y][i->x] = '+';
    }
    for (int row=0; row < height_; ++row) {
        for (int col=0; col < width_; ++col) {
            char val = data[row][col];
            char sign = '.';
            if (val)
                sign = val;
            std::cout << sign;
        }
        std::cout << endl;
    }
    std::cout << "size: " << width_ << "x" << height_ << endl;
}


Tile::Tile(const char array[MAX_HEIGHT][MAX_WIDTH], char sign) {
    OrientedTile tile(array, sign);
    orientations_.push_back(tile);
    tile = tile.rotated();
    if (!matches(tile))
        orientations_.push_back(tile);
    tile = tile.rotated();
    if (!matches(tile))
        orientations_.push_back(tile);
    tile = tile.rotated();
    if (!matches(tile))
        orientations_.push_back(tile);
    tile = tile.mirrored();
    if (!matches(tile))
        orientations_.push_back(tile);
    tile = tile.rotated();
    if (!matches(tile))
        orientations_.push_back(tile);
    tile = tile.rotated();
    if (!matches(tile))
        orientations_.push_back(tile);
    tile = tile.rotated();
    if (!matches(tile))
        orientations_.push_back(tile);
}

bool Tile::matches(OrientedTile oriented_tile) {
    for (vector<OrientedTile>::const_iterator i = orientations_.begin(); i != orientations_.end(); ++i) {
        if (*i == oriented_tile)
            return true;
    }
    return false;
}

void Tile::dump() const {
    std::cout << "****** TILE-DUMP ******" << endl;
    std::cout << "Orientations: " << orientations_.size() << endl;
    for (vector<OrientedTile>::const_iterator i = orientations_.begin(); i != orientations_.end(); ++i) {
        i->dump();
    }
    std::cout << endl;
}

Board::Board(const vector<Tile> &tiles) : tiles_(tiles), solutions_(0) {
    for (int row=0; row < BOARD_HEIGHT; ++row) {
        for (int col=0; col < BOARD_WIDTH; ++col) {
            data_[row][col] = 0;
        }
    }
    for (vector<Tile>::iterator i = tiles_.begin(); i != tiles_.end(); ++i) {
        unused_tiles_.push_back(&(*i));
    }
}

void Board::dump() const {
//    std::cout << "****** BOARD-DUMP ******" << endl;
    for (int row=0; row < BOARD_HEIGHT; ++row) {
        for (int col=0; col < BOARD_WIDTH; ++col) {
            char val = data_[row][col];
            if (!val)
                val = '.';
            std::cout << val;
        }
        std::cout << endl;
    }
    std::cout << endl;
}

void Board::fill(int queue_position) {
    Position seed;
    seed = queue_[queue_position];
    while (at(seed.x, seed.y)) {
        // skip check of vector size, free seed must be available
        ++queue_position;
        seed = queue_[queue_position];
    }
    // we have a free seed now
    size_t number_of_tiles = unused_tiles_.size();
    if (number_of_tiles == sizeof(INIT_TILES)/sizeof(INIT_TILES[0]))
        number_of_tiles -= 3;
    // rotate over all tiles
    for (int n=0; n < number_of_tiles; ++n) {
        Tile &tile = *unused_tiles_.front();
        unused_tiles_.pop_front();
        // iterate over all orientations
        const vector<OrientedTile> &orientations = tile.orientations();
        for (vector<OrientedTile>::const_iterator i = orientations.begin(); i !=orientations.end(); ++i) {
            const OrientedTile &ot = *i;
            // iterate over all body blocks of the oriented tile
            for (vector<Position>::const_iterator j = ot.body().begin(); j != ot.body().end(); ++j) {
                const Position &offset = *j;
                int x = seed.x-offset.x+1;
                int y = seed.y-offset.y+1;
                // try to fill the seed with the given offset
                new_seeds_.clear();
                if (ot.insert(*this, x, y)) {
                    bool valid_tile(true);
                    // corner seeds have additional conditions to skip equivalent solutions
                    if (at(width()-1, 0) && (at(width()-1, 0) < at(0, 0) // upper right must be larger than upper left
                                             || (at(0, height()-1) && at(width()-1, 0) > at(0, height()-1)))) // and smaller than lower left
                        valid_tile = false;
                    else if (at(0, height()-1) && at(0, height()-1) < at(0, 0)) // lower left must be larger than upper left
                        valid_tile = false;
                    else if (at(width()-1, height()-1) && at(width()-1, height()-1) < at(0, 0)) // lower right must be larger than upper left
                        valid_tile = false;
                    if (valid_tile) {
                        if (unused_tiles_.empty()) {
                            // solution found!
                            cout << "SOLUTION " << ++solutions_ << endl;
                            dump();
                        } else {
                            size_t number_of_new_seeds = new_seeds_.size();
                            if (number_of_new_seeds)
                                queue_.insert(queue_.end(), new_seeds_.begin(), new_seeds_.end());
                            fill(queue_position+1);
                            // remove new_seeds from queue
                            if (number_of_new_seeds)
                                queue_.erase(queue_.end()-number_of_new_seeds, queue_.end());
                        }
                    }
                    ot.remove(*this, x, y);
                    //dump();
                }
            }
        }
        unused_tiles_.push_back(&tile);
    }
}

int main (int argc, const char * argv[]) {
    vector<Tile> tile_list;
    for (int i=0; i<sizeof(INIT_TILES)/sizeof(INIT_TILES[0]); ++i) {
        const Tile t(INIT_TILES[i], 'A'+i );
        tile_list.push_back(t);
//      t.dump();
    }
    Board board(tile_list);
    board.fill();
}