八皇后问题

发布时间:2016-12-8 12:19:17 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"八皇后问题",主要涉及到八皇后问题方面的内容,对于八皇后问题感兴趣的同学可以参考一下。

#include <stdio.h> #include <stdlib.h> #include <string.h> typedef int bool; #define true 1 #define false 0 #define M (8) #define OK(x, y) ((x) >= 0 && (x) < M && (y) >= 0 && (y) < M) static int board[M][M]; /* 棋盘 */ int cnt = 0; /* 记录解法种类 */ /* 判断当前位置是否合法? 如果横竖斜方向存在皇后,则返回0,否则返回1 */ static int right_pos(int row, int col) { int i = 0; for(i = 0; i < M; i++) { if(board[row][i] || board[i][col]) return false; if(OK(row - i, col - i)) { if(board[row - i][col - i]) return false; } if(OK(row + i, col + i)) { if(board[row + i][col + i]) return false; } if(OK(row + i, col - i)) { if(board[row + i][col - i]) return false; } if(OK(row - i, col + i)) { if(board[row - i][col + i]) return false; } } return true; } /* 自动根据棋盘状态判断下一步应该走向哪里 */ static bool next(int * row, int * col) { int i; /* 换行 */ if(*row + 1 < M) { *row += 1; return true; } else { /* 否则,改变列,回溯 */ /* 如果回溯到第0行还不行,返回false */ if(*col == 0) return false; (*col)--; /* 找到上一列的位置 */ for(i = 0; i < M; i++) if(board[i][*col]) break; /* 清除不合法的位置 */ board[i][*col] = 0; *row = i; return next(row, col); } } void print() { int i, j; cnt++; printf("第%d种解法:\n", cnt); /* 打印结果 */ for(i = 0; i < M; i++) { for(j = 0; j < M; j++) { if(board[i][j]) printf("Q "); else printf("* "); } printf("\n"); } printf("\n"); getchar(); } void go() { int row, col, good; row = col = 0; good = 1; do { if(good) { board[row][col] = 1; if(col == M - 1) { print(); board[row][col] = 0; row = M - 1; if(!next(&row, &col)) return ; } else { col += 1; row = 0; } } else if(!next(&row, &col)) return ; good = right_pos(row, col); }while(1); } int main() { go(); printf("COUNT:%d\n", cnt); return 0; }

上一篇:Android开发规范——命名
下一篇:开发笔记之20140215

相关文章

关键词: 八皇后问题

相关评论