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