IT公司面试题收集整理---C相关---八皇后详解

2013-3-8 16:16| 发布者: 红黑魂| 查看: 1272| 评论: 0|原作者: wang6279026|来自: CSDN博客

摘要: 八皇后详解，有人可能看不懂上一篇帖子，我又特别整理了一下，尽量弄得简单易懂。注释很详细，基本上都有注释。先贴一张图，看图看程序比较容易贴上详细代码view plaincopyprint?#includestdio.h#defineROW8//代表列 ...

八皇后详解，有人可能看不懂上一篇帖子，我又特别整理了一下，尽量弄得简单易懂。注释很详细，基本上都有注释。

先贴一张图，看图看程序比较容易

贴上详细代码

[cpp]view plaincopyprint?
#include  
#define ROW 8//代表列，坐标是x  
#define COL 8//代表行，坐标是y  
#define NUM 7//八皇后问题，数组下标0-7  
  
#define TRUE 0//真  
#define FALSE 1//假  
  
#define YES 1//有皇后  
#define NO 0//没有皇后  
  
#define NO_BACK 0//表示不需要回溯  
#define BACK 1//表示需要回溯  
  
  
int a[ROW][COL];//默认值都是0，表示坐标没有皇后，如果改为1，表示这个坐标有皇后  
int k=0;//表示第k中情况  
  
//n代表遍历的列的下标，即X值。ROW  
int queens(int n)  
{  
    int i, j;  
    //输出八皇后棋盘  
    if(n>NUM)  
    {  
        printf("----------%06d----------\n",++k);  
        for(i=0;i
        {  
            for(j=0;j
                printf("%s",a[i][j]==1?"○":"●");//为0说明不是皇后，为1说明是皇后  
            printf("\n");  
        }  
        printf("--------------------------\n\n");  
        return BACK;//表示正常返回，进行回溯  
    }  
    //如果没有遍历完全，  
    for(j=0;j//遍历Y值0->COL  
    {  
        int flag=TRUE;  
        //这个循环遍历的是X值，就是Y值不变，X值变化  
        for(i=0;i//根据传过来的列的下标X值，ROW值，进行遍历  
        {  
            //如果【同行】【左斜角，东北西南方向】【右斜角，西北东南方向】出现了皇后的话，则推出此次循环，进行下次循环  
            if(a[i][j]==YES||((i+j-n)>=0&&a[i][i+j-n]==YES)||((j+n-i
            {  
                flag=FALSE;  
                break;  
            }  
        }  
        if(flag==TRUE)//如果刚才的循环没有出现这种情况  
        {//那么此处放置皇后  
            a[n][j]=YES;  
            if(queens(n+1)==BACK)  
            {//如果下层遍历需要进行回溯  
                a[n][j]=NO;//此处不放置皇后  
            }else{//如果下层遍历不需要回溯的话，返回  
                return NO_BACK;  
            }  
        }  
    }  
    //遍历Y值的时候，一直没有出现合适的，出现了flag=FALSE;那么说明下级不能放置皇后，那么进行回溯  
    return BACK;  
      
}  
int main(void)  
{  
    queens(0);  
    return 0;  
}  