字符串数组的全排列到八皇后问题详解

1.记得在一次面试终要求写一个程序，程序题目为：

输入字符串的全排列：例如输入字符串为abc，那么他的全排列有abc，bac等六种。尝试确定输入字符串的全排列，并输出。

字符串全排其实是一个数学问题，根据数学计算可以知道，程序的复杂度为O（n！），并且没有比较明显的改善算法。比较常见的算法都是将问题变为一个子问题，然后对子问题进行反复迭代，得出最终的结果。

而子问题就是采用字母固定的方法，即先在字符串中选择一个字母（一般为第一个字母），选择一个固定的位置（第一个位置），然后对剩下的字母挨个选择并在剩余的位置上选择一个位置，如此继续，便可以得出将第一个字母在第一个位置上的剩余字符串的全排列；变换第一个位置上的字母，重复上面的过程，直到所有字母都已经到了第一个位置上呆过位置。

根据8皇后摆放位置的要求，可以看出就是一个字符串重排的问题。可以将8*8象棋格子认为是2个包含8个元素的数组。其中一个数组表示水平方向的位置，而另外一个表示竖直方向上的位置。而将行看成不变的数组来标记皇后放的位置，因此对其中一个数组进行全排列就能够保证任意两个皇后肯定不同行不同列。接下来，我们只需要判断得到的每一个排列对应的八个皇后是不是在同一对角斜线上，也就是数组的两个下标i和j，是不是i-j==ColumnIndex[i]-Column[j]或者j-i==ColumnIndex[i]-ColumnIndex[j]。 下面是代码实现：
首先修改全排列的函数实现：
//检查是否符合八皇后的位置要求
bool CheckQueen(int ColumnIndex[], int length)
{    for(int i = 0; i < length; ++ i)    {        for(int j = i + 1; j < length; ++ j)        {            if((i - j == ColumnIndex[i] - ColumnIndex[j])                || (j - i == ColumnIndex[i] - ColumnIndex[j]))            return false;        }    }     return true;} void PrintQueen(int ColumnIndex[], int length){    printf("满足八皇后的第%d个摆放位置为：\n", number);     for(int i = 0; i < length; ++i)        printf("%d\t", ColumnIndex[i]);    printf("\n");}
void EightQueen(){    const int queens = 8;    int ColumnIndex[queens];    for(int i = 0; i < queens; ++ i)        ColumnIndex[i] = i;//初始化皇后在每一列的位置    Permutation(ColumnIndex, 0, queens);}