拿8皇后这个问题来说，问题的解可以表示为1,2,3,..8这8个数一个permutation。所以从这个角度想，我们可以通过遍历{1,2,3,..,8}的所有permutation的角度来实现这个算法。STL中已经有了next_permutation这个函数。当然，这样做太暴力了。在此基础上我们可以做一个轻微的优化：为next_permutation函数加一个额外的参数：index i。 要求这个函数返回的新序列一定要把前i个字符有所改变。比如，假如当前permutation的序列是{4,1,2,3}，我们发现{4,1}这个prefix不work，那我们就可以把index i设置成2，要求一定把1增加。那么下一个permutation就是{4,2,1,3}而不是{4,1,3,2}。用这种方式我们就可以跳过一些permutation，从而达到backtracking的目的。而对于next_permutation函数的这个改进是通用的，可以用来解决很多类似的backtracking问题（只要解空间是{1,2,...,n}的permutation)
--
FROM 61.172.164.*