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();
}
}
}