dfs 알고리즘 : NQueen

package N_Queen;

import java.util.Scanner;

public class source {

static int n;

static int arr[][] = new int[15][15];

static boolean chk[] = new boolean[15];

public static void main(String[] args){

Scanner sc = new Scanner(System.in);

n = sc.nextInt();

System.out.println(back(1));

}

static int back(int k){

if (k==n+1) return 1;

int total=0;

for (int i=1;i<=n; i++){

if(chk[i]) continue;

boolean impossible = false;

for(int j=1; j<k; j++){

if (i-j>0 && arr[k-j][i-j]==1) impossible = true;

if (i+j<=n && arr[k-j][i+j]==1) impossible = true;

}

if(impossible) continue;

arr[k][i] = 1;

chk[i] = true;

total += back(k+1);

arr[k][i] = 0;

chk[i] = false;

}

return total;

}

}