注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

微软、Google等面试题

剑指Offer:名企面试官精讲典型编程题

 
 
 

日志

 
 

程序员面试题精选100题(58)-八皇后问题[算法]  

2011-05-03 15:16:16|  分类: 数字游戏 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

题目:在8×8的国际象棋上摆放八个皇后,使其不能相互攻击,即任意两个皇后不得处在同一行、同一列或者同一对角斜线上。下图中的每个黑色格子表示一个皇后,这就是一种符合条件的摆放方法。请求出总共有多少种摆法。

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

这就是有名的八皇后问题。解决这个问题通常需要用递归,而递归对编程能力的要求比较高。因此有不少面试官青睐这个题目,用来考察应聘者的分析复杂问题的能力以及编程的能力。

由于八个皇后的任意两个不能处在同一行,那么这肯定是每一个皇后占据一行。于是我们可以定义一个数组ColumnIndex[8],数组中第i个数字表示位于第i行的皇后的列号。先把ColumnIndex的八个数字分别用0-7初始化,接下来我们要做的事情就是对数组ColumnIndex做全排列。由于我们是用不同的数字初始化数组中的数字,因此任意两个皇后肯定不同列。我们只需要判断得到的每一个排列对应的八个皇后是不是在同一对角斜线上,也就是数组的两个下标ij,是不是i-j==ColumnIndex[i]-Column[j]或者j-i==ColumnIndex[i]-ColumnIndex[j]

关于排列的详细讨论,详见本系列博客的第28篇,《字符串的排列》,这里不再赘述。

接下来就是写代码了。思路想清楚之后,编码并不是很难的事情。下面是一段参考代码:

int g_number = 0;

 

void EightQueen()

{

    const int queens = 8;

    int ColumnIndex[queens];

    for(int i = 0; i < queens; ++ i)

        ColumnIndex[i] = i;

 

    Permutation(ColumnIndex, queens, 0);

}

 

void Permutation(int ColumnIndex[], int length, int index)

{

    if(index == length)

    {

        if(Check(ColumnIndex, length))

        {

            ++ g_number;

            PrintQueen(ColumnIndex, length);

        }

    }

    else

    {

        for(int i = index; i < length; ++ i)

        {

            int temp = ColumnIndex[i];

            ColumnIndex[i] = ColumnIndex[index];

            ColumnIndex[index] = temp;

 

            Permutation(ColumnIndex, length, index + 1);

 

            temp = ColumnIndex[index];

            ColumnIndex[index] = ColumnIndex[i];

            ColumnIndex[i] = temp;

        }

    }

}

 

bool Check(int ColumnIndex[], int length)

{

    for(int i = 0; i < length; ++ i)

    {

        for(int j = i + 1; j < length; ++ j)

        {

            if((i - j == ColumnIndex[i] - ColumnIndex[j])

                || (j - i == ColumnIndex[i] - ColumnIndex[j]))

            return false;

        }

    }

 

    return true;

}

 

void PrintQueen(int ColumnIndex[], int length)

{

    printf("Solution %d\n", g_number);

 

    for(int i = 0; i < length; ++i)

        printf("%d\t", ColumnIndex[i]);

   

    printf("\n");

}

博主何海涛对本博客文章享有著作权。网络转载请注明出处http://zhedahht.blog.163.com/。整理出版物请和作者联系。对解题思路有任何建议,欢迎在评论中告知,或者加我微博http://weibo.com/zhedahht或者http://t.163.com/zhedahht与我讨论。谢谢。

  评论这张
 
阅读(45271)| 评论(28)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017