[UVa]167:The Sultan's Successors

典型8皇后問題，利用backtracking即可得解。

[C](0.016)

	#include<stdio.h>
	int queen[8][8] = {0};
	int answer = 0;
	void backtracking( int sum, int x, int y[], int slash1[], int slash2[] )
	{
	if( x == 8 )
	{
	if( sum > answer )
	answer = sum;
	return;
	}
	int i;
	for( i = 0 ; i < 8 ; i++ )
	{
	if( !y[i] && !slash1[(i+x)%15] && !slash2[(i-x+15)%15] )
	{
	y[i] = 1;
	slash1[(i+x)%15] = 1;
	slash2[(i-x+15)%15] = 1;
	backtracking( sum+queen[x][i], x+1, y, slash1, slash2 );
	y[i] = 0;
	slash1[(i+x)%15] = 0;
	slash2[(i-x+15)%15] = 0;
	}
	}
	}
	int main()
	{
	int k;
	while( scanf( "%d", &k ) != EOF )
	{
	int n;
	for( n = 1 ; n <= k ; n++ )
	{
	int y[8] = {0}, slash1[15] = {0}, slash2[15] = {0};
	int i, j;
	for( j = 0 ; j < 8 ; j++ )
	for( i = 0 ; i < 8 ; i++ )
	scanf( "%d", &queen[j][i] );
	answer = 0;
	backtracking( 0, 0, y, slash1, slash2 );
	printf( "%5d\n", answer );
	}
	}
	return 0;
	}

view raw UVa167.c hosted with ❤ by GitHub