法一:按格搜索,暴力搜索每行每列
#include <iostream>
using namespace std;
const int N = 10 ;
bool row[N], col[N] ,dg[N*2] , udg[N*2] ; // 用于表示行、列、正对角线、反对角线上是否没有皇后
char g[N][N] ; // 棋盘
int n ;
/* 法一:每行每列依次搜索
* x,y表示坐标,s表示当前的皇后数*/
void dfs(int x , int y , int s){
if(y == n) y = 0 , x++ ; // 当前行已遍历完,遍历下一行
if(x == n ){ // 遍历已完成
if(s == n){ // 皇后数已满,该次遍历找到满足条件的方案
for(int i = 0 ; i < n ; i++) cout << g[i] << endl ;
cout << endl ;
}
return ;
}
/* 截距法:
* 正对角线:y = x + u => u = y - x , 保证非负,因此 u = y -x + n
* 反对角线:y = u - x => u = y + x */
if(!row[x] && !col[y] && !dg[y -x + n] && ! udg[y+x]){ // 当前位置上可放皇后
g[x][y] = 'Q' ;
row[x] = col[y] = dg[y - x + n] = udg[y + x] = true ;
dfs(x,y+1,s+1) ; // 遍历下一个点
/*恢复现场*/
g[x][y] = '.' ;
row[x] = col[y] = dg[y - x + n] = udg[y + x] = false ;
}
dfs(x,y+1,s) ; // 当前点不可以放皇后,遍历下一个点
}
int main(){
cin >> n ;
/*初始化棋盘*/
for(int i = 0 ; i < n ; i++)
for(int j = 0 ; j < n ; j++)
g[i][j] = '.' ;
dfs(0,0,0) ;
return 0 ;
}
法二:按行或者按列搜索
#include <iostream>
using namespace std;
const int N = 10 ;
bool col[N], dg[N*2] , udg[N*2] ;
int n ;
char g[N][N] ;
/*法二:每列上只会有一个皇后,每列上也只有一个皇后。因此可以按行搜或者按列搜*/
void dfs(int u){ // u表示皇后数
if(u == n){
for(int i = 0 ; i < n ; i++) cout << g[i] << endl ;
cout << endl ;
return ;
}
/*遍历每列*/
for(int i = 0 ; i < n ; i++){
/*这儿同理,u表示行,i表示列*/
if(!col[i] && !dg[u+i] && !udg[i-u + n]){
g[u][i] = 'Q';
col[i] = dg[u+i] = udg[i - u + n] = true ;
dfs(u+1) ; // 遍历下一行
/*恢复现场*/
g[u][i] = '.';
col[i] = dg[u+i] = udg[i - u + n] = false;
}
}
}
int main(){
cin >> n ;
for(int i = 0 ; i < n ; i++)
for(int j = 0 ; j < n ; j++)
g[i][j] = '.' ;
dfs(0) ;
return 0 ;
}