import java.io.*;

public class Ndamas
{
  public static void main( String [] in) 
       throws IOException, PilhaOverflow, PilhaUnderflow, CloneNotSupportedException
  {
    boolean deu_certo;
    boolean existe = true;
    
    PosicaodasDamas P = new PosicaodasDamas();  //declara variaveis
    Posicao atual = new Posicao();
    System.out.println("Digite n");
    
    int n = Leitura.leInt();                   // le o n da entrada padrao
    
    atual.linha  = 1;
    atual.coluna = 1;
    
    while( atual.linha <= n){
      
      deu_certo = false;
      while( ! deu_certo && atual.coluna <= n) // tenta colocar dentro do tabuleiro
	if ( P.PodeColocar(atual) )
	  deu_certo = true;
        else atual.coluna++; // se nao pode colocar, tenta na coluna seguinte
      
      if( deu_certo) {       // achou posicao livre na linha
	P.Empilha((Posicao) atual.clone()); // empilha copia do atual
        /* passa a tentar na proxima linha */
	atual.linha++;
	atual.coluna = 1;  //  e na coluna 1 
      }
      else // Backtrack (nao pode colocar nesta linha)
	{  
          try  // tenta volta `a ultima decisao e modifica'-la
	  {
	    
	    atual = P.TopoPilha();  // pega a ultima decisao empilhada
	    P.Desempilha();
	    atual.coluna++;         // comeca a tentar a partir desta coluna
	  }
	  catch (PilhaUnderflow e)  // se nao tem decisao a tomar, nao existe
	                            // solucao 
	  {
	    System.out.println("Nao existe solucao");
            existe = false;
	    break;
	  }
	
	}
    }
    if (existe){
      System.out.println("posicao das damas");
      while(! P.PilhaVazia()){
	System.out.println("linha "+P.TopoPilha().linha +
                           " coluna "+P.TopoPilha().coluna);
	P.Desempilha();
	
	  }
    }
  }
}