Question

一个难题，八列八行一个棋盘，有八个哨兵，将他们分别放在棋盘上，并且横竖斜行都只能放一个哨兵，怎么放？

Answer 1

这个问题是由高斯首先提出的。解决这一问题的最直接方法是穷举出所有摆法。我们先用回溯的思想按行递推出一种合理方案。开始棋盘为空，第一个皇后可以放在第一行的任意一个位置。我们把它试置在（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）这一个位置可选。