数据结构：递归n皇后问题

逃离我推掉我的手 2023-07-24 02:51 24阅读 0赞

# 数据结构：递归实现n皇后问题 #

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

**n皇后问题：在n\*n格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。**

以8\*8为例：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTI3NTAz_size_16_color_FFFFFF_t_70]

#include <stdio.h>
    #include <math.h>
    #define n 8 
    
    int x[n+1]={
        0};
    int sum=0;
    
    void print()
    {
        
        int i;
        printf("%d:\n",sum);
        for(i=1;i<=n;i++)
        printf("%d:%d\n",i,x[i]);
    }
    
    int Place(int k)
    {
        
        for(int j=1;j<k;j++)
            if(((int)fabs(k-j) == (int)fabs(x[j]-x[k])) 
            || x[j]==x[k])
            return 0;
        return 1;
    }
    
    void Backtrack(int t)
    {
        
        if(t>n)
        {
            sum++;
             print();
             getchar();
        }
        else
        for(int i=1;i<=n;i++)
        {
            x[t] = i;
             if(Place(t))   Backtrack(t+1);
        }
    }
    
    int main()
    {
        
        Backtrack(1);
    }

8\*8的 一共92种：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTI3NTAz_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTI3NTAz_size_16_color_FFFFFF_t_70]: /images/20230528/a82555eb3aa4499da9b3800e7f065863.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTI3NTAz_size_16_color_FFFFFF_t_70 1]: /images/20230528/9af9b22f53774dd29bfa00e79685032d.png