#include <iostream>
#include <vector>

struct piece{
    int w, h;
    char* data;

    //this way I can quickly create a piece form a string:
    piece(int w, int h, const char* dat=0) : w(w), h(h){
        data = new char[w*h];
        if(dat) memcpy(data, dat, w*h);
        else memset(data, ' ', w*h);
    }

    //these two copy all the data so that it can be safely manipulated and deleted
    piece(const piece& p) : w(p.w), h(p.h){
        data = new char[w*h];
        memcpy(data, p.data, w*h);
    }
    piece& operator = (const piece& p){
        w = p.w; h = p.h;
        data = new char[w*h];
        memcpy(data, p.data, w*h);
        return *this;
    }
    ~piece(){
        delete[] data;
    }

    //some output
    void print(){
        for(int y = 0; y < h; y++){
            for(int x = 0; x < w; x++)
                std::cout.put( data[x+y*w] );
            std::cout.put('\n');
        }
    }

    //rotate a piece by 90 degrees:
    void turn(){
        char* ndat = new char[w*h];

        for(int x = 0; x < w; x++)
            for(int y = 0; y < h; y++)
                ndat[(h-1-y)+x*h] = data[x+y*w];

        delete[] data;
        data = ndat;
        std::swap(w, h);
    }

    //this function tries to put one piece onto another
    //if there is some overlapping, function returns 0, neither piece is changed
    //else function returns 1, 'this' is changed.
    bool blit(int px, int py, piece& p){
        if(px < 0 || py < 0 || px+p.w > w || py+p.h > h) return 0;

        for(int x = 0; x < p.w; x++)
            for(int y = 0; y < p.h; y++)
                if(p.data[x+y*p.w] != ' ' &&  data[px+x+(py+y)*w] != ' ') return 0;

        for(int x = 0; x < p.w; x++)
            for(int y = 0; y < p.h; y++)
                if(p.data[x+y*p.w] != ' ') data[px+x+(py+y)*w] = p.data[x+y*p.w];

        return 1;
    }
};

//this is where the magic happens
bool TryAll(std::vector<piece> list, piece res){
    piece result = res;
    for(int a = 0; a < 4; a++){//function tries every coordinate and angle of the top piece in the list
        for(int x = 0; x < result.w; x++){
            for(int y = 0; y < result.h; y++){
                if( result.blit( x, y, list.back() ) ){//if piece fits in the jigsaw..
                    result.print();
                    std::cout.put('\n');
                    bool b = true;
                    if(list.size() > 1)//if this wasn't the last piece,
                        //recursively call TryAll with a shorter list and the new variant of jigsaw
                        b = TryAll( std::vector<piece>(list.begin(), list.end()-1), result);
                    if(b) return true;//else the jigsaw is solved
                    else result = res;//if something fails, and the piece you tried is not in the right place,
                            //you have to reset the jigsaw to its former state.
                }
            }
        }
        list.back().turn();
    }
    return 0;//this point is only reached when no piece matches into the puzzle.
}

int main(){
    std::vector<piece> list;//here I construct the pieces. normally you would use a file for that.
    list.push_back( piece(3, 1, "###") );
    list.push_back( piece(3, 3, "OOOO  OOO") );
    list.push_back( piece(2, 3, "XXX XX") );

    piece result(5, 3);//the jigsaw itself is also a piece.
    //however this piece never holds any value. If you want to change that you could make TryAll return piece*

    TryAll(list, result);

    std::cin.get();
    return 0;
}