#include <iostream.h>
#include <assert.h>
#define ROWS 8
#define COLS 8
#define DEBUGMODE false

int best=20;
int sols=0;
// Specify the F Pentomino.
int wi=3;
int he=3;
int orient=8;
int wid[8] = {3,3,3,3,3,3,3,3};
int hei[8] = {3,3,3,3,3,3,3,3};
int pnt[8][3][3] = 
 { {{0,1,1},{1,1,0},{0,1,0}},
   {{1,1,0},{0,1,1},{0,1,0}},
   {{0,1,0},{0,1,1},{1,1,0}},
   {{0,1,0},{1,1,0},{0,1,1}},
   {{0,1,0},{1,1,1},{0,0,1}},
   {{0,1,0},{1,1,1},{1,0,0}},
   {{0,0,1},{1,1,1},{0,1,0}},
   {{1,0,0},{1,1,1},{0,1,0}} };

int grid[ROWS*COLS];
int check[(ROWS+2)*COLS];

void print(int pieces) {
  int r,c;
  cout << pieces << " ominoes placed.\n";
  for (r=0;r<ROWS;r++) {
    for (c=0;c<COLS;c++) {
      cout << " " << grid[r*COLS+c];
    }
    cout << "\n";
  }
  cout << "\n";
}

bool checkslide(int n) {
  bool lblock=false;
  bool rblock=false;
  bool ublock=false;
  bool dblock=false;
  int loc;
  for (loc=0;loc<ROWS*COLS;loc++) if (grid[loc]==n) {
    if (!lblock) {
      if (loc%COLS==0) lblock=true;
      else if ((grid[loc-1] != 0) && (grid[loc-1] != n)) lblock=true;
    }
    if (!rblock) {
      if (loc%COLS==COLS-1) rblock=true;
      else if ((grid[loc+1] != 0) && (grid[loc+1] != n)) rblock=true;
    }
    if (!ublock) {
      if (loc/COLS==0) ublock=true;
      else if ((grid[loc-COLS] != 0) && (grid[loc-COLS] != n)) ublock=true;
    }
    if (!dblock) {
      if (loc/COLS==ROWS-1) dblock=true;
      else if ((grid[loc+COLS] != 0) && (grid[loc+COLS] != n)) dblock=true;
    }
  }
  return (lblock && rblock && ublock && dblock);
}

bool place(int n,int curloc,int ori) {
  int mypnt[he][wi];
  int mywid,myhei;
  int r,c,currow,curcol;
  bool success = true;
  mywid = wid[ori];
  myhei = hei[ori];
  mypnt = pnt[ori];
  currow = curloc/COLS;
  curcol = curloc%COLS;
  // see if we can place
  for (r=0;r<myhei;r++) for (c=0;c<mywid;c++) if (mypnt[r][c]==1) {
    if (currow+r >= ROWS) success = false; 
    else if (curcol+c >= COLS) success = false; 
    else if (grid[(currow+r)*COLS+curcol+c] != 0) success = false; 
  }
  if (success) {
    for (r=0;r<myhei;r++) for (c=0;c<mywid;c++) if (mypnt[r][c]==1) {
      grid[(currow+r)*COLS+curcol+c] = n;
    }
    int checkpoint = (currow+myhei)*COLS+curcol+mywid;
    while (check[checkpoint]!=0) checkpoint++;
    check[checkpoint]=n;
  }
  return(success);
}

int unplace(int n,int curloc,int ori) {
  for (int a=0;a<ROWS*COLS;a++) 
    if (grid[a]==n) grid[a]=0;
  for (int a=0;a<(ROWS+2)*COLS;a++) 
    if (check[a]==n) check[a]=0;
}

void recurse(int n, int curloc) {
  if (n-1>best) return;
  // put the nth omino at location curloc.  Or not.
  if (curloc == (ROWS+2)*COLS) {
    if ((n-1<=best) && (n>1)) {
      if (n-1<best) sols=0;
      sols++;
      best = n-1;
      print(best);
    }
  } else if (curloc >= ROWS*COLS) {
    if ((check[curloc] == 0) || (checkslide(check[curloc]))) {
      recurse(n,curloc+1);
    }
  } else {
    if (DEBUGMODE) { cout << "Checking " << check[curloc] << " at "
        << curloc << "...\n"; }
    if ((check[curloc] == 0) || (checkslide(check[curloc]))) {
      for (int ori=0;ori<orient;ori++) {
        if (place(n,curloc,ori)) {
          if (DEBUGMODE) { cout << "Placing " << n << "...\n"; }
          recurse(n+1,curloc+1);
          unplace(n,curloc,ori);
        }
      }
      recurse(n,curloc+1);
    }
  }
}

void main(void) {
  int curloc=0;
  int r;
  for (r=0;r<ROWS*COLS;r++) grid[r]=0;
  for (r=0;r<ROWS*COLS;r++) check[r]=0;
  recurse(1,curloc);
  cout << "Done.  " << sols << " solutions found.\n";
}