《数据结构与算法》——八皇后问题
算法的核心就是通过递归的办法不断地遍历棋盘，如果前n-k个皇后都找到位置了，那么就能判断第n-k+1个能否找到位置。遍历一行的每一个位置，通过递归的办法不断地判断这一行的每一个位置是否满足条件，若满足条件调用一次函数，遍历下一行的每个位置，当遍历完八行，每一行都找到满足条件的位置则打印并返回，若是出现一行找不到满足条件的位置，则返回但不打印。
#include<cstdio>
#include<cstdlib>
#include<iostream>
using namespace std;
int n = 0;
void Output(int chess)
{
n++;
printf("No.%d\n", n);
for (int i = 0; i < 8; i++)
{
for (int j = 0; j < 8; j++)
{
cout << chess << " ";
}
cout << endl;
}
cout << endl;
}
int isDanger(int chess, 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 == 1)
{
flag1 = 0;
break;
}
}
for (int i = row; i < 8; i++)
{
if (chess == 1)
{
flag2 = 0;
break;
}
}
for (int i = row, j = col; i >= 0 && j >= 0; i--, j--)
{
if (chess == 1)
{
flag3 = 0;
break;
}
}
for (int i = row, j = col; i < 8 && j < 8; i++, j++)
{
if (chess == 1)
{
flag4 = 0;
break;
}
}
for (int i = row, j = col; i < 8 && j >= 0; i++, j--)
{
if (chess == 1)
{
flag5 = 0;
break;
}
}
for (int i = row, j = col; i >= 0 && j < 8; i--, j++)
{
if (chess == 1)
{
flag6 = 0;
break;
}
}
if (flag1&&flag2&&flag3&&flag4&&flag5&&flag6)return 0;
else return 1;
}
void queen(int chess, int row, int n)
{
int chess2;
for (int i = 0; i < 8; i++)
{
for (int j = 0; j < 8; j++)
{
chess2 = chess;
}
}
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 = 0;
}
chess2 = 1;
queen(chess2, row + 1, n);
}
}
}
}
int main()
{
int chess;
for (int i = 0; i < 8; i++)
{
for (int j = 0; j < 8; j++)
{
chess = 0;
}
}
queen(chess, 0, 8);
printf("\nThere is %d ways in total\n", n);
system("PAUSE");
}
页:
[1]