アルゴリズムのまとめ——八皇后問題(三種類の解法)

問題の説明はチェスができる人はすべてよく知っています:皇后は横、縦、斜線の上で歩数に限らず他の駒を食べることができます.どのように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は92種類の異なる配置方法のいずれかを要求するので、92種類の異なる配置方法を一度に求めて、1つの配列に保存してもいいです.この問題を解くためにはマトリクスシミュレーション盤が必要で、1つの駒を試すたびにまだ制御されていない格子の上に置くしかなく、新しい駒を置くと、その制御できるすべての位置にマークを設定し、このようにして8つの駒を置くことができます.1つの配置が完了したら、次の配置を試してみます.辞書順に実行可能な並べ方を記録するには、一定の順序で試してみましょう.すなわち、最初の駒を小さい頃から大きい順に試みる.1番目の駒の各位置について、2番目の駒を実行可能な位置から小さい順から大きい順に試みる.第1の第2の駒が固定されている場合、第3の駒を実行可能な位置から小さい順から大きい順に試みる.順次類推する.
まず,8*8のマトリクスシミュレーション盤があり,現在配置されている駒が制御する領域を識別する.92行の行ごとに8要素の2次元配列で実行可能な配置方法を記録します.再帰プログラムを使用して、配置を試みるプロセスを実現します.基本思想は,我々が最初の駒を並べ,その制御領域を設けたと仮定すると,この問題は7皇后問題となり,8皇后と同様の方法で問題の解を得ることができる.では、私たちはどのように1つの皇后の駒を置くかに重点を置いて、配置の基本的なステップは:1から8番目の位置まで、順番に駒を各制御されていない位置に置くことを試みて、その駒が制御している格子を設定して、問題をもっと小さい規模の問題に変えて下に再帰して、注意しなければならないのは毎回新しい制御されていない位置を試してみる前に、前回の試行位置で制御した格子を復元します.
リファレンスプログラム1

#include 
#include 
int queenPlaces[92][8]; //  92          
int count = 0;
int board[8][8]; //    
void putQueen(int ithQueen); //    ，        

void main()
{
   int n, i, j;  
    for(i = 0; i < 8; i++){  //    
	    for(j = 0; j < 8; j++)
	        board[i][j] = -1;
	    for(j = 0; j < 92; j++)
	        queenPlaces[j][i] = 0;
    }
    putQueen(0); //  0       ，       queenPlaces   
   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]);
        printf("
");
    }
}
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;
			 //            ith      i+1    
			 // i    ，    ith               
		     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 || abs(k - i) == abs(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
以上の方法では,1つの2次元配列で碁盤が置かれた駒の制御状況を記録し,新しい駒が置かれるたびにその制御範囲を列挙法で判断した.また、各列を3つの1次元配列でそれぞれ記録することもでき、各45度の斜線と各135度の斜線にすでに配置された駒が制御されているかどうかは、新しい駒が配置されるたびに、その制御範囲を検索する必要がなく、3つの1次元数グループで配置された駒と衝突しているかどうかを直接判断することができ、衝突しない場合、3つの1次元配列の対応する値をそれぞれ設定することで、新しい駒の制御範囲を記録することもできる.
リファレンスプログラム2

#include 
int  record[92][9], mark[9], count = 0; //record     ，mark     ；
bool range[9], line1[17], line2[17]; //       ，45 ，135          
void tryToPut(int ); //       
void main()
{
	int i, testtimes, num;
	scanf("%d", &testtimes);
	
	for(i = 0; i <=8; i++)
		range[i] = true;
	for(i = 0; i < 17; i ++)
		line1[i] = line2[i] = true;

	tryToPut(1);

	while(testtimes --){
		scanf("%d", &num);
		for(i = 1; i <=8; i++)
			printf("%d", record[num - 1][i]);
		printf("
");
	}
}

void tryToPut(int i){
    if(i > 8){ //             ，           
	    for(int k = 1; k < 9; k ++) 
		    record[count][k] = mark[k];
	    count ++;
     }					
     for(int j=1; j<=8; j++){                 
	     if(range[j] && line1 [i + j] && line2[i - j + 9]){ //         ，
                                               //             
		    mark[i] = j;
		    range[j] = line1[i + j] = line2[i - j + 9] = false;
            tryToPut(i + 1);
		    range[j] = line1[i + j] = line2[i - j + 9] = true;
	    }
    }
}

解題構想3この問題は,駒が置かれた制御領域をシミュレートするために碁盤をシミュレートするのではなく,8要素の配列だけで置かれた駒がどの位置に置かれているかを記録し,新しい駒を置く場合は,置かれた駒と衝突しているかどうかを判断するだけでよい.
リファレンスプログラム3

#include 
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;
	}
	for (j=0; j<8; j++){ //     i           
        for(k=0; k

実現中によく見られる問題1:列挙法を用いて、8つの皇后のすべての可能な位置の組み合わせを窮挙し、互いに食べられるかどうかを一つ一つ判断し、タイムアウトエラーを得る.
問題2:複数のグループの入力に対して、複数のグループの出力があり、各グループの出力後に改行符を付けず、フォーマットが間違っている.
問題3:入出力の関数に詳しくなく、数字を文字に変換したり、8つの整数を8ビットの10進数整数に変換して出力を完了したりして、不要な冗長コードを形成しようとします.