1. 

/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, WS09
* Problem: 167 The Sultan's Successors
* Link:
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=103
*
* @author Kratzer Kevin
* @version 1.0, 10/28/2009
*
* Method : Ad-Hoc
* Status : Accepted
* Runtime: 0.516
*/

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;

public class Main167 {

protected final BufferedReader input;
public Main167() {
input = new BufferedReader(new InputStreamReader(System.in));

}

void process() throws IOException {
String lineIn = input.readLine();
int amount = Integer.parseInt(lineIn);
for (int i = 0; i < amount;i++) {
final int[][] board = new int[8][8];
for(int line = 0; line < 8; line++) {
lineIn = input.readLine().trim();
String[] splitLine = lineIn.split(" +");
for(int col = 0; col < 8; col++) {
board[line][col] = Integer.parseInt(splitLine[col]);
}
}
Result best = new Result(null,-1);
for(int newCol = 0; newCol < 8; newCol++) {
best = best.compareTo(backtrack(new ArrayList<int[]>(8),board,0,newCol));
}
System.out.printf("%5d\n",best.score);

}
System.out.flush();

}

private Result backtrack(ArrayList<int[]> queens, int[][] board, int line, int col) {
if(queens.size() == 8) {
int score = 0;
for(int[] queen: queens) {
score += board[queen[0]][queen[1]];
}
return new Result(queens,score);
}
boolean valid = true;
for(int[] queen: queens) {
if(queen[0] == line || queen[1] == col ||
(Math.abs(queen[0]-line) == Math.abs(queen[1]-col))) {
valid = false;
}
}
if(valid) {
ArrayList<int[]> newQueens = new ArrayList<int[]>(queens);
newQueens.add(new int[] {line,col});
Result best = new Result(null,-1);
for(int newCol = 0; newCol < 8; newCol++) {
best = best.compareTo(backtrack(newQueens,board,line+1,newCol));
}
return best;
} else {
return null;
}
}

private class Result {
private final ArrayList<int[]> queens;
private final int score;
public Result(ArrayList<int[]> queens, int score) {
this.queens = queens;
this.score = score;
}
public ArrayList<int[]> getQueens() {
return queens;
}
public int getScore() {
return score;
}

public Result compareTo(Result other) {
if(other == null || score >= other.score) {
return this;
}
return other;
}
}

public static void main(String... args) throws Exception {
new Main167().process();
}
}


2.

/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, WS09
* Problem: 167 - The Sultan's Successors
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=3&problem=103&mosmsg=Submission+received+with+ID+7516378
*
* @author Christoph Hausmann
* @version 0.1, 10/28/2009
*
* Method : Recursive Backtracking
* Status : Accepted
* Runtime: 0.212
*/


import java.io.IOException;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;


public class TheSultansSuccessors_167 {
public static void main(String... args) throws NumberFormatException, IOException {
final Scanner scanner = new Scanner(System.in);

int numberOfBoards = scanner.nextInt();

for(;numberOfBoards > 0; numberOfBoards--) {
final int[][] curBoard = new int[8][8];

for(int i = 0; i < 8; i++) {
for(int j = 0; j < 8; j++) {
curBoard[i][j] = scanner.nextInt();
}
}

final Set<int[]> validConfigs = new HashSet<int[]>();

final int[] config = new int[8];

Arrays.fill(config, -1);

queensRec(validConfigs, config,0);

int bestSolution = -1;

for(final int[] curConf : validConfigs) {
int count = 0;

for(int i = 0; i < 8; i++) {
count += curBoard[i][curConf[i]];
}

if(count > bestSolution) {
bestSolution = count;
}
}

System.out.printf("%5d\n", bestSolution);
}
}

/**
* Recursive algorithm for finding valid configs.
*
* @param validConfigs a set of valid configs that were found.
* @param config the current config
* @param k the row to modify
*/
private static void queensRec(Set<int[]> validConfigs, int[] config, int k) {

if(!isValidConfig(config)) {
// no valid config, skip
return;
}

if(k == 8) {
// valid config and nothing more to do
validConfigs.add(config);
return;
}

for(int i = 0; i < 8; i++) {
final int[] newConfig = Arrays.copyOf(config, 8);
newConfig[k] = i;
queensRec(validConfigs, newConfig, k+1);
}
}

/**
* Checks whether the given config is valid.
*
* @param config the config to test
* @return true if valid, false otherwise
*/
private static boolean isValidConfig(int[] config) {
for(int i = 0; i < 8; i++) {
for(int j = 0; j < 8; j++) {
if(i != j && config[i] != -1 && config[j] != -1) {
if(config[i] == config[j])
return false;
if(Math.abs(i-j) == Math.abs(config[i]-config[j]))
return false;
}
}
}

return true;
}
}