1. 


/**
* Angewandte Mathematik, SS09, IFB 2C
* ACM Problem #750 (8 Queens Chess Problem)
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=9&problem=691&mosmsg=Submission+received+with+ID+7211793
*
* @author Christian Posselt
* @author Jonathan Schubert
* @version 1.0, 06/25/2009
*
* Status : Accepted
* Runtime: 0.116
*/


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main
{
public static StringBuilder builder = new StringBuilder();

public static void main(String[] args) throws NumberFormatException, IOException
{
//set up needed variables
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String line;
int amount;

amount = Integer.parseInt(read(reader));

for(int i=1;i<=amount;i++)
{
//print header
builder.append("SOLN COLUMN\n");
builder.append(" # 1 2 3 4 5 6 7 8\n\n");

line = read(reader);
//calculate 8 Queens for this input
new EightQueens(Integer.parseInt(line.substring(0,1)),Integer.parseInt(line.substring(2)));
builder.append("\n");
}

System.out.print(builder.substring(0, builder.length()-1).toString());
}

/**
* read
*
* reads from an input. Skips empty lines
*
* @param reader: BufferedReader to read from
* @return non-empty String
* @throws IOException: IOException from BufferedReader
*/
public static String read(BufferedReader reader) throws IOException
{
String answer = reader.readLine();
while(answer.isEmpty())
answer = reader.readLine();

return answer;
}

/**
* EightQueens
*
* tries to find the solutions for this problem
*
* @author Christian Posselt
* @author Jonathan Schubert
*
*/
static class EightQueens
{
/**
* amount of queens to be placed
*/
private final int amountQueens = 8;

/**
* holds one complete solution
*/
private final int[] solution = new int[8];

/**
* column and row to be included in solution
*/
private final int must_row, must_col;

/**
* counter for solution
*/
private int counter;

public EightQueens(int must_col, int must_row)
{
this.must_row = must_row;
this.must_col = must_col;
counter = 1;
put(0);
}

public void put(int k)
{
//if eight Queens are set and solution includes the wanted Queen -> print
if (k==amountQueens && solution[must_row-1] == must_col)
print();

//find a position for every queen
for (int p=1; p<=amountQueens; p++)
if (!hasConflict(k,p))
{
solution[k] = p;
put(k+1);
}
}


public boolean hasConflict(int k, int pos)
{
for (int i=0; i<k; i++)
{
//if a queen at this position can not be set
if ((solution[i]==pos) || (solution[i]-i==pos-k) || (solution[i]+i==pos+k))
return true;
}
return false;
}


//write the solution according to the output definiton
public void print()
{
if(counter<10)
builder.append(" " + counter++ +" ");
else
builder.append(counter++ +" ");

for (int i=0; i<8; i++)
builder.append(" " + solution[i]);
builder.append("\n");
}
}

}