不学网

 找回密码
 立即注册

只需一步,快速开始

手机号码,快捷登录

查看: 235|回复: 0

[c/c++] 八皇后问题

[复制链接]
j2cat 发表于 2018-1-6 18:33:19 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
  1. #include <stdio.h>

  2. #define N 8

  3. //地址偏移位
  4. typedef struct _tag_address_offset {
  5.         int ios;
  6.         int jos;
  7. }pos_os;
  8. //3个偏移位(左斜上,正上方,右斜上)
  9. pos_os pos[] = { {-1, -1}, {-1, 0}, {-1, 1} };
  10. //棋盘大小
  11. char board[N + 2][N + 2];
  12. //记录解法个数
  13. int count = 0;

  14. void display_map(void) {
  15.         for (int i = 0; i < N + 2; i++) {
  16.                 board[0][i] = '#';
  17.                 board[N + 1][i] = '#';
  18.                 board[i][0] = '#';
  19.                 board[i][N + 1] = '#';
  20.         }
  21.         for (int i = 1; i <= N; i++) {
  22.                 for (int j = 1; j <= N; j++) {
  23.                         board[i][j] = ' ';
  24.                 }
  25.         }
  26. }

  27. void display_result(void) {
  28.         for (int i = 0; i < N + 2; i++) {
  29.                 for (int j = 0; j < N + 2; j++) {
  30.                         printf("%c", board[i][j]);
  31.                 }
  32.                 printf("\n");
  33.         }
  34. }

  35. //检查该行该列,是否可以放置皇后
  36. int check(int i, int j) {
  37.         int ret = 1;
  38.         for (int p = 0; p < 3; p++) { //检查3个偏移方向上是否没有其他皇后
  39.                 int ni = i;
  40.                 int nj = j;

  41.                 while (ret && (board[ni][nj] != '#')) { //ret是否为假, 循环方向加偏移量是否走完'#'
  42.                         //加偏移量
  43.                         ni = ni + pos[p].ios;
  44.                         nj = nj + pos[p].jos;
  45.                         ret = ret && (board[ni][nj] != '*'); //是否有其他皇后是,则退出循环,标记ret为假,该行该列的3个方向上某个方向存在皇后.
  46.                 }
  47.         }
  48.         return ret;
  49. }

  50. void find(int i) {

  51.         if (i > N) { //i大于N时 证明该行该列已经放置完皇后,进行打印输出.并退出递归
  52.                 count++;
  53.                 printf("Solution: %d\n", count);
  54.                 display_result();

  55.         }
  56.         else {
  57.                 for (int j = 1; j <= N; j++) {//循环该列是否可以放置皇后,当j大于N,退出循环
  58.                         if (check(i, j)) { //判断该位置是否可以放置皇后;
  59.                                 board[i][j] = '*'; //放置皇后
  60.                                 find(i+1);         //继续检查下一行
  61.                                 board[i][j] = ' '; //回溯,递归完后清空该列的活动记录数据
  62.                         }
  63.                 }
  64.         }
  65. }

  66. int main(void) {
  67.         display_map();
  68.         find(1);
  69.         getchar();
  70.         return 0;
  71. }
复制代码

回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|手机版|小黑屋|不学网

GMT+8, 2018-6-21 16:40

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表