回溯法解决N皇后问题（以四皇后为例）

     以4皇后为例，其他的N皇后问题以此类推。所谓4皇后问题就是求解如何在4×4的棋盘上无冲突的摆放4个皇后棋子。在国际象棋中，皇后的移动方式为横竖交叉的，因此在任意一个皇后所在位置的水平、竖直、以及45度斜线上都不能出现皇后的棋子，例子

     要求编程求出符合要求的情况的个数。四皇后问题有很多种解法，这里主要介绍一种经典的解决方法：回溯法

     回溯法的基本思想是：可以构建出一棵解空间树，通过探索这棵解空间树，可以得到四皇后问题的一种或几种解。这样的解空间树有四棵

     在如上图所示的4×4的棋盘上，按列来摆放棋子，首先因为皇后棋子不能在同一列，所以先排除有2个或2个以上的棋子在同一列的情况，所以第一个棋子在第一列有4种摆放方法（第1列第1行，第1列第2行，第1列第3行，第1列第4行），同样第二个棋子在第二列有4种，同样第三个棋子在第三列有4种，同样第四个棋子在第四列有4种，所以进行简单的排除不在同一列的情况后，还有4×4×4×4=256种可能，但是在这256种可能里，依然存在比如棋子在同一行，或在45度斜线上的情况出现。另一个角度思考，所有的满足四皇后问题的摆放方式一定都存在于这256种情况之中。简单的理解就是：这256种棋盘局面包含了所有满足4皇后问题的解，但是不包含全部的棋盘局面。

     下面是解空间树的示例（以上一段的按列摆放的方式来进行示例讲解），其中第i层的棋盘局面是在第i-1层的棋盘局面演化而来的（1