8×8的棋盘上摆8粒棋子,要求每横,竖,斜行都只能有一粒棋子,请问怎么摆?
来源:学生作业帮助网 编辑:作业帮 时间:2024/06/27 17:02:25
![8×8的棋盘上摆8粒棋子,要求每横,竖,斜行都只能有一粒棋子,请问怎么摆?](/uploads/image/z/12570677-53-7.jpg?t=8%C3%978%E7%9A%84%E6%A3%8B%E7%9B%98%E4%B8%8A%E6%91%868%E7%B2%92%E6%A3%8B%E5%AD%90%2C%E8%A6%81%E6%B1%82%E6%AF%8F%E6%A8%AA%2C%E7%AB%96%2C%E6%96%9C%E8%A1%8C%E9%83%BD%E5%8F%AA%E8%83%BD%E6%9C%89%E4%B8%80%E7%B2%92%E6%A3%8B%E5%AD%90%2C%E8%AF%B7%E9%97%AE%E6%80%8E%E4%B9%88%E6%91%86%3F)
8×8的棋盘上摆8粒棋子,要求每横,竖,斜行都只能有一粒棋子,请问怎么摆?
8×8的棋盘上摆8粒棋子,要求每横,竖,斜行都只能有一粒棋子,请问怎么摆?
8×8的棋盘上摆8粒棋子,要求每横,竖,斜行都只能有一粒棋子,请问怎么摆?
这个问题是由高斯首先提出的.
解决这一问题的最直接方法是穷举出所有摆法.我们先用回溯的思想按行递推出一种合理方案.开始棋盘为空,第一个皇后可以放在第一行的任意一个位置.我们把它试置在(1,1).这样,满足J=1或I=J的格子都不能再放皇后了.第二个皇后置在第二行,J可取3..8中的任意一列,我们先试放在(2,3).那么第三行的J可以取4..8,先试(3,4).以此类推,第四个皇后在(4,2)((4,7),(4,8)也可);然后是(5,6)((5,8)也可);第六行就只有(6,8)这一个位置可选.这时,第七行已没有空位置可放,说明前面皇后的位置试选得不对.回溯到上一行,由于第六行已没有其他位置可选择,只能删除(6,8)这个皇后,再退到第五行,把(5,6)的皇后移到(5,8).这样,第六行又没有可选位置了,回溯到第四行,把(4,2)移到(4,7)……最后,得出第一种可行方案:(1,1),(2,5),(3,8),(4,6),(5,3),(6,7),(7,2),(8,4).
我们可以编写一个程序,让计算机按上述思路穷举出所有摆法(网上也很多,搜“八皇后”).经计算机穷举,共有92种摆法.其实,这其中只有12种基本摆法,每种基本摆法又可经对称(水平、竖直、及沿两对角线翻转)、旋转(90、180、270度)等几何变换得出另外7种.这8种摆法的实质是一样的.那么,摆法共应有12*8=96种,为什么是92种呢?原来,在这12种基本摆法中,有一种是中心对称图形!用国际象棋记录法是:a4,b6,c8,d2,e7,f1,g3,h5.
推而广之还有所谓“N皇后问题”,即 在N*N的棋盘上,放置N个皇后.4皇后有2个答案,5后有10答,6后有4答,7后有40答,9后有352答,10后有724答.