1.

import java.util.Scanner;

/**
 * FWP, Ausgewählte Probleme aus dem ACM Programming Contest, WS10/11 
 * 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 Fabian Liebl
 * @version 1.0, 10/06/2010
 * 
 * Method : Backtracking algorithm
 * Status : Accepted
 * Runtime: 0.224
 */

public class Main {

	private static int[] queen = new int[8];
	private static int[][] field = new int[8][8];
	private static int max;
	
	private static boolean checkVertical(int pos, int line) {
		if (line <= -1) return true;
		if (queen[line] == pos) return false;
		else return checkVertical(pos, line - 1);
	}
	private static boolean checkDiag1(int pos, int line) {
		if (pos < 0) return true;
		if (line <= -1) return true;
		if (queen[line] == pos) return false;
		else return checkDiag1(pos - 1, line - 1);
	}
	private static boolean checkDiag2(int pos, int line) {
		if (pos > 7) return true;
		if (line <= -1) return true;
		if (queen[line] == pos) return false;
		else return checkDiag2(pos + 1, line - 1);
	}
	
	private static void doLine(int line) {
		for (int i = 0; i < 8; i++) {
			queen[line] = i;
			if (!checkVertical(i, line-1)) continue;
			if (!checkDiag1(i-1, line-1)) continue;
			if (!checkDiag2(i+1, line-1)) continue;
			// Found valid position
			if (line == 7) {
				// Found possible solution
				calcSolution();
			} else {
				doLine(line + 1);
			}
		}
	}
	
	private static void calcSolution() {
		int x = 0;
		for (int i = 0; i < 8; i++) {
			x+=field[queen[i]][i];
		}
		if (x>max) max = x;
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int testCases = sc.nextInt();
		
		for (int tc = 0; tc < testCases; tc++) {
			max = 0;
			
			// Parse chess field
			for (int y = 0; y < 8; y++) {
				for (int x = 0; x < 8; x++) {
					field[x][y] = sc.nextInt();
				}
			}
			
			// Start recursive backtracking algorithm
			doLine(0);
			
			System.out.printf("%5d\n", max);
		}	
	}

}


2. 
/**
 * FWP, Ausgewählte Probleme aus dem ACM Programming Contest, SS10 
 * 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 Evgeni Pavlidis 
 * @version 1.0, 06/02/2010
 * 
 * Method : Backtracking
 * Status : Accepted
 * Runtime: 0.428
 */

/* Sorting of the squares wasn't needed in the end,
because we have to check all possibilities */

import java.io.*;
import java.util.*;

class Main {

    static class Square implements Comparable<Square> {
        int x,y, value;
        Square(int aX, int aY, int aValue) 
        {
            x = aX;
            y = aY;
            value = aValue;
        }

        public int compareTo(Square other)
        {
            if(this.value > other.value)
                return -1;
            if(this.value < other.value)
                return 1;
            return 0;
        }

        public String toString()
        {
            return "("+x+","+y+")["+value+"] ";
        }
    }

    private static List<Square> chessboard = new ArrayList<Square>();
    private static boolean[] row;
    private static boolean[] column;
    private static boolean[] d1;
    private static boolean[] d2;

    private static int max;

    private static Stack<Square> stack = new Stack<Square>();

    static void backtrack(int step, int index,int sum)
    {
        if(step == 8)
        {
            if(sum > max)
                max = sum;
            return;
        }            

        Square s;

        for(int i = index; i < 64; i++)
        {   
            s = chessboard.get(i);
            if(!row[s.y] && !column[s.x] && !d1[s.x-s.y+9] && !d2[s.x+s.y])
            {
                row[s.y] = true;
                column[s.x] = true;
                d1[s.x-s.y+9] = true;
                d2[s.x+s.y] = true;
                
                //System.out.println(step + " +++++++ " + s);
                //stack.push(s);

                backtrack(step+1, i+1, sum+s.value);
                    
                //stack.pop();
                //System.out.println(step + " ------- " + s);

                d1[s.x-s.y+9] = false;
                d2[s.x+s.y] = false;
                row[s.y] = false;
                column[s.x] = false;
            }
        }
    }

    public static void main(String...args)
    {
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();

        for(int t = 0; t < k; t++)
        {
            chessboard.clear();
            row = new boolean[9];
            column = new boolean[9];
            d1 = new boolean[20];
            d2 = new boolean[20];
            max = 0;

            for(int y = 1; y <= 8; y++)
                for(int x = 1; x <= 8; x++)
                    chessboard.add(new Square(x,y,sc.nextInt()));

            Collections.sort(chessboard);
            backtrack(0,0,0);

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