9.7例題:八皇后問題

問題の説明:
チェスができる人はよく知っています.皇后は横、縦、斜線で歩数を問わず他の駒を食べることができます.どのように8個の皇后を碁盤の上に置くか(8*8個の四角い格子がある)、それらを誰にも食べられないようにするか!これが有名な八皇后問題である.ある要求を満たす8皇后の配置方法について、1つの皇后列aとそれに対応する、すなわちa=b 1 b 2...b 8を定義し、そのうちbiは対応する配置法の中でi行目の皇后が置かれている列数である.8皇后問題は全部で92組の解があることが分かった(すなわち92個の異なる皇后列).b番目の列の出力を要求する数bが与えられる.列の比較は、皇后列xが皇后列yの前に置かれ、xが整数とみなされる場合のみyよりも小さい.入力データの1行目は試験データのグループ数nであり、その後n行に従って入力される.各グループの試験データは1行を占め、正の整数b(1<=b<=92)の出力要求n行を含み、各行出力は入力に対応します.出力は正の整数であり、bに対応する皇后列入力サンプル2 1 92出力サンプル15863724 84136275であるべきである.
コード例1:

/*
*
*Declaration:The author of <<Accelerated C++>> has wrote in the end of that book: As you look for reading materimal,
 keep in mind that books on the shelf do not make you a better programmer.
 Ultimately, the only way to improve your programming is to write programs.
>        ACM  ，          ，         。    ，     ，       。
*
*    ：mingxinglai#gmail.com
*
*/

//    
#include <stdio.h>
#include <math.h>
#include <string.h>

int queenPlaces[92][8]; //  92          
int count = 0;
int board[8][8];//    
void putQueen( int ithQueen );//    ，         
int main(int argc, char* argv[])
{
	int n, i, j;
	memset( board, -1, sizeof(int) * 8 * 8 );//     
	memset( queenPlaces, 0, sizeof( int ) * 92 * 8 );
	
	putQueen( 0 );
	scanf("%d", &n);
	for( i = 0; i < n; i++ )
	{
		int ith;
		scanf("%d", &ith);
		for( j = 0; j < 8; j++ )
			printf("%d", queenPlaces[ith -1 ][j]);
		puts("");
	}
	return 0;
}

void putQueen( int ithQueen )
{
	int i, k, r;
	if( ithQueen == 8 )
	{
		count ++;
		return;
	}	
	
	for( i = 0; i < 8; i++ )
	{
		if( board[i][ithQueen] == -1)//    
		{
			board[i][ithQueen] = ithQueen;//    
			for( k = count; k < 92; k++ )
				queenPlaces[k][ithQueen] = i + 1;

			//      
			for( k = 0; k < 8; k++ )
				for( r = 0; r < 8; r++ )
					if( board[k][r] == -1 && ( k == i || r == ithQueen || fabs( k - i) == fabs( r - ithQueen) ) )
						board[k][r] = ithQueen;
			//     	
			putQueen( ithQueen + 1 );

			//  ，      
			for( k = 0; k < 8; k++)
				for( r = 0; r < 8; r++)
					if( board[k][r] == ithQueen) board[k][r] = -1;
		}
	}
		
}

コード例2:
より直感的で、簡潔で、理解しやすい.構想:8要素の配列で配置された駒がどの位置に置かれているかを記録し、新しい駒を配置する場合は、配置された駒と衝突しているかどうかを判断するだけでよい.

/*
*
*Declaration:The author of <<Accelerated C++>> has wrote in the end of that book: As you look for reading materimal,
 keep in mind that books on the shelf do not make you a better programmer.
 Ultimately, the only way to improve your programming is to write programs.
>        ACM  ，          ，         。    ，     ，       。
*
*    ：mingxinglai#gmail.com
*
*/


#include <stdio.h>

//hang[i] = j    i      j 
int ans[92][8], n, b, i, j, num, hang[8];

void queen( int i )
{
	int j, k;
	if( i == 8 )//        
	{
		for( j = 0; j < 8; j++)
			ans[num][j] = hang[j] + 1;
		num++;
		return;
	}
	// i     i  8   ，          i - 1        	
	for( j = 0; j < 8; j++)//               
	{
		for( k = 0; k < i; k++)//    i          
			if( hang[k] == j || ( k - i ) == ( hang[k] - j) || ( i - k ) == ( hang[k] - j) )
			 break;			

		if( k == i)//  i，   i + 1    
		{
			hang[i] = j;
			queen( i + 1 );
		}
	}	
}
int main(int argc, char* argv[])
{
	num = 0;
	queen(0);
	scanf("%d", &n);	
	for( i = 0; i < n; i++ )
	{
		scanf("%d", &b);
		for( j = 0; j < 8; j++ ) 
			printf("%d", ans[ b - 1][j]);
		printf("
");
	}
	return 0;
}