生成和检查结合.

7.4.1 八皇后

利用数组C[cur]记录列数，行号。关键在于回溯 -- 如果不合适，那么回溯到上一层。break;

c#include 
    
     using namespace std;int n, tot;const int maxn = 100;int C[maxn];void search(int cur){    int i, j;    if(cur == n) tot++;    else for(i = 0; i < n; i++)    {        int ok = 1;        C[cur] = i;        for(j = 0; j < cur; j++)        {            if(C[cur] == C[j] || cur-C[cur] == j-C[j] || cur+C[cur] == j+C[j])            {                ok = 0;                break;            }        }        if(ok) search(cur+1);    }}int main(int argc, const char *argv[]){    while(~scanf("%d", &n))    {        tot = 0;        search(0);        printf("%d\n", tot);    }    return 0;}
    

7.4.2 素数环

cpp#include 
    
     #include 
     
      const int maxn = 100;bool is_prime[maxn];int prime[maxn];int pn;int n;void init(){    int i, j;    pn = 0;    memset(is_prime, 1, sizeof(is_prime));    for(i = 2; i < maxn; i++)    {        if(is_prime[i]) prime[pn++] = i;        for(j = 0; j < pn && i * prime[j] <= maxn; j++)        {            is_prime[i * prime[j]] = 0;            if(i % prime[j] == 0) break;        }    }}int a[maxn];int vis[maxn];void dfs(int cur){    // 递归边界    if(cur == n && is_prime[a[0] + a[n-1]])    {        for(int i = 0; i < n; i++) printf("%d ", a[i]);        printf("\n");    }    else for(int i = 2; i <= n; i++) if(!vis[i] && is_prime[i + a[cur-1]])    {        a[cur] = i;        vis[i] = 1;        dfs(cur+1);        vis[i] = 0;    }}int main(int argc, const char *argv[]){    init();    a[0] = 1;    while(~scanf("%d", &n))    {        dfs(1);    }    return 0;}
     
    

7.4.3 困难的串

每次从后面寻找串即可， 前面的串已经是没有重复的了。

c#include 
    
     #include 
     
      using namespace std;int n, l;const int maxn = 100;int tot;int a[maxn];int dfs(int cur){    // 递归一次即找到一个解    if(tot++ == n)    {        for(int i = 0; i < cur; i++) printf("%c", a[i] + 'A');        printf("\n");        return 0;    }    for(int i = 0; i < l; i++)    {        a[cur] = i;        int ok = 1;        for(int j = 1; j*2 <= cur+1; j++)        {            int equal = 1;            for(int k = 0; k < j; k++) if(a[cur-k] != a[cur-k-j])            {                equal = 0;                break;            }            if(equal) { ok = 0; break;}        }        if(ok && !dfs(cur+1)) return 0;    }    return 1;}int main(int argc, const char *argv[]){    while(~scanf("%d%d", &n, &l))    {        dfs(0);    }    return 0;}