ehh.cpp

八皇后经典问题.C++实现,非可视化.

#include <iostream>

 #define stepMax 8

 int m,n;

 int i,j,count=0;

 int iArray[20][20]={0};

 

void IFUN(int a,int b)

 {//列冲突 

 for(i=a;i<stepMax;i++) iArray[i][b]+=1;

 for(i=a;i>=0;i--) iArray[i][b]+=1;

 //行冲突 

 for(j=b;j<stepMax;j++) iArray[a][j]+=1;

 for(j=b;j>=0;j--) iArray[a][j]+=1;

 //反对角线冲突 

for(i=a,j=b;(i<stepMax)&&(j>=0);i++,j--) iArray[i][j]+=1;

 for(i=a,j=b;(i>=0)&&(j<stepMax);i--,j++) iArray[i][j]+=1;

 //对角线冲突 

 for(i=a,j=b;(i<stepMax)&&(j<stepMax);i++,j++) iArray[i][j]+=1;

 for(i=a,j=b;(i>=0)&&(j>=0);i--,j--) iArray[i][j]+=1;

  }

void DFUN(int a,int b)

{

//列冲突取消 

 for(i=a;i<stepMax;i++) iArray[i][b]-=1;

 for(i=a;i>=0;i--) iArray[i][b]-=1;

 //行冲突 取消 

 for(j=b;j<stepMax;j++) iArray[a][j]-=1;

 for(j=b;j>=0;j--) iArray[a][j]-=1;

 //反对角线冲突取消 

for(i=a,j=b;(i<stepMax)&&(j>=0);i++,j--) iArray[i][j]-=1;

 for(i=a,j=b;(i>=0)&&(j<stepMax);i--,j++) iArray[i][j]-=1;

 //对角线冲突 取消 

 for(i=a,j=b;(i<stepMax)&&(j<stepMax);i++,j++) iArray[i][j]-=1;

 for(i=a,j=b;(i>=0)&&(j>=0);i--,j--) iArray[i][j]-=1;

} 

void  printQueens()

{

 for(i=0;i<stepMax;i++)

 {for(j=0;j<stepMax;j++)

 if(iArray[i][j]<20)

printf("   *");

 else printf("   Q");

 printf("\n");}

 printf("\n"); 

}

int tryThisStep(int lev,int k)

{ if(iArray[lev][k]==0)//当该位置为0的话 

{ IFUN(lev,k);                  //在lev行,k列处放置皇后的冲突

    iArray[lev][k]=999;             //在lev行,k列处放置皇后

return 1;

}

return 0;

}

int canDoThisStep(int lev)

{

    for(j=0;j<stepMax;j++)

    {if(iArray[lev+1][j]==0)    //如果下一步中有一个空格，说明这个可以放 

       return 1;

    } 

    return 0;                //能执行到这步，说明下一步中没有空格。 

}

void OutStackDoSomeThing(int lev,int k)

{

DFUN(lev,k);          //把原来放皇后后冲突的位还原 

iArray[lev][k]=0;    //把原来放皇后的位置还原 

}

 

void TryPutQueens(int level) { //level是指放置皇后的计数，如果这次需要放第3行了，

                       //那么此时level==3(注：我这里假设level范围是1~8)

 

    if (level == stepMax) {

        //已经放了8个皇后了，任务完成了，打印吧！

          printQueens();  //<--这是输出结果的过程。

        count++;        //共有几种方法计数.

        return ;

    }

    else //如果没有放到第8个的话，就继续放，level <=8 都要执行这个

        for (int w=0; w<stepMax;w++) {  //stepMax指的是试探方法(能够尝试放置的方法)，比如本

                                     //题中第level皇后总有8种放法——从第一列到第八列。

                                     //因此，此时的stepMax=8

         if(! tryThisStep(level,w)) continue; //<---尝试第i种试探方法

         if (canDoThisStep(level))  //<---- 就是说不会造成皇后间的攻击，可以放

                TryPutQueens(level+1);    //<---第N个皇后如果可以放置，就可以尝试放第N+1个皇后

 OutStackDoSomeThing(level,w);   //比如你说的拿掉一个Queens后，要把其他位置减1。

        }

};

 void main()

 {

 TryPutQueens(0);           ////从第0行开始放。

 printf("%3d",count);

 return; }