《数据结构与算法》——八皇后问题

luciferzf

算法的核心就是通过递归的办法不断地遍历棋盘，如果前n-k个皇后都找到位置了，那么就能判断第n-k+1个能否找到位置。
遍历一行的每一个位置，通过递归的办法不断地判断这一行的每一个位置是否满足条件，若满足条件调用一次函数，遍历下一行的每个位置，当遍历完八行，每一行都找到满足条件的位置则打印并返回，若是出现一行找不到满足条件的位置，则返回但不打印。

#include<cstdio>
#include<cstdlib>
#include<iostream>
using namespace std;

int n = 0;

void Output(int chess[8][8])
{
        n++;
        printf("No.%d\n", n);
        for (int i = 0; i < 8; i++)
        {
                for (int j = 0; j < 8; j++)
                {
                        cout << chess[i][j] << " ";
                }
                cout << endl;
        }
        cout << endl;
}

int isDanger(int chess[8][8], int row, int col)
{
        int flag1 = 1, flag2 = 1, flag3 = 1, flag4 = 1, flag5 = 1, flag6 = 1;
        for (int i = row; i >= 0; i--)
        {
                if (chess[i][col] == 1)
                {
                        flag1 = 0;
                        break;
                }
        }
        for (int i = row; i < 8; i++)
        {
                if (chess[i][col] == 1)
                {
                        flag2 = 0;
                        break;
                }
        }
        for (int i = row, j = col; i >= 0 && j >= 0; i--, j--)
        {
                if (chess[i][j] == 1)
                {
                        flag3 = 0;
                        break;
                }
        }
        for (int i = row, j = col; i < 8 && j < 8; i++, j++)
        {
                if (chess[i][j] == 1)
                {
                        flag4 = 0;
                        break;
                }
        }
        for (int i = row, j = col; i < 8 && j >= 0; i++, j--)
        {
                if (chess[i][j] == 1)
                {
                        flag5 = 0;
                        break;
                }
        }
        for (int i = row, j = col; i >= 0 && j < 8; i--, j++)
        {
                if (chess[i][j] == 1)
                {
                        flag6 = 0;
                        break;
                }
        }

        if (flag1&&flag2&&flag3&&flag4&&flag5&&flag6)return 0;
        else return 1;
}

void queen(int chess[8][8], int row, int n)
{
        int chess2[8][8];
        for (int i = 0; i < 8; i++)
        {
                for (int j = 0; j < 8; j++)
                {
                        chess2[i][j] = chess[i][j];
                }
        }

        if (row == 8)
        {
                Output(chess2);
        }
        else
        {
                for (int j = 0; j < n; j++)
                {
                        if (!isDanger(chess2, row, j))
                        {
                                for (int i = 0; i < 8; i++)
                                {
                                        chess2[row][i] = 0;
                                }
                                chess2[row][j] = 1;
                                queen(chess2, row + 1, n);
                        }
                }
        }

}

int main()
{
        int chess[8][8];
        for (int i = 0; i < 8; i++)
        {
                for (int j = 0; j < 8; j++)
                {
                        chess[i][j] = 0;
                }
        }
        queen(chess, 0, 8);
        printf("\nThere is %d ways in total\n", n);

        system("PAUSE");
}