回溯法总结

一 简介

回溯法是一种非常常用的算法：在一个解空间中寻找一个满足限制条件的解，则继续寻找下一个，如果找不到，则抹去该解，回溯上一个，基本思路是：

1. 非递归版

while(可行解范围内)
    {
     if(一个可行解产生了)  打印出来;
     for(寻找可行解的解空间)
        if(满足可行解的限制条件)
            加入可行解空间
     if(是否已经找到一个可行解)
        继续寻找下一个
     else     抹去该可行解,回溯到上一个
    }

2.递归版

function (int k)
    {
    if(一个可行解产生了) 打印出来;
    寻找满足该k层的解;
        if(找到了k层的可行解)
         寻找下一层,function(k++);
     else 回溯到上一层，抹去该k层的痕迹，function(k--);
    }

二 n皇后问题

一个n*n矩阵中放置n颗棋子，要求每个棋子之间必须不能同一行列，正对角线，斜对角线放置。

1.非递归版

/*
* n 皇后问题：
* 棋盘中不能横 竖 斜着放置
*/

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

#define N num
//检查行 列 横竖对角线是否合法
static int num;//记录皇后的阶数
int x[20];//记录每一列的数据

int isPlace(const int row,const int col)
{
    int i;
    for(i=0;i<row;i++)
        if((x[i]==col)||(x[i]-i==col-row)||(x[i]+i==col+row))
            return 0;
    return 1;
}

void nQueue()
{
   int k=0,i;
   while(k>=0)
   {
    if(k==N)
    {
    for(i=0;i<N;i++)
    printf(" %d ",x[i]);
     printf("\n");
     k=N-1;
    }
    for(i=x[k]+1;i<N;i++)
    if(isPlace(k,i))
    {
      x[k]=i;
      k++;
      break;
    }
    if(i==N)
    {
        x[k]=-1;//抹去上次的痕迹
     k--;
    }
   }
}

void main(int argc,char*args[])
{
    int i;
    if(argc!=2)
    {
    fprintf(stderr,"usage:%s num!\n",args[0]);
    exit(-1);
    }
    num=atoi(args[1]);
    for(i=0;i<N;i++)
        x[i]=-1;
    nQueue();
    printf("It's over!\n");
}

2.递归版

/*
*n皇后问题递归实现
*/
#include <stdio.h>
#include <stdlib.h>

#define N num

static int num;//记录皇后的阶数
int x[20];//记录每一列的数据

int isPlace(int row,int col)
{
    int i;
    for(i=0;i<row;i++)
    if(x[i]==col||(x[i]-i==col-row)||(x[i]+i==col+row))
        return 0;
    return 1;
}

void nQueue(int k)
{
    int i;
    if(k==N)
    {
     for(i=0;i<N;i++)
      printf(" %d ",x[i]);
     printf("\n");
     k=N-1;
    }
    for(i=x[k]+1;i<N;i++)
    if(isPlace(k,i))
    {
      x[k]=i;
      k++;
      break;
    }
    if(i==N)
    {
    x[k]=-1;
    k--;
    }
    if(0==k&&x[k]==N-1)
    {
      printf("It's over!\n");
      return;
    }
    nQueue(k);
}
void main(int argc,char* args[])
{
    int i;
    if(argc!=2)
    {
    fprintf(stderr,"usage:%s num!\n",args[0]);
    exit(-1);
    }
    num=atoi(args[1]);
    for(i=0;i<N;i++) x[i]=-1;
    nQueue(0);
}