作业帮8×8的棋盘上摆8粒棋子,要求每横,竖,斜行都只能有一粒棋子,请问怎么摆?
来源：学生作业帮助网 编辑：作业帮 时间：2024/05/05 17:44:24
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答.