八皇后问题,输出了所有情况,不过有些结果只是旋转了90度而已

匿名网友 匿名网友 发布于: 2015-08-30 00:00:00
阅读 92 收藏 0 点赞 0 评论 0

八皇后问题,输出了所有情况,不过有些结果只是旋转了90度而已。(回溯算法的典型例题,是数据结构书上算法的具体实现,大家都亲自动手写过这个程序吗?)
#define N 8
int Board[N][N];
int Valid(int i, int j) {  // 判断下棋位置是否有效
 int k = 1;
 for(k=1; i>=k && j>=k;k++)
  if(Board[i-k][j-k]) return 0;
 for(k=1; i>=k;k++)
  if(Board[i-k][j])  return 0;
 for(k=1; i>=k && j+k<N;k++)
  if(Board[i-k][j+k]) return 0;
 return 1;
}

void Trial(int i, int n) {  // 寻找合适下棋位置
 if(i == n) {
  for(int k=0; k<n; k++) {
   for(int m=0; m<n; m++)
    printf(“%d “, Board[k][m]);
   printf(“n”);
  }
  printf(“n”);
 } else {
  for(int j=0; j<n; j++) {
   Board[i][j] = 1;
   if(Valid(i,j))
    Trial(i+1, n);
   Board[i][j] = 0;
  }
 }
}

int main(int argc, char* argv[]) {
 Trial(0, N);
}

评论列表
文章目录