1. 
/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, SS2010
* Problem: 750 - 8 Queens Chess Problem
* Link: http://uva.onlinejudge.org/external/7/750.html
*
* @author Barny Porcio
* @version 1.0, 05/09/2010
*
* Status : Accepted
* Runtime: 0.212
*/

import java.util.Scanner;


public class QueensChessProblem750 {

static boolean[][] field ;
static int queensrow;
static int queenscol;
static boolean[] rows;
static boolean[] cols ;
static int counter;

static boolean add(int row,int col){
//rows und cols checken
if (rows[row] == true || cols[col])
return false;
int a = 7;
//diagonale checken
while (a >=0){
int b = col-(row-a);
int c = col+(row-a);
if (c <=7 &&c >=0)
if (field[a][c])
return false;
if (b>=0 && b<=7)
if (field[a][b])
return false;
--a;
}
//setzen
rows[row] = true;
cols[col] = true;
field[row][col] = true;
return true;
}

private static void remove(int row,int col){
//loeschen
rows[row] = false;
cols[col] = false;
field[row][col] = false;
}

//array wird benutzr um loesung zu speichern
static int[] ergebnis = new int[8];

static void backt(int col){
if (col ==queenscol){
ergebnis[col] = queensrow;
backt(col+1);
}
for (int i = 0; i<8;++i){
if (add(i,col)){
ergebnis[col] = i;
if (col == 7 || (col == 6 && queenscol == 7)){
ergebnis[queenscol] = queensrow;
++counter;
if (counter <=9)
System.out.print(" ");
System.out.print(counter+" ");
for(int t : ergebnis)
System.out.print(" "+(t+1));
System.out.println();
remove(i,col);
return;
}
backt(col+1);
remove(i, col);
}
}
}

public static void main(String[] args){
Scanner br = new Scanner(System.in);
int la = br.nextInt();
for(int i = la; i > 0; --i){
field = new boolean[8][8];
rows = new boolean[8];
cols = new boolean[8];
counter = 0;
queensrow =br.nextInt()-1;
queenscol = br.nextInt()-1;
add(queensrow,queenscol);
System.out.println("SOLN COLUMN");
System.out.println(" # 1 2 3 4 5 6 7 8");
System.out.println();
backt(0);
remove(queensrow, queenscol);
if (i != 1)
System.out.println();
}
}
}