深度优先搜索算法C++实现

用C++编写的利用有界深度优先搜索算法解决8数码问题

// DNF_Search.cpp : Defines the entry point for the console application.
//

#include  
#include “iostream.h“
#include “stdio.h“
#include “stdlib.h“
#include “time.h“
#include “string.h“
#include 
#include 
using namespace std;

const int N = 3;//3*3图
enum Direction{NoneUpDownLeftRight};//方向

struct Map//图
{
    int cell[N][N];//数码数组
    Direction BelockDirec;//所屏蔽方向
    int step;
    struct Map * Parent;//父节点
};

//打印图
void PrintMap（struct Map *map）
{
    cout<<“*************************************************“<    for（int i=0;i    {
        for（int j=0;j        {
          cout<cell[i][j]<<“   “;
        }
        cout<    }
 cout<<“*************************************************“<}
//移动图
struct Map * MoveMap（struct Map * mapDirection Directbool CreateNewMap）
{
    struct Map * NewMap;

    //获取空闲格位置
    int ij;
    for（i = 0; i < N; i++）
    {
        bool HasGetBlankCell = false;
        for（j = 0; j < N; j++）
        {
            if（map->cell[i][j] == 0）
            {
                HasGetBlankCell = true;
                break;
            }
        }
        if（HasGetBlankCell）
            break;
    }
    //移动数字
    int t_i = it_j = j;
    bool AbleMove = true;
    switch（Direct）//判断沿direct所指方向移动数字是否被允许
    {
    case Down:
        t_i++;
        if（t_i >= N）
            AbleMove=false;
        break;
    case Up:
        t_i--;
        if（t_i < 0）
            AbleMove=false;
        break;
    case Left:
        t_j--;
        if（t_j < 0）
            AbleMove=false;
        break;
    case Right:
        t_j++;
        if（t_j >= N）
            AbleMove=false;
        break;
    };

    if（!AbleMove）//不可以移动则返回原节点
    {
        return map;
    }

    if（CreateNewMap）
    {
        NewMap = new Map（）;
        for（int x = 0; x < N; x++）
            for（int y = 0; y < N; y++）
                NewMap->cell[x][y] = map->cell[x][y];
    }
    else NewMap = map;
    NewMap->cell[i][j] = NewMap->cell[t_i][t_j];
    NewMap->cell[t_i][t_j] = 0;

    return NewMap;
}

//初始化一个初始图
//由目标图生成初始图，保证可以获得结果
struct Map * RandomMap（const struct Map * map）
{
    int M = 30;//随机移动图步数
    struct Map * NewMap;
    NewMap = new Map（）;
    memcpy（NewMapmapsizeof（Map））; 
    srand（（unsigned）time（NULL））;
    for（int i = 0; i < M; i++）
    {    
        int Direct = rand（）%4;
        NewMap = MoveMap（NewMap（Direction）Directfalse）;
    }
    return NewMap;
}
//初始图的另种生成方式，随机生成各位置的数
//此方式生成的图在有限次搜索中若深度超过5则多数无解
struct Map * RandomMap（）
{
 int a[9];
 struct Map * NewMap;
    NewMap = new Map（）;
 srand（（unsigned）time（NULL））;
 for（int k = 0; k < 9; k++）
    {  
  bool Isre = false;
  a[k] = rand（）%9;
  for （int l = 0; l < k; l++）
  {
   if （a[k] == a[l]）
   { 
    Isre = true;
    break;
   }
  }
  if（Isre）
  {
   k = k - 1;
   continue;
  }
 }
    

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件       4243  2009-05-04 23:41  DFS\DFS.dsp

     文件        531  2009-05-04 17:09  DFS\DFS.dsw

     文件      41984  2009-05-11 22:14  DFS\DFS.ncb

     文件      53760  2009-05-11 22:14  DFS\DFS.opt

     文件       1242  2009-05-11 22:13  DFS\DFS.plg

     文件       6251  2009-05-11 22:13  DFS\dfs8.cpp

     文件         33  2009-05-23 22:59  DFS\Readme.txt

     目录          0  2009-05-24 10:40  DFS

----------- ---------  ---------- -----  ----

               108044                    8