趣味集算:八皇后问题

有关国际象棋的问题很多,八皇后问题就是其中相当著名的一个。在 8×8 的国际象棋棋盘中,放入 8 个皇后,使它们不互相攻击,共有多少种方法呢?

国际象棋中皇后的威力巨大,攻击范围是同一行、同一列以及同一斜行,因此,符合条件的 8 个皇后必须都不在同一行、同一列或者同一斜行上。

由于每一行中只能放入一个皇后,所以可以使用一个长度为 8 的序列,依次设入每行中皇后所在的列数,以此来表示皇后的放置状态。当某一行还没有置入皇后时,即该行没有一列上有皇后,记为 0;而每次置入新的皇后时,如果列数不是序列中已有的,就说明没有皇后在同一列中。这样,不同行、不同列就能很容易的判定了。

那么,在置入新的皇后时,就只需要保证它与已有的皇后都不在同一斜行上了。如果一个皇后在 m 行 k 列,那么在 m+n 行,最多只有两个位置和它在同一斜行上,而且这两个位置距离它的横向距离等于纵向距离,也就是说最多

只有 (m+n,k+n) 和(m+n,k-n)这两个位置与这个皇后在同一斜行上。

这样,只要把每个皇后在每一行的所有情况都检查一遍,就可以知道共有多少种情况满足要求了。

经过上面的抽象分析,我们只需要在集算器中,通过循环计算来完成这些判断就行了。具体代码如下:

第 1 行,A1 就是记录皇后放置状态的序列;B1 定义了一个变量 i,用来在计算时记录当前放置皇后的行。

第 2 行代码,每循环一次,就把当前行的皇后下移 1 列,用这样的方法遍历行中每个位置。

第 3 行代码,如果棋子移到了第 9 列,说明当前行的棋子已经完成了所有位置的循环,此时,应该把当前行的记录复原为 0,并将 i 减 1,可以返回去继续上一行的遍历;特别的,当第 1 行也全部循环后,说明完成了遍历,此时 i 被设为 0,停止循环。

第 4 行代码,在移动第 1 行皇后时,可以不用判断,直接开始放置第 2 个皇后。

第 6 行代码,判断已放好的皇后中,是否存在同一列的;

第 7 行代码,判断已放好的皇后中,是否存在同一斜行的。如果既没有同一列的,也没有同一斜行的,就可以继续放置下一行的皇后了。

如果此时 8 个皇后都放置成功,则在第 9 行代码中记录下当前每个皇后的位置。

经过计算,A10 中结果如下:

可以在 C1 中查看具体结果:

当然,还可以用经典的递归方式解决这个问题,集算器中递归调用子函数的方法的代码如下:

在 A2 定义的子程序中,在一个新行中尝试放置皇后,在 B2 中循环每一个可能的列。

A5 中的子程序用来判断新的一行是否可以使用指定的列,其中在 C5 中查看是否本列已存在皇后,第 6 行查看是否已有皇后在同一斜行,在这样的情况下说明不能放置。如果某一列可以放置,则判断是否 8 个皇后都放置成功,如果已全部设置成功则记录在 C1 中。如果未放置满,则递归调用 A2 中的子程序,继续在下一行放置。这种方法的代码更易理解,计算结果与前面的方法是相同的。

©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 218,546评论 6 507
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 93,224评论 3 395
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 164,911评论 0 354
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 58,737评论 1 294
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 67,753评论 6 392
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 51,598评论 1 305
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 40,338评论 3 418
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 39,249评论 0 276
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 45,696评论 1 314
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,888评论 3 336
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 40,013评论 1 348
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 35,731评论 5 346
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 41,348评论 3 330
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,929评论 0 22
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 33,048评论 1 270
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 48,203评论 3 370
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 44,960评论 2 355

推荐阅读更多精彩内容

  • 有关国际象棋的问题很多,八皇后问题就是其中相当著名的一个。在 8×8 的国际象棋棋盘中,放入 8 个皇后,使它们不...
    小黄鸭呀阅读 322评论 0 0
  • 泛读这本俄罗斯文化史,以致敬这个文化巨匠灿若繁星、艺术作品壮丽璀璨的民族。 人在旅途,很容易忘记自己是谁,还以为自...
    如系此心阅读 690评论 0 4
  • 今天和大家聊聊恐惧带来的认知局限论 01 现在的我还有40分钟时间更文,我静心觉知刚刚潜意识的波澜:我一定啊要...
    笋鸦深剖阅读 910评论 2 10
  • 码字岛打卡第3天 在“得到”听到这样一个故事,有一头特别的鲸,它发生的频率在52赫兹,比其他鲸发声频率(50赫兹)...
    星酉林夕阅读 223评论 0 0
  • 《雪斩》 文/无哲 多年以后,他飘回来 带着少许疯狂 覆在枝条的眉毛上 覆上枯叶折皱的脉络 覆紧茅草的骨架 覆在厚...
    山西无哲阅读 124评论 0 0