C++浅谈八皇后问题中数据结构对算法的影响

#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;
//二维数组，用来存储皇后位置
int nums[9][9]= {0};
//记数
int total=0;
int show() {
 total++;
 for(int i=1; i<9; i++) 
  for(int j=1; j<9; j++) 
   if( nums[i][j]!=0 ) 
    cout<<"("<<i<<","<<j<<")"<<nums[i][j] <<"\t";
 cout<<"\n-----------------"<<endl;
}
/*
*判断位置是否符合要求
*/
bool isExist(int row,int col) {
 for(int i=1; i<9; i++) {
  for(int j=1; j<9; j++) {
   //同一行
   if(i==row && nums[i][j]!=0)return false;
   //同一列
   if(j==col && nums[i][j]!=0)return false;
   //对角线一
   if( (row+col)==(i+j) &&  nums[i][j]!=0 )return false;
   // 对角钱二
   if ( row>=col  && (row-col)==(i-j)   &&    nums[i][j]!=0 )return false;
   if ( row<col  && (col-row)==(j-i)   &&   nums[i][j]!=0  )return false;
  }
 }
 return true;
}
/*
*按行扫描遍历二维数组
*
*/
void search(int row) {
 for(int col=1; col<=8; col++) {
  if( isExist(row,col) ) {
   //如果位置可用
   nums[row][col]=col;
   if(row==8) show();
             else search(row+1);
   nums[row][col]=0;  
  }
 }
}
int main(int argc, char** argv) {
 search(1);
 cout<<"\共有"<<total<<"种摆放方案！";
 return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int  CELLS =9;
//存储结果
int res[CELLS];
void init() {
 memset(res,sizeof(res),0);
}
/*
*一维数组中的结果映射到二维平面上
*/
void showRes() {
 //填充皇后位置用 1 表示，没有填充位置用 0
 for(int r=1; r<CELLS; r++) {
  for( int c=1;c<CELLS; c++ ) {
   if(  res[c]==r  )cout<<"1\t";
   else cout<<"0\t";
  }
  cout<<endl;
 }
}

//检查该列位置放置皇后是否合法
int validate(int col,int row) {
 for (int i=1; i<col; i++) {
  if (row==res[i] || abs(row-res[i])==(col-i))
   return 0;
 }
 return  1;
}

void dfs(int col) {
 //可选择的位置
 for( int r=1; r<CELLS; r++) {
  if( validate(col,r) ) {
   res[col]=r;
   if( col==CELLS-1 ) {
    //最后一列
    showRes();
    cnt++;
    cout<<"----------------"<<endl;
   } else {
    dfs(col+1);
    res[col]=0;
   }
  }
 }
}

int main() {
 init();
 dfs(1);
 cout<<cnt<<endl;
 return 0;
}

#include <bits/stdc++.h>
using namespace std;
//一维数组模拟二维数组
int nums[64]= {0};
//计数器
int total=0;
//初始化
void init() {
 for(int i=0; i<64; i++) {
        //因为 0 是合法位置
  nums[i]=-1;
 }
}
//输出结果
int show() {
 total++;
 for(int i=0; i<64; i++) {
         //一维坐标转换成二维坐标
  int r=i/8;
  int c=i%8;
         //如果存储有位置信息
  if( nums[i]!=-1  )cout<<"("<<r<<","<<c<<")"<<nums[ i ] <<"\t";
 }
 cout<<"\n-------------------"<<endl;
}

//检查该列位置放置皇后是否合法
int isExist(int row,int col) {
 for (int i=0; i<row*8+col; i++) {
         //一维坐标转换为二维坐标
  int r=i/8;
  int c=i%8;
  int d=abs(row-r)-abs(col-c);
        //如盯存储有皇后位置信息
  if( nums[i]!=-1) {
             //是否和即将放置的位置相冲突
   if( r==row  || c==col || d==0 )
    return 0;
  }
 }
 return  1;
}

/*
*按行扫描
*/
void search(int row) {
     //每行可有的选择
 for(int col=0; col<8; col++) {
  if( isExist(row,col) ) {
   //如果位置可用
   nums[row*8+col]=col;
   if(row==7) show();
   else search(row+1);
   nums[row*8+col]=-1;
  }
 }
}

int main(int argc, char** argv) {
 init();
 search(0);
 cout<<"\共有"<<total<<"种摆放方案！";
 return 0;
}