Tantrix

#include <iostream>
#include <list>
#include <vector>
#include <string>
#include <sstream>

enum colorState {r, g, b, y};

enum rot {I,II,III,IIII,IIIII,IIIIII};

const int dirs[6][2] = { {0,1},
                         {1,1},
                         {1,0},
                         {0,-1},
                         {-1,-1},
                         {-1,0} };

int totalBoards = 0;
int perm = 0;

class coords {
    public:int x;
    public:int y;

    public:coords() = default;

    friend bool operator==(const coords& c1, const coords& c2) {
        return c1.x == c2.x && c1.y == c2.y;
    }

    public:coords(int nx, int ny) {
        x = nx;
        y = ny;
    }
};

class tile {
    public:colorState states[6];
    public:int identifier;
    public:coords coordinates;

    public:tile() = default;

    friend bool operator==(const tile& t1, const tile& t2) {
        return t1.identifier == t2.identifier;
    }

    public:tile(colorState s[6], int i, coords c) {
        *states = *s;
        identifier = i;
        coordinates = c;
    }

    public:void rotateC() {
        colorState tmpA,tmpB;
        tmpA = states[1];
        states[1] = states[0];
        tmpB = states[2];
        states[2] = tmpA;
        tmpA = states[3];
        states[3] = tmpB;
        tmpB = states[4];
        states[4] = tmpA;
        tmpA = states[5];
        states[5] = tmpB;
        states[0] = tmpA;
    }

    public:void rotateAC() {
        colorState tmpA, tmpB;
        tmpA = states[0];
        states[0] = states[1];
        tmpB = states[5];
        states[5] = tmpA;
        tmpA = states[4];
        states[4] = tmpB;
        tmpB = states[3];
        states[3] = tmpA;
        tmpA = states[2];
        states[2] = tmpB;
        states[1] = tmpA;
    }

    public:void alterX(int altX) {
        coordinates.x += altX;
    }

    public:void alterY(int altY) {
        coordinates.y += altY;
    }

    public:void setX(int altX) {
        coordinates.x = altX;
    }

    public:void setY(int altY) {
        coordinates.y = altY;
    }
};

class tileRot {
    public: tile t;
    public: rot r;

    public:tileRot(tile nt, rot nr) {
        t = nt;
        r = nr;
    }
};

bool compareTiles(const tile& a, const tile& b) {
    if (a.coordinates.x < b.coordinates.x) return true;
    if (b.coordinates.x < a.coordinates.x) return false;

    if (a.coordinates.y < b.coordinates.y) return true;
    if (b.coordinates.y < a.coordinates.y) return false;
}

class board {
    public:std::list<tile> boardtiles;

    public:board(){
        boardtiles = std::list<tile>();
    }

    public:void addToBoard(tile toadd) {
        boardtiles.push_back(toadd);
    }

    public:void removeFromBoard(tile toadd) {
        boardtiles.remove(toadd);
    }

    public:std::list<tile> getBoard() {
        return boardtiles;
    }

    public:std::list<coords> getAdjecentCoords() {
        std::list<coords> result = std::list<coords>();
        for (tile t : boardtiles) {
            for (int i = 0; i < 6; i++) {
                int x = t.coordinates.x + dirs[i][0];
                int y = t.coordinates.y + dirs[i][1];
                if (std::find(result.begin(), result.end(), coords{ x,y }) != result.end())
                    break;
                else for (tile tTMP : boardtiles)
                    if (tTMP.coordinates.x == x && tTMP.coordinates.y == y)
                        result.push_back(coords{ x,y });
            }
        }
        return result;
    }

    public:std::list<coords> getValidCoords(std::list<coords> adjCoords) {
        std::list<coords> result = std::list<coords>();
        for (coords c : adjCoords) {
            int tileCount = 0;
            for (int i = 0; i < 6; i++) {
                int x = c.x + dirs[i][0];
                int y = c.y + dirs[i][1];
                for (tile t : boardtiles) {
                    if (t.coordinates.x == x, t.coordinates.y == y)
                        tileCount++;
                }
            }
            if (tileCount > 1)
                result.push_back(c);
        }
        return result;
    }


    public:void printBoard() {
        std::list<tile> tmp = boardtiles;
        tmp.sort(compareTiles);
        for (tile t : tmp)
            printf("%s",generateTile(t).c_str());
    }

    private:std::string generateTile(tile t) {
        std::ostringstream stream;
        stream << "  == ++\n";
        stream << " =%c    %c+\n", enumToChar(t.states[4]), enumToChar(t.states[5]);
        stream << "| %c %2d %c |\n", enumToChar(t.states[3]),t.identifier, enumToChar(t.states[0]);
        stream << " =%c    %c+\n", enumToChar(t.states[2]), enumToChar(t.states[1]);
        stream << "  == ++\n";
        return stream.str();
    }

    private:char enumToChar(colorState state) {
        if (state == r)
            return 'r';
        if (state == g)
            return 'g';
        if (state == b)
            return 'b';
        if (state == y)
            return 'y';
    }
};

void calcboard(std::vector<tile> permVec, board b);
std::list<std::list<tile>> findPermutations(std::list<tile> original);
std::list<tileRot> getValidSpacesForTile(tile t, bool secondToAdd, board b);
bool checkLineContinuous(colorState state, board b);
tile* findTile(int x, int y, board b);
bool checkValidPosition(tile pos, board b);

int main()
{
    tile Tc[14] = { tile(new colorState[6]{r,g,g,b,b,r},1 ,{INT16_MIN,INT16_MIN}),
                    tile(new colorState[6]{g,r,r,b,b,g},2 ,{INT16_MIN,INT16_MIN}),
                    tile(new colorState[6]{r,b,b,r,g,g},3 ,{INT16_MIN,INT16_MIN}),
                    tile(new colorState[6]{g,r,r,g,b,b},4 ,{INT16_MIN,INT16_MIN}),
                    tile(new colorState[6]{b,r,r,b,g,g},5 ,{INT16_MIN,INT16_MIN}),
                    tile(new colorState[6]{r,g,g,b,b,r},6 ,{INT16_MIN,INT16_MIN}),
                    tile(new colorState[6]{g,r,b,g,b,r},7 ,{INT16_MIN,INT16_MIN}),
                    tile(new colorState[6]{b,r,g,b,g,r},8 ,{INT16_MIN,INT16_MIN}),
                    tile(new colorState[6]{g,r,r,b,g,b},9 ,{INT16_MIN,INT16_MIN}),
                    tile(new colorState[6]{r,g,g,b,r,b},10,{INT16_MIN,INT16_MIN}),
                    tile(new colorState[6]{r,b,b,g,r,g},11,{INT16_MIN,INT16_MIN}),
                    tile(new colorState[6]{b,r,r,g,b,g},12,{INT16_MIN,INT16_MIN}),
                    tile(new colorState[6]{b,g,g,r,b,r},13,{INT16_MIN,INT16_MIN}),
                    tile(new colorState[6]{g,b,b,r,g,r},14,{INT16_MIN,INT16_MIN}),
                  };

    printf("starting...\n");

    for (int iFirst = 0; iFirst < 14; iFirst++) {
        board b = board();

        std::list<tile> toAdd = std::list<tile>();


        Tc[iFirst].coordinates.x = 0;
        Tc[iFirst].coordinates.y = 0;

        b.addToBoard(Tc[iFirst]);
        for (int iNext = 0; iNext < 14; iNext++) {
            if (iNext != iFirst)
                toAdd.push_back(Tc[iNext]);
        }
        //we have to add 13 more tiles.
        for (std::list<tile> perm : findPermutations(toAdd)) {
            printf("Permutations found");
            std::vector<tile> permVec(perm.begin(), perm.end());
            calcboard(permVec, b);
        }
    }
    printf("finished \n");
}

//provide a board with tiles layed on them and premVec an list of tiles to still place on the board.
void calcboard(std::vector<tile> permVec, board b) {
    bool secondToAdd;
    std::list<tileRot> valid = std::list<tileRot>();
    secondToAdd = true;
    //iterate through all tiles in the list
    for (int iTile = 0; iTile < 13; iTile++) {
        //obtain the list of valid tiles and rotation for the iTileth tile of the list
        valid = getValidSpacesForTile(permVec.at(iTile), secondToAdd, b);
        //we now have a list of all valid positions for all rotations for the tile to insert next given the previous board.
        for (tileRot tileValid : valid) {
            //add the tile to the board so we can recursively see how the next tile fits the board.
            b.addToBoard(tileValid.t);
            //check if there are still tiles to place
            if (permVec.size() > 0) {
                //create a copy of the list
                std::vector<tile> cpy = permVec;
                //remove the placed element from the copy
                cpy.erase(cpy.begin() + iTile);
                //calculate all board options for the remaining tiles.
                calcboard(cpy, b);
            } else {
                totalBoards++;
                //check if the board contains a single line for state "r" (currently potentially broken)
                if (checkLineContinuous(r, b))
                {
                    //we've found a line that works, print the board.
                    printf("Board %d is valid!\n", totalBoards);
                    b.printBoard();
                }
                else
                {
                    //we've found an invalid board.
                    printf("Board %d is invalid!\n", totalBoards);
                }
            }
            //remove the tile from the board so it can be added somewhere else.
            b.removeFromBoard(tileValid.t);
        }
        secondToAdd = false;
    }
}

bool checkLineContinuous(colorState state, board b) {
    int outs = 0;
    for (tile t : b.boardtiles) {
        //enumerate through each position
        for (int i = 0; i < 6; i++) {
            if (t.states[i] = state) {
                // find the neighbour in the list
                tile* neighbour = findTile(t.coordinates.x + dirs[i][0],
                                           t.coordinates.y + dirs[i][1],
                                           b);
                if (neighbour == nullptr) {
                    outs++;
                }
            }
        }
    }
    return outs == 2;
}

std::list<tileRot> getValidSpacesForTile(tile t,bool secondToAdd, board b) {
    std::list<tileRot> valid = std::list<tileRot>();
    for (int iRot = 0; iRot < 6; iRot++) {
        std::list<coords> toCheck = b.getAdjecentCoords();
        if (!secondToAdd)
            toCheck = b.getValidCoords(toCheck);
        for (coords c : toCheck) {
            t.setX(c.x);
            t.setX(c.y);
            if (checkValidPosition(t, b)) {
                valid.push_back(tileRot(t, (rot)iRot));
            }
        }
        t.rotateC();
    }
    return valid;
}

std::list<std::list<tile>> findPermutations(std::list<tile> original)
{
    perm++;
    if (perm % 1000000000 == 0)
    {
        printf("perm reached %1.000.000.000\n");
    }
    std::list<std::list<tile>> result = std::list<std::list<tile>>();
    if (original.size() == 2)
    {
        // these are permutations of array of size 2
        result.push_back(std::list<tile>(original));
        result.push_back(std::list<tile>{original.end(),original.begin()});
        return result;
    }
    else
    {
        // going through array
        for(tile t : original)
        {
            // creating subarray = array
            std::list<tile> rlist = std::list<tile>(original);
            // removing element
            rlist.remove(t);
            for(std::list<tile> retlist : findPermutations(rlist))
            {
                retlist.push_front(t); // inserting the element at pos 0
                result.push_back(retlist);
            }
        }
    }
    return result;
}

bool checkValidPosition(tile pos, board b) {
    //the directions from pos to each neighbour

    //enumerate through each position
    for (int i = 0; i < 6; i++) {
        // find the neighbour in the list
        tile* neighbour = findTile(pos.coordinates.x + dirs[i][0],
                                   pos.coordinates.y + dirs[i][1],
                                   b);
        //check if neighbour exists
        if(neighbour != nullptr)
            //check if the 2 states next to each other don't match
            if (neighbour->states[(i + 3) % 6] != pos.states[i])
                //if there is no match, the position is invalid
                return false;
    }
    //all existing neoghbours have matching states
    return true;
}

tile* findTile(int x, int y, board b) {
    for (tile b : b.boardtiles)
        if (x == b.coordinates.x && y == b.coordinates.y)
            return &b;
    return nullptr;
}