回溯-N皇后

回溯算法其实就是暴力穷举算法，只不过暴力穷举采用了先拆解子问题，然后将子问题使用递归的方式进行求解，并且在不满足条件的情况下，有向上回溯的过程。

许多复杂的，规模较大的问题都可以使用回溯法。

回溯问题看起来比较复杂，但一般都有固定的套路。

据我个人的理解，回溯过程中需要明确以下几个问题

1.什么是合法的解

2.什么时候退出递归

3.什么时候需要回溯

下面我们使用经典的N皇后问题，来解读回溯算法的一般思路。

案例1：

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

现在我们来依次解决前面提出的三个问题

1.什么是N皇后问题合法的解

其实题意中已经非常明确，n皇后放在nxn的棋盘山，要求同一行、同一列、同一斜线都只能有一个皇后。

我们是按照每行一个皇后开始放置的，每一行肯定不会重复，我们只需要校验每一列、每一个45度斜线、每一个135度斜线没有重复的皇后即可。

我们定义三个set来判断列和两个斜线上的皇后数

  //列
private Set<Integer> columnSet = new HashSet<>();
    //45度上升对角线
private Set<Integer> diagonalSet1 = new HashSet<>();
    //135度下降对角线
private Set<Integer> diagonalSet2 = new HashSet<>();

原文地址：http://www.cnblogs.com/wangbin2188/p/16848520.html