题目链接：Uva 167
思路分析：八皇后问题，采用回溯法解决问题。
代码如下：
#include <iostream>
#include <string.h>
using namespace std; const int MAX_N = ;
int A[MAX_N];
int M[MAX_N][MAX_N];
int num, Max = ; int is_safe( int row, int col )
{
for ( int i = ; i < row; ++i )
{
if ( A[i] == col )
return false;
if ( A[i] + i == row + col )
return false;
if ( i - A[i] == row - col )
return false;
} return true;
} void dfs( int row )
{
if ( row == )
{
for ( int i = ; i < ; ++i )
num += M[i][A[i]];
if ( num > Max )
Max = num; num = ;
return;
}
else
{
for ( int i = ; i < ; ++i )
{
if ( is_safe( row , i ) )
{
A[row] = i;
dfs( row+ );
} }
}
} int main( )
{
int n; cin >> n;
while ( n-- )
{
num = Max = ;
memset( M, , sizeof( M ) );
memset( A, , sizeof( A ) ); for ( int i = ; i <= ; ++i )
for ( int j = ; j <= ; ++j )
cin >> M[i][j]; dfs( );
printf( "%5d\n", Max );
} return ;
}