1.

/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, SS11
* Problem: 750 - 8 Queens Chess Problem
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=9&page=show_problem&problem=691
*
* @author Christian Posselt
* @author Christian Mitterreiter
* @version 1.0, 13.04.2011
*
* Status: Accepted
* Time: 0.196
*/

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

public class Main
{
//will have saved all 92 solutions of the 8 queen's problem
public static ArrayList<ArrayList<Integer>> completeSolution = new ArrayList<ArrayList<Integer>>();

public static void main(String[] args) throws IOException
{

BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String solution = "";

//get amount of cases
int numbers = Integer.parseInt(reader.readLine());

//solve the 8 Queen Problem by setting a queen at 1,1 and start from there
putQueen(new int[8],0);

for(int i=0;i<numbers;i++)
{
String mustQueen = reader.readLine();
mustQueen = mustQueen.replaceAll(" ", "");

//ignore empty rows between test cases
if(mustQueen.isEmpty())
{
i--;
continue;
}

//get the coordinates of the Queen which must be placed
int mustColumn = (int)(mustQueen.charAt(0)-'0');
int mustRow = (int)(mustQueen.charAt(1)-'0');

int amountSolutions = 0;

solution = solution + "SOLN COLUMN\n";
solution = solution + " # 1 2 3 4 5 6 7 8\n\n";

for(int j=0;j<completeSolution.size();j++)
{
ArrayList<Integer> part = completeSolution.get(j);

//if the solution set contains the queen which must be placed, then print
if(part.get(new Integer(mustRow-1)).equals(new Integer(mustColumn)))
{
if(amountSolutions<9)
solution = solution + " " + (++amountSolutions) + " ";
else
solution = solution + (++amountSolutions) + " ";
for(int n:part)
solution = solution + " " + n;
solution = solution + "\n";
}
}

solution = solution + "\n";
}

//delete one line break
solution = solution.substring(0, solution.length()-1);
System.out.print(solution);

}

/**
* isConsistent
*
* tests wheter the so far put queens are set correct
*
* @param q: array of the so far found solution
* @param n: numbers of queens that have been placed
* @return true: solution is correct so far
* false: solution is wrong
*/
public static boolean isConsistent(int[] q, int n) {
for (int i = 0; i < n; i++) {
if (q[i] == q[n]) return false; // same column
if ((q[i] - q[n]) == (n - i)) return false; // same major diagonal
if ((q[n] - q[i]) == (n - i)) return false; // same minor diagonal
}
return true;
}

/**
* Find the solutions for the 8 queen's problem with
* backtracking
*
* @param q: array representing the size of the set (e.g. 8x8)
* @param n: queen to be placed
*/
public static void putQueen(int[] q, int n) {
//number of queens that have to be placed
int N = q.length;
//if 8 queens were placed, save the solution
if (n == N) saveSolution(q);
//try to place a queen according to the rule
else {
for (int i = 0; i < N; i++) {
q[n] = i;
if (isConsistent(q, n)) putQueen(q, n+1);
}
}
}

/**
* puts the solution into the completeSolution set
*
* @param q: solution
*/
public static void saveSolution(int[] q) {
int N = q.length;
ArrayList<Integer> solution = new ArrayList<Integer>();
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (q[i] == j) solution.add(j+1);
}
}
completeSolution.add(solution);
}

}



----------------------

1.

/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, WS10/11
* Problem: 750 8 Queens Chess Problem
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&page=show_problem&problem=691
*
* @author Patrick Bédat
* @version 1.0, 10/25/2010
*
* Method : Backtracking
* Status : Accepted
* Runtime: 0.340
*/
package eightqueens;

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

public class Main
{

private static class LexicographicalComparator implements Comparator<Integer[]>
{

public int compare(Integer[] o1, Integer[] o2)
{
for (int i = 0; i < 8; i++)
{
if (o1[i] < o2[i])
return -1;
if (o1[i] > o2[i])
return 1;
}

return 0;
}
}

private static HashSet<Integer[]> solutions = new HashSet<Integer[]>();

public static void main(String[] args) throws IOException
{
BufferedReader reader = new BufferedReader( new InputStreamReader(System.in));

int numberOfTestCases = Integer.parseInt(new StringTokenizer(reader.readLine()).nextToken());

StringBuilder out = new StringBuilder();

for (int tc = 0; tc < numberOfTestCases; tc++)
{
int x = -1;
int y = -1;

if (reader.ready())
{
String line = reader.readLine();

//empty lines are just being skipped...
if(line.trim().isEmpty())
{
tc--;
continue;
}

StringTokenizer st = new StringTokenizer(line);
x = st.hasMoreTokens() ? Integer.parseInt(st.nextToken()) : 0;
y = st.hasMoreTokens() ? Integer.parseInt(st.nextToken()) : 0;

x -= 1;
y -= 1;
}

Integer[] queens = new Integer[8];

//if the (x,y) coordinate is invalid, the latest solution will be printed
if (x >= 0 && y >= 0 && x < 8 && y < 8)
{
solutions.clear();
queens[y] = x;
findQueens(0, queens, x, y);
}

int solNumber = 1;

List<Integer[]> sols = new ArrayList<Integer[]>(solutions);
Collections.sort(sols, new LexicographicalComparator());

out.append("SOLN COLUMN");
out.append(String.format("%n"));

out.append(" # 1 2 3 4 5 6 7 8");
out.append(String.format("%n%n"));

for (Integer[] sol : sols)
{
out.append(String.format("%2d ", solNumber++));

for (int i = 0; i < 8; i++)
out.append(String.format("%d%s", sol[i] + 1, i == 7 ? "" : " "));

out.append(String.format("%n"));
}

if (tc < numberOfTestCases - 1)
out.append(String.format("%n"));
}
System.out.print(out);
}

/**
* Given the first queen set on a checker board this method adds all possible arrangements
* of 7 further queens on a checkerboard.
* @param y current line
* @param queens current solution vector
* @param firstX x coordinate of the first queen
* @param firstY y coordinate of the first queen
*/
private static void findQueens(int y, Integer[] queens, int firstX, int firstY)
{
//skip the line if the first queen is in there
if (y == firstY)
y++;

if (y == 8)
{
solutions.add(queens.clone());
return;
}

for (int x = 0; x < 8; x++)
{
boolean valid = true;

//check if (x,y) is valid to the coords of the first queen
valid = valid && x != firstX && Math.abs(firstX - x) != Math.abs(firstY - y);

//check each row if the current x is valid
for (int row = 0; row < y && valid; row++)
{
//vertical check
valid &= queens[row] != x;
//diagonal check
valid &= Math.abs(queens[row] - x) != Math.abs(row - y);
}

if (valid)
{
queens[y] = x;
findQueens(++y, queens, firstX, firstY);
y--;
}
}
}
}


2.
/**
* 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();
}
}
}