我来我网
https://5come5.cn
 
您尚未 登录  注册 | 菠菜 | 软件站 | 音乐站 | 邮箱1 | 邮箱2 | 风格选择 | 更多 » 
 

本页主题: 国际象棋五皇后问题 显示签名 | 打印 | 加为IE收藏 | 收藏主题 | 上一主题 | 下一主题

iguard



贝尔诺勋章 自信之戒
性别: 帅哥 状态: 该用户目前不在线
头衔: 要走了
等级: 版主
家族: 战略研究所
发贴: 11259
威望: 5
浮云: 407
在线等级:
注册时间: 2005-12-07
最后登陆: 2009-11-04

5come5帮你背单词 [ disagree /disə'gri:/ vi. 不符,不一致,不同意,争执,不适合 ]


国际象棋五皇后问题

国际象棋棋盘由8*8的格子组成,皇后是最厉害的一种棋子可以吃掉横线,斜线,直线上的任意一个子.现在给你5个皇后,放在棋盘上.

保证:
1.这5个棋子彼此不会攻击.
2.再放任何一个棋子在这个棋盘上都会被这5个棋子中的某个棋子吃掉!

要求得到所以可能的排列方式。

大家讨论一下有什么算法可以解决这个问题。
顶端 Posted: 2007-01-09 14:10 | [楼 主]
iguard



贝尔诺勋章 自信之戒
性别: 帅哥 状态: 该用户目前不在线
头衔: 要走了
等级: 版主
家族: 战略研究所
发贴: 11259
威望: 5
浮云: 407
在线等级:
注册时间: 2005-12-07
最后登陆: 2009-11-04

5come5帮你背单词 [ shoe /u:/ n. 鞋 ]


以下是我的程序:

Copy code
lineUsed=[-1,-1,-1,-1,-1,-1,-1,-1]#lineUsed[i]=-1 means line i is empty,lineUsed[i]=j means line i is used by a Queen who is right in row j
rowUsed=[-1,-1,-1,-1,-1,-1,-1,-1] #rowUsed[i]=-1 means row i is empty,rowUsed[i]=j means row i is used by a Queen who is right in line j
boxUsed=[]
diagonal_1_used=[]
diagonal_2_used=[]

def Test(boxList):
   lineUsed2=[-1,-1,-1,-1,-1,-1,-1,-1]
   rowUsed2=[-1,-1,-1,-1,-1,-1,-1,-1]
   diagonal_1_used2=[]
   diagonal_2_used2=[]
   for m in range(0,len(boxList)):
       lineUsed2[boxList[m]//8]=boxList[m]%8
       rowUsed2[boxList[m]%8]=boxList[m]//8
       diagonal_1_used2.append((boxList[m]%8)+(boxList[m]//8))
       diagonal_2_used2.append((boxList[m]//8)-(boxList[m]%8))
   for n in range(0,64):
       if lineUsed2[n//8]==-1 and rowUsed2[n%8]==-1 and (not (n//8)+(n%8) in diagonal_1_used2) and (not (n//8)-(n%8) in diagonal_2_used2):
           return False
   return True
   
def myPrint(boxList):
   for i in range(0,len(boxList)):
       L_N=boxList[i]//8
       R_N=boxList[i]%8
       print L_N,'-',R_N,'     ',
   print ''

count=0

def Try(boxNum):
   global count
   if boxNum<64:
       for set in [True,False]:
           lineNum=boxNum//8
           rowNum=boxNum%8
           if (lineUsed[lineNum]==-1) and (rowUsed[rowNum]==-1) and (not lineNum+rowNum in diagonal_1_used) and (not lineNum-rowNum in diagonal_2_used) and (not boxNum in boxUsed) and set:
               boxUsed.append(boxNum)
               lineUsed[lineNum]=rowNum
               rowUsed[rowNum]=lineNum
               diagonal_1_used.append(lineNum+rowNum)
               diagonal_2_used.append(lineNum-rowNum)
               if len(boxUsed)<5:
                   Try(boxNum+8-rowNum)
               if len(boxUsed)==5:
                   if Test(boxUsed):
                       count+=1
                       print count,'         '
                       myPrint(boxUsed)
               boxUsed.pop()
               lineUsed[lineNum]=-1
               rowUsed[rowNum]=-1
               diagonal_1_used.pop()
               diagonal_2_used.pop()
           if set==False:
               Try(boxNum+1)

Try(0)
input()
本帖最近评分记录:
  • 浮云:5 (by est) | 理由: 引发讨论
  • 顶端 Posted: 2007-01-09 14:11 | [1 楼]
    fengtao57



    性别: 帅哥 状态: 该用户目前不在线
    等级: 鹤立鸡群
    家族: 八宝推倒委员会
    发贴: 1131
    威望: 0
    浮云: 1156
    在线等级:
    注册时间: 2005-10-05
    最后登陆: 2007-06-24

    5come5帮你背单词 [ myself /mai'self/ pron. (反身代词)我自己,我亲自 ]


    程序不是重要的
    主要是算法
    你直接写算法流程就行了嘛
    顶端 Posted: 2007-01-09 14:32 | [2 楼]
    iguard



    贝尔诺勋章 自信之戒
    性别: 帅哥 状态: 该用户目前不在线
    头衔: 要走了
    等级: 版主
    家族: 战略研究所
    发贴: 11259
    威望: 5
    浮云: 407
    在线等级:
    注册时间: 2005-12-07
    最后登陆: 2009-11-04

    5come5帮你背单词 [ erase /i'reiz/ vt. 擦掉,抹掉 ]


    Quote:
    引用第2楼fengtao57于2007-01-09 14:32发表的:
    程序不是重要的
    主要是算法
    你直接写算法流程就行了嘛

    基本思想是:
    先排列出一个五皇后互相不打架的局面(当然要把所有可能都排出来),再逐个格子判断是否能放下第六个皇后,如果所有格子都无法放下第六个皇后,则输出一个结果,并统计总方案数。
    顶端 Posted: 2007-01-09 16:27 | [3 楼]
    战无敌平琼宇



    性别: 保密 状态: 该用户目前不在线
    等级: 鹤立鸡群
    家族: 低调一族
    发贴: 1135
    威望: 0
    浮云: 1126
    在线等级:
    注册时间: 2006-08-17
    最后登陆: 2007-06-11

    5come5帮你背单词 [ troublesome /'trΛblsəm/ a. 令人烦恼的,麻烦的,讨厌的 ]


    楼主强啊,用的什么语言哦
    顶端 Posted: 2007-01-13 11:31 | [4 楼]
    richardxx





    性别: 保密 状态: 该用户目前不在线
    等级: 品行端正
    发贴: 193
    威望: 0
    浮云: 1144
    在线等级:
    注册时间: 2005-10-01
    最后登陆: 2009-02-28

    5come5帮你背单词 [ derive /di'raiv/ vt. 得到,追寻…的起源,派生,引出;vi. 由来,衍生 ]


    棋盘多项式直接数学解出。
    顶端 Posted: 2007-01-14 00:01 | [5 楼]
    20001202





    性别: 帅哥 状态: 该用户目前不在线
    等级: 荣誉会员
    家族: 萌菌物语
    发贴: 9382
    威望: 3
    浮云: 467
    在线等级:
    注册时间: 2005-10-15
    最后登陆: 2012-05-26

    5come5帮你背单词 [ harm /ha:m/ n. & vt. 伤害,危害,损害 ]


    ~~~才发现这个帖子   国际象棋能做到8皇后不攻击的~`~从国际象棋来说哈   程序不太懂
    顶端 Posted: 2007-07-08 12:19 | [6 楼]
    震月



    年度之星奖 社区建设奖 终身成就奖
    性别: 帅哥 状态: 该用户目前不在线
    等级: 幕后精英
    家族: 坛猪弹劾组
    发贴: 16349
    威望: 13
    浮云: 85107
    在线等级:
    注册时间: 2006-03-28
    最后登陆: 2024-07-10

    5come5帮你背单词 [ critical /'kritikəl/ n. 批评家,评论家 ]


    Quote:
    引用第4楼战无敌平琼宇于2007-01-13 11:31发表的:
    楼主强啊,用的什么语言哦


    Python
    顶端 Posted: 2007-07-08 13:49 | [7 楼]
    kiwiy



    性别: 帅哥 状态: 该用户目前不在线
    等级: 栋梁之材
    家族: 飞跃重洋
    发贴: 660
    威望: 0
    浮云: 1161
    在线等级:
    注册时间: 2006-07-29
    最后登陆: 2009-06-28

    5come5帮你背单词 [ defect /di'fekt/ n. 缺陷,缺点,缺乏 ]


    Quote:
    引用第5楼richardxx于2007-01-14 00:01发表的:
    棋盘多项式直接数学解出。

    ms不行吧...rock polynomials 不能保证其控制的有效性吧....
    再说数学解的求解还是倚赖递归.
    倒不如直接回溯....有效性可以通过 布尔阵元素和是否为64 检验....
    顶端 Posted: 2007-07-08 18:22 | [8 楼]
    carwin





    性别: 保密 状态: 该用户目前不在线
    等级: 品行端正
    发贴: 189
    威望: 0
    浮云: 1204
    在线等级:
    注册时间: 2006-09-17
    最后登陆: 2014-02-11

    5come5帮你背单词 [ highly /'haili/ adv. 高度地,很,非常 ]


    应该是八皇后问题吧??
    经典的pascal黄皮书上有算法的(好想是清华出的那本)
    应该是用的回溯法
    顶端 Posted: 2007-07-13 21:53 | [9 楼]
    我来我网·5come5 Forum » 程序员之家

    Total 0.010217(s) query 5, Time now is:11-27 09:02, Gzip enabled
    Powered by PHPWind v5.3, Localized by 5come5 Tech Team, 黔ICP备16009856号