自己写的八皇后算法
快两年没有来鱼C学编程了，当初看小甲鱼的C语言和汇编教程（汇编基本全忘了。。。），不过经常过来也就是打打酱油，今天微博看到小甲鱼的数据结构八皇后教程。
想起当初学算法的时候，没有完成这道经典题目，于是就试着写了个。
在小甲鱼的代码基础上对检测冲突和棋盘的空间复杂度做了点优化。。。
很久没有用C/C++写代码，大一大二学的是C++
去年升大三开始学校学的是Java，很久没用指针，
不知道写的好不好，轻拍O(∩_∩)O~
#include <stdio.h>
#define CHESS_ROW 8 //棋盘行数
#define CHESS_COLUMN 8 //棋盘列数
//清除row+1行的棋子
void clearRow(int row, int ch[]) {
int j;
for (j = 0; j < CHESS_COLUMN; j++)
ch = 0;
}
//判断是否有冲突，有冲突返回1，没有返回0
/*
* 由于棋子是由上往下一行行排列的，
* 所以没有必要判断下半部分的棋盘
* 是否有冲突（还没有摆棋子），
* 只需要判断上半列，左上，右上三个方向。
* 即每次判断上一行的(row-1,col),(row-1,col-1)和(row-1,col+1)
* 三个位置即可
*/
int isConflict(const int row, const int col, const int ch[]) {
int i;
int offset = 1; //用于判断左右两边的偏移量
for (i = row - 1; i >= 0; i--, offset++) {
if ( ch != 0) {
return 1; //上半列有冲突
}
if ( (col - offset) >= 0) {
if ( ch != 0) { //判断是否越界
return 1; //左上有冲突
}
}
if ( (col + offset) < CHESS_COLUMN) { //判断是否越界
if ( ch != 0) {
return 1; //右上有冲突
}
}
}
return 0; //没有冲突返回0
}
//打印棋盘
void printChess(int ch[] ) {
int i, j;
static int count = 1;
printf("第%d种情况：\n", count);
for (i = 0; i < CHESS_ROW; i++) {
for (j = 0; j < CHESS_COLUMN; j++) {
printf("%d ",ch);
}
printf("\n");
}
printf("\n");
count++;
}
/*
* 八皇后递归算法，只使用了一个棋盘。
* 每次摆放到该行的最后一列时，
* 在返回上一行前先清空上一行上面
* 摆放的棋子。则不需要每次调换都
* 生成棋盘记录当前棋盘状况。
*/
void eightQueen(const int row, int ch[]) {
int j;
if (row == 8) { //第八行完成，打印棋盘
printChess(ch);
clearRow(row - 1, ch); //清空最后一行，以便下一轮计算
return;
}
for (j = 0; j < CHESS_COLUMN; j++) {
if ( !isConflict(row, j, ch)) { //检测没有冲突，递归调用
ch = 1;
eightQueen(row + 1, ch);
}
}
if (row > 0) { //没有到首行，则清空上一行
clearRow(row - 1, ch);
}
}
int main() {
int chess;
int i, j;
//初始化棋盘
for (i = 0; i < CHESS_ROW; i++) {
for (j = 0; j < CHESS_COLUMN; j++) {
chess = 0;
}
}
eightQueen(0, chess);
return 0;
}
写的很好向你学习 写的很好啊 淡定，淡定，淡定…… 看帖，回复支持下 看看老帖，支持下 我想说，没人回帖吗 看帖，支持下 看看，回复支持下 再看看，支持下 八皇后问题是经典算法······· 学习了！:lol: 写的不错，学习了啊 写得挺好的 怎么就没人回复呢 多谢楼主分享 感谢分享，看看 感谢楼主无私奉献！ 八皇后问题，想起当年学习往事，哎，不堪回首 确实是值得思考的一个问题！ 呵呵不错不错，。。。
页:
[1]
2