n人のクイーン

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

//----------------------------------------------------------------
#define N 20
#define LR(x,y) (x-y+N-1) 
#define RL(x,y) (x+y)
char board[N][N];
int lr[2*N-1];
int rl[2*N-1];
int h[N];
int count;
int n;

//----------------------------------------------------------------

/*void show(){
 int x, y;
 for(y= 0; y!=N; y++){
   for(x= 0; x!=N; x++){
     printf("%c",board[x][y]);
   }
   printf("\n");
 }
 printf("\n");
}
*/

//----------------------------------------------------------------
void solve(int x){
 int y;            //行
 if( x==n ){           //全列配置し終わったら
   count++; //show();  //カウントひとつ増やす
   return;             //ループを抜ける
 }
 for(y= 0; y!=n; y++){     //全行終わるまで
 
   if( !h[y] && !lr[LR(x,y)] && !rl[RL(x,y)] ){
     h[y]= lr[LR(x,y)]= rl[RL(x,y)]= 1;    //配置判定済
     board[x][y]= 'Q';     //王妃を配置
     solve(x+1);           //再帰的に次の列を判定
     
     board[x][y]= '.';     //盤面の初期化
     h[y]= lr[LR(x,y)]= rl[RL(x,y)]= 0;    //配置判定初期化
   }
 }
}


//----------------------------------------------------------------
int main(int argc, char *argv[]){
 
 int x, y;
 n= atoi(argv[1]);     //コマンドラインより数値を取得
 
 for(y= 0; y!=n; y++){     //盤面の初期化
   h[y]= 0;                //行未配置設定
   for(x= 0; x!=n; x++){   //列初期化
     board[x][y]= '.';     //未配置
     lr[LR(x,y)]= 0;       //斜めライン配置判定初期化
     rl[RL(x,y)]= 0;       //斜めライン配置判定初期化
   }
 }
 count= 0;         //カウンタ初期化
 solve(0);         //関数solveて配置判定
 
 printf("%d\n", count);        //結果出力

 return 0;
} 

メモ--------------------------------------------------------------------
左斜めライン #define LR(x,y) (x-y+N-1)
右斜めライン #define RL(x,y) (x+y)
盤面　char board[N][N];
左斜めラインの判定配列　int lr[2*N-1];
右斜めラインの判定配列　int rl[2*N-1];
王妃配置済み　int h[N];
int count;

-----------------------------------------------------------------------
プログラム説明
-----------------------------------------------------------------------
関数solve
-----------------------------------------------------------------------
王妃の配置判定
各行列、左右の対角線上には一つの王妃しか置けない
if( !h[y] && !lr[LR(x,y)] && !rl[RL(x,y)] ){
h[y]= lr[LR(x,y)]= rl[RL(x,y)]= 1; //配置判定済
board[x][y]= 'Q'; //王妃を配置
solve(x+1); //再帰的に次の列を判定
行に対して配置判定し、配置済みであれば列を次に移すことで組み合わせの処理を省く
再帰的に次の列を判定していき、
処理から返ってきた時点で盤面と判定配列を初期化して次の組み合わせを調べる
全列配置し終わったらカウントしてループを抜ける

-----------------------------------------------------------------------
main
-----------------------------------------------------------------------
コマンドラインより数値を取得
盤面配列の初期化と配置済み判定配列の初期化
カウントを初期化
関数solveで配置判定