#include <stdio.h>
#include <stdlib.h>
#include <cassert>

using namespace std;



const int maxSize = 100;
const int notSeized = maxSize+1;

int seizedAtLevel[maxSize][maxSize];

void initSeized(){
  for( int col = 0 ; col < maxSize ; col += 1 ){
    for( int row = 0 ; row < maxSize ; row += 1 ){
      seizedAtLevel[col][row] = notSeized;
    }
  }
}

bool seized(const int col, const int row, const int currentLevel ){
  return seizedAtLevel[col][row] <= currentLevel;
}

void setSeizedValue(const int col, const int row, const int currentLevel, const int value ){

  if( col < 0 || row < 0 || col >= maxSize || row >= maxSize ){
    // out of board
    return;
  }
  
  if( seizedAtLevel[col][row] < currentLevel ){
    // already seized by previous queen
    return;
  }
  seizedAtLevel[col][row] = value;
}


void changeSeizedCells(const int row, const int level, const int size, const int value ){
  for( int d = 1 ; d < size-level ; d += 1 ){
    // same row
    setSeizedValue(level+d,row,level,value);

    // upwards diagonal
    setSeizedValue(level+d,row-d,level,value);

    // downwards diagonal
    setSeizedValue(level+d,row+d,level,value);
  }
}


void dumpSeized(const int size){
  for( int row = 0 ; row < size ; row += 1 ){
    for( int col = 0 ; col < size ; col += 1 ){
      printf( "\t%d", seizedAtLevel[col][row] );
    }
    printf( "\n");
  }
}

bool stillPossible( const int level, const int size ){
  for( int col = level+1 ; col < size ; col += 1 ){
    int freeCells = 0;
    for( int row = 0; row < size ; row += 1 ){
      if( !seized(col,row,level) ){
        freeCells += 1;
      }
    }
    if( freeCells < col-level-1){
      // there are no enough free cells in the column
      return false;
    }
  }
  return true;
}

bool placeQueenAtLevel( const int level, const int size, int queensRows[] ){
  assert(size < maxSize );

  // printf( "\n INTENTANDO NIVEL:%d\n", level);
  // dumpSeized(size);
  
  if( level == size ){
    return true;
  }
  
  for( int row = 0 ; row < size ; row += 1 ){

    if( seized(level,row,level) ){
      continue;
    }

    // place queen in col=level, row=row
    queensRows[level] = row;
    changeSeizedCells(row,level, size,level);

    // try next queen
    if( stillPossible(level,size) ){
      if( placeQueenAtLevel(level+1,size,queensRows) ){
        return true;
      }
    }

    // remove queen from col=level, row=row
    changeSeizedCells(row,level, size,notSeized);
  }

  return false;
}

void dumpQueens(int queensRows[], int size){
  for( int row = 0 ; row < size ; row += 1 ){
    for( int col = 0 ; col < size ; col += 1 ){
      const char cell = (col+row)%2==0 ? '.' : ' ';
      printf( " %c", queensRows[col]==row ? 'Q' : cell );
    }
    printf( "\n");
  }

}
  
int main( int argc, char *argv[] ){

  system("date");

  int currentQueen = 0;
  const int size = 31;

  int queensRows[size];

  initSeized();
  bool result = placeQueenAtLevel(0,size,queensRows);

  printf( "Conseguido:%s\n", result ? "Si" : "No");
  if( result ){
    dumpQueens(queensRows, size);
  }

  system("date");
  
}