论坛 › 数据结构与算法 › 八皇后问题与回溯法

spy 发表于 2015-3-27 17:27:21

八皇后问题与回溯法

本帖最后由 spy 于 2015-12-20 00:34 编辑

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <conio.h>

/* 此程序在vc6.0下编译运行是正确的，
    在vs2008上编译成功，但运行会出现stack overflow !
    高版本的编译器默认分配的的栈空间小一些，
    应该可以在编译器里设置默认分配的栈的大小的,
    如果不能设置的话可以将皇后个数减少。
*/

//NUM大于8时, 频繁的递归调用会造成栈空间溢出
#define NUM 8//8个皇后

void SolveQueen(char (*), int, int);
int NotSafety(char (*), int, int);
void MoveBack(char (*), int, int);
void ShowQueen(char (*));

int cnt = 0;
clock_t start, finish;

void main()
{
      char chess;
      int i, j;
      for(i=0; i<NUM; i++)//初始化棋盘
      {
                for(j=0; j<NUM; j++)
                {
                        chess = '0';
                }
      }
      start = clock();
      SolveQueen(chess, 0, 0);   //从(0,0)开始搜索
}

//NUM个皇后依次放置放到第0列到第NUM-1列的相应位置, 第j列上的皇后具体位置的确定需依次遍历第0行到第NUM-1行, 若第i行安全, 皇后位置chess(i,j)=1
void SolveQueen(char (*chess), int i, int j)
{
      while(i<NUM)
      {
                if( !NotSafety(chess, i, j) )//当前位置安全
                {
                        *(*(chess+i)+j) = '1';//置棋盘元素chess(i,j)=1
                        if(j==NUM-1)//找到一种方案
                        {
                              ShowQueen(chess);//将位置打印出来
                              chess = '0'; //清0, 准备搜索下一行
                        }
                        else
                        {
                              SolveQueen(chess, 0, j+1);//搜索下一列
                        }
                }
                i++;//当前行不安全, 向下移动一行
      }
      if(i==NUM)//当前列都不安全
      {
                MoveBack(chess, 0, j-1);//向前回溯一列
      }
}

//判断当前位置是否安全, 若不安全返回1, 否则返回0
int NotSafety(char (*chess), int i, int j)
{
      //判断同一行是否安全
      int m, n;
      m = j-1;
      if(m>=0) //←
      {
                while( m>=0 && chess!='1' );
                if(chess[++m]=='1')
                {
                        return 1;
                }
      }

      //判断主对角线是否安全
      //左上方
      m = i-1;//↑
      n = j-1;//←
      if(m>=0 && n>=0)
      {
                while(m>=0 && n>=0 && chess!='1');
                if(chess[++m][++n]=='1')
                {
                        return 1;
                }
      }

      //判断次对角线是否安全
      //左下方
      m = i+1;//↓
      n = j-1;//←
      if(m<NUM && n>=0)
      {
                while(m<NUM && n>=0 && chess!='1');
                if(chess[--m][++n]=='1')
                {
                        return 1;
                }
      }
      return 0;
}

//回溯至前一列, 继续对该列未搜索的行进行搜索
void MoveBack(char (*chess), int i, int j)
{
      while(chess!='1');//找到之前搜索的行
      chess[--i] = '0';//该行无效
      if(i==NUM-1 && j-1>=0)//若该列的所有行都无效, 则继续回溯前一列; j-1>=0 表示当前列j=0 时就不能再向前回溯了, 因为回溯至0-1=-1列无意义
      {
                MoveBack(chess, 0, j-1);
      }
      if(i==NUM-1 && j-1<0)//若回溯到chess(NUM-1,0)则所有解法已全部遍历结束, 终止程序运行
      {
                finish = clock();
                printf("\n%d皇后问题的解共有%d个!\n",NUM, cnt);
                printf("\n耗时%ldms\n", finish-start);
                _getch();
                exit(0);
      }
      SolveQueen(chess, i+1, j);//搜索下一行
}

void ShowQueen(char (*chess))
{
      int i, j;
      printf("\n第%d种方案 :", ++cnt);
      putchar('\n');
      for(i=0; i<NUM; i++)
      {
                for(j=0; j<NUM; j++)
                {
                        printf("%c ", *(*(chess+i)+j));
                }
                putchar('\n');
      }
}

robinshie 发表于 2015-3-27 21:09:28

{:1_1:}

Furk 发表于 2015-5-7 16:20:55

刚看完这个视频

vank 发表于 2015-5-26 01:39:17

感谢额 我看看学习学习

逆战时代 发表于 2015-5-26 21:48:54

看看。。。。。。。。。。。

vanentu 发表于 2015-5-27 03:04:28

LZ好人。。。。。。。。。

fuckyou 发表于 2015-6-9 17:07:44

lz好人

溯月0503 发表于 2015-6-13 10:26:07

好牛呀

逆战时代 发表于 2015-6-15 16:52:11

顶、、、、、、、、、

小学期 发表于 2015-6-17 18:02:32

sgoyi

秒速五厘米 发表于 2015-6-18 14:16:01

问一下，我用vs2013运行的时候为什么会出现10个错误啊？

溯月0503 发表于 2015-6-19 21:13:30

为什么运行会出现错误？？？？？？？？

秒速五厘米 发表于 2015-6-20 22:23:42

溯月0503 发表于 2015-6-19 21:13
为什么运行会出现错误？？？？？？？？

你运行的时候有没有错误呢？

溯月0503 发表于 2015-6-21 09:00:36

秒速五厘米 发表于 2015-6-20 22:23
你运行的时候有没有错误呢？

有呀   你运行了吗

秒速五厘米 发表于 2015-6-21 12:24:00

溯月0503 发表于 2015-6-21 09:00
有呀   你运行了吗

我的错误不是截图了吗？你没看到？

溯月0503 发表于 2015-6-22 09:59:10

秒速五厘米 发表于 2015-6-21 12:24
我的错误不是截图了吗？你没看到？

好吧   刚看到我也是   解决了嘛？？？？？？？？？？？

秒速五厘米 发表于 2015-6-23 12:07:50

菜鸟一个，解决不了！！！靠你了！

秒速五厘米 发表于 2015-6-23 12:08:21

溯月0503 发表于 2015-6-22 09:59
好吧   刚看到我也是   解决了嘛？？？？？？？？？？？

菜鸟一个，解决不了！！！靠你了！

溯月0503 发表于 2015-6-24 09:03:13

:sad

565335545 发表于 2015-6-24 09:45:20

溯月0503 发表于 2015-6-24 09:03


啥东西

查看完整版本: 八皇后问题与回溯法