游戏开发论坛

 找回密码
 立即注册
搜索
查看: 4410|回复: 2

[原创] 用excel解决八皇后问题

[复制链接]

2

主题

3

帖子

35

积分

注册会员

Rank: 2

积分
35
发表于 2018-9-1 10:39:52 | 显示全部楼层 |阅读模式
-这可能是最蛋疼的excel问题之一

  • 1.八皇后介绍
某天,好友毁童年发来一个题目,就是找到八皇后的所有解。我说这非常简单,我写段代码给你撸出来,网上也到处都是代码。他说,不能写代码用excel的本身功能。我觉得你这就为难我胖西了,但是不能就这么认怂,所以仔细思考了一下,经过好几个小时之后确实解决了这个问题。只用了excel的基础功能+函数,找到了八皇后的全部的解。
先简单介绍八皇后的题目,下方来自百度:

八皇后问题,是一个古老而著名的问题,是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出:在8×8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。 高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解,后来有人用图论的方法解出92种结果。计算机发明后,有多种计算机语言可以解决此问题。

再继续看下面的内容时,读者可以尝试用自己的方法来解决这个问题。以免会有更好的方案被我的思路给干扰到。


实际上我最后也一次性的成功找到了全部的解。如下图:
每一个方块代表一个棋盘,标色是皇后。

  • 2.尝试思路
首先我尝试的思路是找到一个解,找到一个解就能理解题目的意思,在这之前我从没有做过这个题,也没有用其他方法来解决这个问题。现在得从头开始。
第一个方案是,第一个皇后位置进行假设,后面的棋子位用if函数进行剔除,后来发现这明显是失败的,因为我无法让每个单元格的函数进行重复计算,这样会造成循环引用,第一个方案失败。
我紧接着的第二个想法就是,吧图形编码化,把图形问题转化为数学问题。
  • 3.图形编码化
要把一个棋盘编码化意味着,我需要用一个数据来储存一个棋盘,很快我发现这个很容易做到,我们可以用一个八位数来储存一个棋盘,每一个数字代表一列,实际上代表一行也是没有问题的,好在八皇后的条件就是棋子不能同一列,这个省去了我们太多麻烦。只要哪个棋子再哪一行,这一列的数字就是多少即可。例如,11111111,这代表的是一个第一行被占满棋子的棋盘。
实际上棋子也不能同一行,这又给我们省去很多事情,棋盘就会变成123456578,因为同样的数字会代表同样的列,现在8个数字不能重复。接下来我们就要处理掉最后一个问题,那就是如何让他们不再统一斜排。不能在同以斜排意味着,这个数字的任意两位的差不能等于他们的间隔,这个问题如果采用代码解决就会非常简单,循环遍历即可,但是这里加上了自虐的条件,就是不能用代码来实现。我们要实现类似与循环的行为来进行这里的数据处理。
  • 4.用拖拉解决循环问题
Excel里面有一个非常像循环的操作,就是拖拉,循环几次就拖拉几行,最后一行的结果,就是循环的结果,这种行为非常类似于for(i=1 to 行数)机制,但是这里又有另一个问题,这只是单层循环并且根据excle的基础功能,似乎没有实现多层循环的方案(是不是二维数组可以视为2层循环?那样就得用一个单元格储存所有信息,就得给处理的数据设计数据结构来储存。这样似乎更幸苦。如果有其他的方案请告知我。)
再确定了只有一层循环之后,要做的就是循环展开,就要精确的计算最内层的循环次数,并且确定每一次循环的外层的编号数据。最内层的数据实际上在本题中,就是12345678能够组成多少个不同的数?
  • 5.排列组合
实际上有一定数学基础的人很容易解决这个答案,那就是8!=40320个。也就是说,做到最好的情况下,我们只要拖拉40320行,就可以便利所有符合条件的棋盘,excel一共支持104w行,在数据量超过10w行之后就基本会出现严重的卡顿情况,在这种复杂的计算的情况下,40320行的拖拉,还不是特别大的问题。
接下来的问题是,我没有要把这40320种可能性全部列出来。由于我们只有一层循环,我们的列出这些数字的时候一定需要按照某种严格的排序,才能确保不会遗漏。一个简单的方法就是,从小到大的方法去进行排列。最小的数字显然是12345678,其次就是12345687,按照这种方案,我们得写一些公式,就能吧他们全部列出来。这个函数是下一个数字 = f(上一个数字,1),然后你可以发现,这种函数极其难写,因为你得对这个数字进行内部排序,而且多次,一定会牵扯到循环问题。
实际上每一次的变化,都是2个数字的变动,都是一次局部排序,如果能把局部排序的需要调动的数字给列出来,就可以容易的列出这个数据组合。我们渴望获得一个这样的数组。



前面的没有变动的数字就让他不要变动,只要对后面的排序变动的数据进行操作。这里有一个问题,就是一定要知道我的数字调动到哪一层了。比如只变动最后2个,还是最后3个,还是最后4个。这样我需要知道,每一行,我变动到了哪个位置,我就需要知道每一层的行数,也是循环量。实际上这个内部的循环量每一个都是小的x皇后问题。用阶乘计算,然后逐行减去,就是本层的数据。使用mod和vlookup就可以定位泵行的变动位数,就能列出上体这种表,只需要再增加一个阶乘表的差就可以。实际上这个表也可以写在公式里,但是未来清晰,单列一个表,然后用vlookup引用即可。这个表shi这样的:


第一列是位数,第二列是阶乘差,第三列是阶乘。
你知道对自己的行数和位数定位取余就能确定自己的排序位置。然后就能得到yi张我上面说到的表。
  • 6.用字符串函数解决抽取问题
现在我们要用上面的”字符变化表”来获得真正的数据对字符进行真正的排序。我如何对这个数据进行真正的排序呢。这里采用字符串来储存。一个完整的字符串初始状态是12345678,遇到了一个11111121,意味着最后2位需要颠倒才能拿到正确的数值。
这里你要理解我们上面做11111121的真正目的,就是1代表着这一位实际上是后续的数字种排序最小的数字。最后的21的2意味着这里应该是后面2为种排序第二小的数字,那就是78的8,这样就转化为了12345687.为了顺利的实现这个目的,加上了8行的辅助列。逐步的后拆解后续的数字,方便对后续进行排序。本质上,我们是从这个字符串种,抽出了它的每一位的数字。就拿12345678,遇到11111121来说,11111121的第一个1,需要抽取的是12345678的第一个数字,最小的,实际上哟个mid就可以完成,剩余2345678,第二个抽去2,依次,直到78,遇到了2,这次需要先抽取8,再抽取7,就实现了12345678转化为12345687.于是现在的表格变成这样

  • 7.展示所有可能方案
你发现最后的综合排序已经是我们需要的解了,至此,只要拖拉40320行,我们就已经找出了全部可能的解,接下来我们只要对数据进行筛选,找出符合的数据。
  • 8.对可能的数据验证
上面说到,要找到所有位数差=数字差的数,都不符合条件。如12345678,1在第一位,2在第二位,1-2=1的位数-2的位数,这是不符合的。这里用笨办法来处理,因为只有八位,我们把所有的位数差都列出来。那就是:
第一位和后面的位数差,2345678
第二位和后面的位数差,345678
最后以为位数差,8
总体列出来就是,2345678345678456785678678788.
把他们每一个变成一行,然后真正的计算位数差,位数差=数字差,该位为0.
我们现在要剔除所有本行中包含0 的数字,很简单的方法,全部相乘,只要有一个0结果就是0,结果不是0那么意味着所有的都不是0.新起一列进行验算。结果是这样的。

  • 9.筛选出正确答案
即将大公搞成,增加一个筛选,验算结果0的选项去掉。


选中这一列,excel惊喜的提示你


没错,我们吧所有的解找出来了,再加一列,吧前面一个一个挑出来的数字完整的数字吧。
下面就是全部的答案。
15863724,16837425,17468253,17582463,24683175,25713864,25741863,26174835,26831475,27368514,27581463,28613574,31758246,35281746,35286471,35714286,35841726,36258174,36271485,36275184,36418572,36428571,36814752,36815724,36824175,37285146,37286415,38471625,41582736,41586372,42586137,42736815,42736851,42751863,42857136,42861357,46152837,46827135,46831752,47185263,47382516,47526138,47531682,48136275,48157263,48531726,51468273,51842736,51863724,52468317,52473861,52617483,52814736,53168247,53172864,53847162,57138642,57142863,57248136,57263148,57263184,57413862,58413627,58417263,61528374,62713584,62714853,63175824,63184275,63185247,63571428,63581427,63724815,63728514,63741825,64158273,64285713,64713528,64718253,68241753,71386425,72418536,72631485,73168524,73825164,74258136,74286135,75316824,82417536,82531746,83162574,84136275

  • 10.答案图形化
接下来把这些答案变成棋盘,为了方便观看,这就容易的多了


一个判断函数,数字位置判断行号,符合的为1,不符合为0.然后用条件格式,或者其他任何方法,把有数字的位置显示出来。
  • 11.整理发布
最后一步,为了看的更清晰,吧所有的解根据列棋子的位置分列,就得到了最开始的图。

12.给我点赞
可以前往我的知乎,找我要原始表格

1

主题

16

帖子

80

积分

注册会员

Rank: 2

积分
80
发表于 2018-9-4 10:22:21 | 显示全部楼层
公式说的不明确,补充一下:
替换字符串函数:SUBSTITUTE(包含需要替换字符的字符串,需要替换的旧字符串,新字符串),新字符串可以填空值,这样就达到了楼主说的抽取字符串的目的。
取当前剩余数字的第n个最小值(求n值):我用trunc函数取整,mod取余,附一张截图如下 TIM截图20180904102128.png

0

主题

2

帖子

5

积分

新手上路

Rank: 1

积分
5
发表于 2018-10-11 21:31:12 | 显示全部楼层
为啥不贴上知乎链接?
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

作品发布|文章投稿|广告合作|关于本站|游戏开发论坛 ( 闽ICP备17032699号-3 )

GMT+8, 2024-3-29 14:57

Powered by Discuz! X3.4

Copyright © 2001-2021, Tencent Cloud.

快速回复 返回顶部 返回列表