鱼C论坛

 找回密码
 立即注册
查看: 6750|回复: 28

[技术交流] 自己写的八皇后算法

[复制链接]
发表于 2013-3-9 22:10:38 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

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

x
快两年没有来鱼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[][CHESS_COLUMN]) {
        int j;
        for (j = 0; j < CHESS_COLUMN; j++)
                ch[row][j] = 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[][CHESS_COLUMN]) {
        int i;
        int offset = 1;                //用于判断左右两边的偏移量
        for (i = row - 1; i >= 0; i--, offset++) {
                
                if ( ch[i][col] != 0) {
                        return 1;                //上半列有冲突
                }
                
                if ( (col - offset) >= 0) {
                        if ( ch[i][col - offset] != 0) {        //判断是否越界
                                return 1;        //左上有冲突
                        }
                }

                if ( (col + offset) < CHESS_COLUMN) {        //判断是否越界
                        if ( ch[i][col + offset] != 0) {
                                return 1;        //右上有冲突
                        }
                }
        }

        return 0;                                //没有冲突返回0
}

//打印棋盘
void printChess(int ch[][CHESS_COLUMN] ) {
        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[i][j]);
                }
                printf("\n");
        }
        printf("\n");
        count++;
}

/*
 * 八皇后递归算法,只使用了一个棋盘。
 * 每次摆放到该行的最后一列时,
 * 在返回上一行前先清空上一行上面
 * 摆放的棋子。则不需要每次调换都
 * 生成棋盘记录当前棋盘状况。
 */
void eightQueen(const int row, int ch[][CHESS_COLUMN]) {
        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[row][j] = 1;
                        eightQueen(row + 1, ch);
                }
        }
        if (row > 0) {                //没有到首行,则清空上一行
                clearRow(row - 1, ch);
        }
}

int main() {
        int chess[CHESS_ROW][CHESS_COLUMN];
        int i, j;
        //初始化棋盘
        for (i = 0; i < CHESS_ROW; i++) {
                for (j = 0; j < CHESS_COLUMN; j++) {
                        chess[i][j] = 0;
                }
        }

        eightQueen(0, chess);
        return 0;
}


想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2013-3-10 00:00:56 | 显示全部楼层
写的很好  向你学习
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2013-4-8 16:56:35 | 显示全部楼层
写的很好啊   
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2013-5-15 22:34:39 | 显示全部楼层
淡定,淡定,淡定……
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2013-7-2 21:37:55 | 显示全部楼层
看帖,回复支持下
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2013-7-2 23:42:52 | 显示全部楼层
看看老帖,支持下
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2013-7-3 16:16:56 | 显示全部楼层
我想说,没人回帖吗
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2013-7-3 17:49:49 | 显示全部楼层
看帖,支持下
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2013-7-3 19:45:59 | 显示全部楼层
看看,回复支持下
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2013-7-4 20:51:08 | 显示全部楼层
再看看,支持下
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2013-8-9 10:24:48 | 显示全部楼层
八皇后问题是经典算法·······
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2013-8-10 17:07:29 | 显示全部楼层
学习了!:lol:
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2013-8-15 08:29:44 | 显示全部楼层
写的不错,学习了啊
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2013-10-9 09:16:59 | 显示全部楼层
写得挺好的 怎么就没人回复呢
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2013-10-9 23:23:25 | 显示全部楼层
多谢楼主分享
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2013-12-28 23:26:22 From FishC Mobile | 显示全部楼层
感谢分享,看看
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2014-4-28 12:26:40 | 显示全部楼层
感谢楼主无私奉献!
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2014-8-1 12:39:21 | 显示全部楼层
八皇后问题,想起当年学习往事,哎,不堪回首
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2014-8-3 17:50:20 | 显示全部楼层
确实是值得思考的一个问题!
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2014-8-3 21:40:50 | 显示全部楼层
呵呵  不错不错,。。。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

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

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-10-1 18:16

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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