头歌回溯法-n皇后问题解题思路

对于n皇后问题，头歌回溯法是一种经典的解题思路。具体步骤如下：

1. 定义一个一维数组board[n]，表示第i行皇后的列位置为board[i]，初始化为-1。
2. 从第0行开始逐行考虑，对于每行i，尝试将皇后放在所有列j(0 <= j < n)中，检查该位置是否合法（即是否与之前的皇后位置冲突），如果合法则将board[i]设置为j，然后递归进入下一行（i+1），否则继续考虑下一个列j。
3. 如果所有列都尝试完了还没有找到合法位置，则回溯到上一行(i-1)，继续尝试下一个列j。
4. 当递归达到n行时，说明找到了一组合法的解。

需要注意的是，在检查当前位置是否合法时，需要分别检查同一列、同一主对角线、同一副对角线上是否已经存在其他皇后。可以用三个一维数组col[n]、dia1[2n-1]、dia2[2n-1]来分别记录每列、每个主对角线、每个副对角线上的占用情况。其中，对于第i行第j列的位置，其主对角线编号为i-j+n-1，副对角线编号为i+j。

使用头歌回溯法可在O(n!)时间内求解n皇后问题。