8quees.cpp

八皇后c++实现

#include <stdio.h>
#include <string.h>
#include <vector>
using namespace std;
bool rows[8], diag[16],diag2[16];
int result[8],total;

// 將 (r,c) 放置一個皇后
void select (int r,int c,int cnt){
 rows[r]=true;
 result[cnt]=r;
 diag[r+c]=true;
 diag2[r-c+9]=true;
}

// 取消(r,c) 放置的皇后
void unselect (int r,int c){
 rows[r]=false;
 diag[r+c]=false;
 diag2[r-c+9]=false;
}

// 判断(row,col) 是否可以合法放置皇后
bool valid(int row,int col){
 return !(rows[row]||diag[row+col]||diag2[row-col+9]);
}

// 搜寻第 col行(column)，找出合法的列rows
void dfs(int col,int cnt){
 if(cnt==8){
  printf("%2d      ",total+1);

  for(int i=0;i<8;i++)
   		printf("%d ",result[i]+1);
   printf("\n");

   total++;
 } else
 for(int i=0;i<8;i++)
   if(valid(i,col) ){
    select(i,col,cnt);
    dfs(col+1,cnt+1);
    unselect(i,col);
   }
}

void init(){
  total=0;
  memset(diag,0,sizeof(bool)*16);
  memset(diag2,0,sizeof(bool)*16);
  memset(rows,0,sizeof(bool)*8);
}

int main(int argc,char **argv){
	init();
	printf("解       COLUMN\n");
	printf(" #      1 2 3 4 5 6 7 8\n\n");
	dfs(0,0);
	scanf(" ");
	return 0;

}