递归--八皇后-蒲公英云

递归--八皇后

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

问题描述
会下国际象棋的人都很清楚：皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如
何将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