UVa 167 - The Sultan's Successors

// UVa 167 - The Sultan's Successors

#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;

bool free_row[8];
int pos_col[8];
int sol, sum;
int chess[8][8];

void rec(int col) {
	if (col == 8) {
		if (sum > sol)
			sol = sum;
		return;
	}
	for (int row = 0; row < 8; row++)
		if (free_row[row]) {
			int a_up = row;
			int a_down = row;
			bool invalid = false;
			for (int i = col - 1; i >= 0; i--) {
				a_up++;
				a_down--;
				if ((a_down >= 0 && pos_col[i] == a_down)
						|| (a_up < 8 && pos_col[i] == a_up)) {
					invalid = true;
					break;
				}
			}
			if (!invalid) {
				pos_col[col] = row;
				free_row[row] = false;
				sum += chess[row][col];
				rec(col + 1);
				pos_col[col] = -1;
				free_row[row] = true;
				sum -= chess[row][col];
			}
		}
}

int main() {
	int t;
	for (cin >> t; t; t--) {
		for (int i = 0; i < 8; i++)
			for (int j = 0; j < 8; j++)
				cin >> chess[i][j];

		memset(pos_col, 255, sizeof(pos_col));
		memset(free_row, true, sizeof(free_row));
		sol = 0;
		sum = 0;
		rec(0);
		printf("%5d\n", sol);
	}
	return 0;
}