【数据结构day15--N皇后问题求解】

• • • N皇后问题
    • • 判断是否放置
      • 回溯
      • 完整代码
      • 测试结果

问题描述

在N×N格的国际象棋上摆放N个皇后，使其不能互相攻击，即不能处于同一列或同一行，也不能处在同一斜线上，请问有多少种摆法？

N皇后问题是回溯算法的经典案例，此处我们采用递归回溯方式解决。

算法思路

（1）使用一个一维数组来存储棋盘，清空棋盘，设当前行为第1行，当前列为第1列。

（2）在当前行判断从第i（1 <= i <= tempN）列是否满足条件（即同一行、同一列、同一斜线上无两个皇后），若满足则执行第（3）步，若不满足则当前列数i加1后再判断是否满足条件。

（3）若当前行第i列满足条件，则在当前位置放置一个皇后，将当前行数（tempT）加1并判断当前行数（tempT）是否大于总行数（tempN），若大于则记录一个解，否则执行第（2）步。

（4）使用一维数组solution来存储棋盘，数组中第i个元素的值代表第i行的皇后的位置，这样的好处是将问题的空间规模压缩为了O(N)。

代码实现如下：

• 判断是否位于同一行

  由于在一行只放置一个皇后，因此不必判断两个皇后是否位于同一行。

• 判断是否位于同一列

  对于判断第j行的皇后和第tempT行的皇后是否位于同一列十分简单，即判断tempSolution[j]是否等于tempSolution[tempT]。

• 判断是否位于同一斜线

  对于判断第j行的皇后和第tempT行的皇后是否位于同一斜线，，只需要判断第j行的皇后的行数减去第tempT行皇后的行数是否等于第j行的皇后的列数减去第tempT行皇后的列数，即判断abs(tempT - j) 是否等于abs(tempSolution[j] - tempSolution[tempT])，由于斜线有正斜线和反斜线故对结果取绝对值。

bool place(int* tempSolution, int tempT)
{
    for(int j = 1; j < tempT; ++j)
    {
        if((abs(tempT - j) == abs(tempSolution[j] - tempSolution[tempT])) || (tempSolution[j] == tempSolution[tempT]))
        {
            return false;
        }
    }
    return true;
}

（1）在当前行判断从第i（1 <= i <= tempN）列是否满足条件（即同一行、同一列、同一斜线上无两个皇后），若满足则执行第（2）步，若不满足则当前列数i加1后再判断是否满足条件。

（2）若当前行第i列满足条件，则在当前位置放置一个皇后，将当前行数（tempT）加1并判断当前行数（tempT）是否大于总行数（tempN），若大于则记录一个解，否则执行第（1）步。

void backTracking(int* tempSolution, int tempN, int tempT)
{
    if(tempT > tempN)
    {
        for(int i = 1; i <= tempN; ++i)
        {
            printf("% d",tempSolution[i]);
        }
        printf("n");
    }else{
        for(int i = 1; i <= tempN; ++i) //判断第tempT行的每一列
        {
            tempSolution[tempT] = i;
            if(place(tempSolution, tempT))
            {
                backTracking(tempSolution, tempN, tempT + 1);
            }
        }
    }
}

例如4皇后问题求解流程如下图：

#include 
#include 
#include 


bool place(int* tempSolution, int tempT)
{
    for(int j = 1; j < tempT; ++j)
    {
        if((abs(tempT - j) == abs(tempSolution[j] - tempSolution[tempT])) || (tempSolution[j] == tempSolution[tempT]))
        {
            return false;
        }
    }
    return true;
}


void backTracking(int* tempSolution, int tempN, int tempT)
{
    if(tempT > tempN)
    {
        for(int i = 1; i <= tempN; ++i)
        {
            printf("% d",tempSolution[i]);
        }
        printf("n");
    }else{
        for(int i = 1; i <= tempN; ++i) //判断第tempT行的每一列
        {
            tempSolution[tempT] = i;
            if(place(tempSolution, tempT))
            {
                backTracking(tempSolution, tempN, tempT + 1);
            }
        }
    }
}


void nQueen(int tempN)
{
    int* solution = (int*)malloc((tempN + 1) * sizeof(int));
    for(int i = 0; i <= tempN; ++i)
    {
        solution[i] = 0;
    }
    backTracking(solution, tempN, 1);
}

int main(){
	nQueen(4);
	return 0;
}

2 4 1 3
3 1 4 2