递归--八皇后

我不是女神ヾ 2021-12-17 02:59 336阅读 0赞

八皇后这个典的问题，是每个真正程序员必须经历过的。这也是我第二次来解决这个问题了，第一次应该是学数据结构那时候吧。这次写起来顺利多了，基本没遇到什么卡壳的地方。递归+回溯。

**问题描述**  
会下国际象棋的人都很清楚：皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如  
何将8 个皇后放在棋盘上（有8 \* 8 个方格），使它们谁也不能被吃掉！这就是著名的八皇后  
问题。 对于某个满足要求的8 皇后的摆放方法，定义一个皇后串a 与之对应，即a=b1b2...b8，  
其中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

**我的解题：根据题目的要求，我们可以先把这92种情况存储在一个数字里面。**

**　　递归，每一行确定一个点之后，就可以把问题缩小为一个相同的，更小的问题。回溯，没确定一个点后，标记下来，当递归完成之后，再回复回来，继续找本行的下一个情况。**

**　　中间还有判断是否符合规则，我这只判断同列、正反对角线这三种情况，因为每行只填一个数。**

**代码：**

#include <stdio.h>
    
    int queen[8][8];
    int nArr[93][8];
    int nCount;
    
    int Jude(int r,int c);
    void Queen(int row);
    void save();
    void print();
    
    
    int main()
    {
        int n,t;
        nCount = 0;
        Queen(0);
        //2printf("Count:%d\n",nCount);
    
        scanf("%d",&n);
        while(n)
        {
            scanf("%d",&t);
            print(t);
            n--;
        }
    
        return 0;
    }
    
    int Jude(int r,int c)
    {
        int i,j;
        
        //check col
        for(i = 0; i < r; i++)
        {
            if(queen[i][c] == 1)
                return 0;
        }
    
        //
        for(i = r-1,j = c-1; i >= 0 && j >= 0; i--,j--)
        {
            if(queen[i][j] == 1)
                return 0;
        }
    
        //
        for(i = r-1,j = c+1; i >= 0 && j <= 7; i--,j++)
        {
            if(queen[i][j] == 1)
                return 0;
        }
        return 1;
    }
    
    void Queen(int row)
    {
        int col;
    
        if (row == 8)
        {
            nCount++;
            save();    
        }
        else
        {
            for(col = 0; col <= 7; col++)
            {
                if(Jude(row,col))
                {
                    queen[row][col]=1;
                    Queen(row+1);
                    queen[row][col]=0;
                }
            }
        }
    }
    
    void save()
    {
        int row,col;
    
        for(row = 0; row <= 7; row++)
        {
            for(col = 0; col <= 7; col++)
            {
                if(queen[row][col] == 1)
                {
                    nArr[nCount][row] = col+1;
                    break;
                }
            }
        }
    }
    
    void print(int n)
    {
        int i;
        for(i = 0; i <= 7; i++)
        {
            printf("%d",nArr[n][i]);
        }
        printf("\n");
    }
    
    2013/5/18  18:53

感觉经历了这次实习之后，我在代码规范性上有了很大的提高。这也得益于看别人的规范代码，多学习。

我的思路是比较笨的方法。因为每次判断是否可以放置皇后的时候，都去遍历一遍和它相同的并在它前面的列、两个对角线的所有点，看它们有没有被放置。其实更好的办法是用三个数组来存储列和连个对角线的情况，因为只有8列，那么我们可以开个range数组来记录列，然后开个lineA\[17\]数组来记录135度对角线，同理lineB\[17\]数组记录45度对角线。因为每个对角线都有共性，比如135度对角线它们每个点的row+col是相等的，45度对角线它们的row-col+9同样是相同的。因此用三个数组来存储可以大大减少我们的代码量，非常好的方法！要学习！！

#include <stdio.h>
    
    int queen[8][8];
    int nArr[93][8];
    int range[9],lineA[17],lineB[17];//col用来标示列，lineA用来标示135度对角线，lineB用来标示45度对角线
    int mark[9];
    int nCount;
    
    void Queen(int row);
    void print(int n);
    
    
    int main()
    {
        int n,t,i;
        nCount = 0;
    
        for(i = 0; i <= 8; i++)
        {
            range[i] = 1;
        }    
        for(i = 0; i <= 16; i++)
        {
            lineA[i] =  lineB[i] = 1;
        }
    
        Queen(0);
        //printf("Count:%d\n",nCount);
    
        scanf("%d",&n);
        while(n)
        {
            scanf("%d",&t);
            print(t);
            n--;
        }
    
        return 0;
    }
    
    void Queen(int row)
    {
        int col;
    
        if (row == 8)
        {
            nCount++;
            for(col = 0; col <=7; col++)
            {
                nArr[nCount][col]=mark[col];
            }
        }
        else
        {
            for(col = 0; col <= 7; col++)
            {
                if(range[col] && lineA[row-col+9] && lineB[row+col])
                {
                    mark[row] = col; 
                    range[col]=lineA[row-col+9]=lineB[row+col] = 0;
                    Queen(row+1);
                    range[col]=lineA[row-col+9]=lineB[row+col] = 1;
                }
            }
        }
    }
    
    void print(int n)
    {
        int i;
        for(i = 0; i <= 7; i++)
        {
            printf("%d",nArr[n][i] + 1);
        }
        printf("\n");
    }
    2013/5/19 11:57

转载于:https://www.cnblogs.com/Jason-Damon/archive/2013/05/18/3085862.html