|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
算法的核心就是通过递归的办法不断地遍历棋盘,如果前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");
- }
复制代码 |
评分
-
查看全部评分
|