#include <fstream.h>
#include <iostream.h>
#include <assert.h>

#define MAXPIECES 25
#define MAXORIENT 12
#define MAXPSIZE 10
#define MAXGSIZE 20
#define DEBUGMODE false

int grid[MAXGSIZE][MAXGSIZE];
int pieces[MAXPIECES][MAXORIENT][MAXPSIZE][MAXPSIZE];
int hei[MAXPIECES][MAXORIENT];
int wid[MAXPIECES][MAXORIENT];
int originrow[MAXPIECES][MAXORIENT];
int origincol[MAXPIECES][MAXORIENT];
int orinum[MAXPIECES];

int srow[MAXPIECES];
int scol[MAXPIECES];
int sori[MAXPIECES];
bool splaced[MAXPIECES];
int numpieces;
long numsols=0;

void printgrid(void) {
  int maxrow=0; int maxcol=0;
  cout << " Grid:\n";
    for (int lcv=0;lcv<MAXGSIZE;lcv++) {
      for (int lcv2=0;lcv2<MAXGSIZE;lcv2++) {
        cout << grid[lcv][lcv2]%64/7 << " " 
             << grid[lcv][lcv2]/64/7 << " ";
    }
    cout << "\n";
  }
}

void printsol(void) {
  cout << "Solution!\n";
if (DEBUGMODE) printgrid();
  for (int piece=0;piece<numpieces;piece++) if (splaced[piece]) {
    cout << "Piece " << piece << ":";
    cout << "  row " << srow[piece] << ",";
    cout << "  col " << scol[piece] << ",";
    cout << "  ori " << sori[piece] << "\n";

    for (int lcv=0;lcv<hei[piece][sori[piece]];lcv++) {
      for (int lcv2=0;lcv2<wid[piece][sori[piece]];lcv2++) {
        cout << pieces[piece][sori[piece]][lcv][lcv2]%64/7 << " " 
             << pieces[piece][sori[piece]][lcv][lcv2]/64/7 << " ";
      }
      cout << "\n" ;
    }
  }
  cout << flush;
}

bool tryplace(int piece,int ori,int currow, int curcol) {
  bool success;
  int orgrow = currow-originrow[piece][ori];
  int orgcol = curcol-origincol[piece][ori];

  success = true;
  // see if we can place the piece at that location.
if (DEBUGMODE) cout << "trying to place piece " << piece
  << " ori " << ori << " at (" << currow << "," << curcol << ")\n";
  if ((orgrow>=0)&&(orgcol>=0)) {
    // will be within bounds
    for(int row=0;row<hei[piece][ori];row++) 
      for(int col=0;col<wid[piece][ori];col++) 
        if (pieces[piece][ori][row][col]
          &(~grid[orgrow+row][orgcol+col])) {
          success = false; goto OUTT; } 
    OUTT: if (success) {
      // we can place!
      for(int row=0;row<hei[piece][ori];row++) 
        for(int col=0;col<wid[piece][ori];col++) 
          grid[orgrow+row][orgcol+col]
            -= pieces[piece][ori][row][col];
      srow[piece] = orgrow;
      scol[piece] = orgcol;
      sori[piece] = ori;
      splaced[piece] = true;
    }
  } else {
    success = false;
  }
if (DEBUGMODE && success) cout << "return success\n";
if (DEBUGMODE && !success) cout << "return no success\n";
  return(success);
}

void unplace(int piece,int ori,int currow, int curcol) {
  int orgrow = currow-originrow[piece][ori];
  int orgcol = curcol-origincol[piece][ori];
  for(int row=0;row<hei[piece][ori];row++) 
    for(int col=0;col<wid[piece][ori];col++) {
      grid[orgrow+row][orgcol+col]
        += pieces[piece][ori][row][col];
  }
  splaced[piece] = false;
//if (DEBUGMODE) cout << "UNPlaced " << piece << "\n";
//if (DEBUGMODE) printsol();
}

void recurse( int placed, int currow, int curcol, int startpiece ) {
//if (DEBUGMODE) cout << "currow: " << currow
//   << " curcol: " << curcol << " curstat: " << grid[currow][curcol]%64/7
//   << " " << grid[currow][curcol]/64/7 << "\n";
//if (DEBUGMODE && placed>=3) printsol();
  if (placed == numpieces) {
    // found solution
    printsol();
    numsols++;
  } else if (grid[currow][curcol] == 0) {
    // cell filled, next piece
if (DEBUGMODE) cout << "(" << currow << "," << curcol << ") filled\n";
    if (curcol+1==MAXGSIZE) {
      if (currow!=MAXGSIZE) 
        recurse(placed,currow+1,0,0);
    } else 
      recurse(placed,currow,curcol+1,0);
  } else {
    // try placing a piece
    for (int piece=startpiece;piece<numpieces;piece++) if (!splaced[piece]) 
                 for (int ori=0;ori<orinum[piece];ori++) {
      if (tryplace(piece,ori,currow,curcol)) {
if (DEBUGMODE) cout << "Placed piece " << piece
    << " with ori " << ori
    << " at (" << currow << "," << curcol << ")\n";
if (DEBUGMODE) cout << placed << " pieces ";
if (DEBUGMODE) printgrid();
        recurse(placed+1,currow,curcol,piece+1);
if (DEBUGMODE) cout << "Pop\n";
        unplace(piece,ori,currow,curcol);
      }
    }
  }
}

void clearall (void) {
  for (int lcv1=0;lcv1<MAXGSIZE;lcv1++)
  for (int lcv2=0;lcv2<MAXGSIZE;lcv2++) {
    grid[lcv1][lcv2] = 0;
  }
  for (int lcv1=0;lcv1<MAXPIECES;lcv1++) {
    srow[lcv1]=0;scol[lcv1]=0;sori[lcv1]=0;
//if (DEBUGMODE) cout << "UNPlaced " << lcv1 << "\n";
    splaced[lcv1]=false;orinum[lcv1]=0;
    for (int lcv2=0;lcv2<MAXORIENT;lcv2++) {
      hei[lcv1][lcv2]=0;
      wid[lcv1][lcv2]=0;
      originrow[lcv1][lcv2]=MAXPSIZE;
      origincol[lcv1][lcv2]=MAXPSIZE;
      for (int lcv3=0;lcv3<MAXPSIZE;lcv3++)
      for (int lcv4=0;lcv4<MAXPSIZE;lcv4++) {
        pieces[lcv1][lcv2][lcv3][lcv4]=0;
      }
    }
  }
}

void eatpieces (ifstream & in) {
  int insanitym = 0;
  int insanityz = 0; int t1,t2;
  int insanityx = 0; int insanityq = 0; 
  int pie=0;int ori=0;int row=0;int col=0;

  in >> ws;
  while (in.peek() != 'M') {
    insanitym++;
    in >> ws;
    while (in.peek() != 'Z') {
      insanityz++;
      in >> ws;
      while (in.peek() != 'Q') {
        insanityq++; 
        in >> ws;
        while (in.peek() != 'X') {
          insanityx++; 
          in >> t1 >> t2;
          pieces[pie][ori][row][col] = 7*(t1+64*t2);
          if ((originrow[pie][ori] > row) 
            &&(origincol[pie][ori] > col)
            &&(pieces[pie][ori][row][col] != 0)) {
            originrow[pie][ori] = row;
            origincol[pie][ori] = col;
          }
          col++; 
          in >> ws; 
          assert(insanityx<65000);
        }
        if (col > wid[pie][ori]) wid[pie][ori] = col; 
        insanityx=0; 
        in.get(); // 'X'
        in >> ws; 
        row++; 
        col=0; 
        assert(insanityq<65000);
      }
      if (row > hei[pie][ori]) hei[pie][ori] = row;
      insanityq=0;
      in.get(); // 'Q'
      in >> ws;
      ori++;
      row=0;
      assert(insanityz<65000);
    }
    orinum[pie]=ori;
    insanityz=0;
    in.get(); // 'Z'
    in >> ws;
    pie++;
    ori=0;
    assert(insanitym<65000);
  }
  numpieces = pie;
}

void eatgrid (ifstream & in) {
  int insanityx = 0; int insanityq = 0; int row=0;int col=0;
  int t1,t2;
  in >> ws;
  while (in.peek() != 'Q') {
    insanityq++; in >> ws;
    col=0;
    while (in.peek() != 'X') {
      insanityx++; 
      in >> t1 >> t2;
      grid[row][col] = 7*(t1+64*t2);
      col++; in >> ws; assert(insanityx<65000);
    }
    insanityx=0; in.get(); in >> ws; row++; col=0; assert(insanityq<65000);
  }
  in.get();
}

void main (int argc, char * argv []) {
  ifstream gd;

  clearall();
  // First, the grid
  cout << "Reading grid " << argv[1] << "...\n";
  gd.open(argv[1],ios::in);
  eatgrid(gd); 
  gd.close();
  // Next, the pieces
  cout << "Reading pieces " << argv[2] << "...\n";
  gd.open(argv[2],ios::in);
  eatpieces(gd); 
  gd.close();
  
  cout << "Solving ... \n";
  recurse(0,0,0,0);
  cout << "There are " << numsols << " total solutions.\n";
}