再帰的に八皇后問題を解く

問題の説明
チェスができる人はよく知っています.皇后は横、縦、斜線で歩数を問わず他の駒を食べることができます.どのように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つの碁盤の上で1行ごとに最大1つの駒しか並べられなくて、1つの皇后を並べてもし私が彼女の制御範囲を記録するならば、私は次の行から1列ごとに並べてすでに並べた皇后に制御されていない領域を探します.8人の皇后が並ぶまで順番に探した.
毎回皇后を置く過程から、私たちはすべての皇后の配置過程が同じであることを発見することができて、それでは私たちは1つの皇后の配置過程を書くだけでいいことができて、皇后の総数は最大8つしかなくて、明らかにこのような特徴はすでに再帰的な性質を構成しています.
実際の解の過程で,列制御,45度角制御,135度角制御を3つの一次元配列で記録できた.
これにより、コードを書くことができます.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int resu[92][8], mark[9];
int rang[9], line_45[17], line_135[17];
int count=0;

void f(int i)
{
    int j;
    if(i > 8)
    {
        //       
        for(j=0; j < 8; j++)
            resu[count][j] = mark[j+1];
        count++;
    }
    //          ，             
    for(j=1; j < 9; j++)
    {
        if(rang[j] && line_45[i+j] && line_135[j+9-i])
        {
            mark[i] = j;
            rang[j] = line_45[i+j] = line_135[j+9-i] = 0;
            f(i+1);
            rang[j] = line_45[i+j] = line_135[j+9-i] = 1;
        }
    }
}

int main()
{
    int nCase, number, i;
    memset(rang, 1, sizeof(rang));
    memset(line_45, 1, sizeof(line_45));
    memset(line_135, 1 , sizeof(line_135));
    scanf("%d", &nCase);
    f(1);
    while(nCase-- > 0)
    {
        scanf("%d", &number);
        for(i=0; i < 8; i++)
            printf("%d", resu[number-1][i]);
        printf("
");
    }
    return 0;
}