算法分析N后问题

实验内容：

N后问题，即在N×N的棋盘上，要放上N个皇后，使得他们两两不在同一条直线上和一条斜线上。

实验要求：

用回溯法或迪杰斯特拉算法实现N皇后问题

实验源代码：

#include "stdio.h" 

#include "windows.h" 

int N; 

int place(int k); 

void backtrack(int i);

void chessboard(); 

static int sum, x[100]; 

int main() 

{ 

    printf("请输入你的皇后数目：");

    scanf("%d",&N);

    backtrack(0); 

    system("pause"); 

    return 0; 

} 

int place(int k) 

{

for (int j = 0; j < k; j ++)

        if (abs(k - j) == abs(x[j] - x[k]) || (x[j] == x[k])) 

            return 0; 

    return 1; 

} 

void backtrack(int t) 

{

    if (t == N) chessboard(); 

    else 

     for (int i = 0; i < N; i ++) {

            x[t] = i; 

            if (place(t)) 

                backtrack(t + 1); 

        } 

} 

void chessboard() 

{ 

    printf("第%d种解法:\\n", ++ sum); 

for (int i = 0; i < N; i ++) {

     for (int j = 0; j < N; j ++)

            if (j == x[i]) printf("@ "); 

            else printf("* "); 

            printf("\\n"); 

    } 

    printf("\\n"); 

}

实验结果：

1、运行代码输入皇后数目为2，由于不可能存在满足条件的皇后使得它们既不在同一直线上也不在同一斜线上，所以程序直接运行到结束找不到符合条件的解。

2、输入皇后数目为4时可以找到两种解，打印出结果如下图所示。

3、输入皇后数目为5时，也有解并打印结果。

4、当皇后数目为8时，就是我们经常说的8皇后问题，得到92种解法。

实验小结：

N后问题，是我们经常说的一类算法问题，也是一种益智的游戏，在我们日常生活中接触比较多的就是8皇后问题。在这个问题的解决过程中主要就是保证两个条件，任意两个皇后既不在同一直线上，也不在同一斜线上，不再同一直线上，我们可以理解为在N×N的棋盘上，每一行都有一个皇后，每一列也都有一个皇后，而不在同一斜线上我们则可以利用斜率来计算，由于在同一斜线上时它们两个的连线的与水平线的夹角为450 因此，他们在行上相差的格数和在列上的相等，利用这一点我们可以来判断两个皇后究竟是不是满足条件的。在具体实践时，我们可以先试探，在不符合条件时进行回退。最终实现这一问题。

通过本次实验，编程实现了对N后问题的解决，也更清楚的了解了该问题解决的具体过程，对要求的算法有了更好的了解。