백준 백트래킹 - 9663번 : N-Queen

https://www.acmicpc.net/problem/9663

9663번: N-Queen

---

import java.io.*;
import java.util.*;
public class Main {
	
	public static void main(String[] args) throws IOException{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int[][] a = new int[n][n];
		br.close();
		int cnt = 0;
		for(int i=0; i<n; i++) {
			cnt+=nqueen(0,i,a);
		}
		bw.write(cnt+" ");
		bw.close();
	}
	public static int nqueen(int i, int j, int[][] board) {
		if(board[i][j]==-1) return 0;
		if(i==board.length-1&&board[i][j]==0) {return 1;}
		board[i][j] = -1;
		int cnt = 0;
		for(int k = 0; k<board.length; k++) {
	         if(check(i+1,k,board))cnt+=nqueen(i+1,k,board);
		}
		board[i][j] = 0;
		return cnt;
	}
	public static boolean check(int i, int j, int[][] board) {
		for(int k = 0; k<board.length; k++) {
			if(board[k][j]==-1) return false;
			else if(board[i][k]==-1) return false;
		}
		int k = i; int l = j;
		while(k<board.length&&l<board.length) {
			if(board[k++][l++] == -1) return false;
		}
		k = i; l = j;
		while(k>=0&&l>=0) {
			if(board[k--][l--] == -1) return false;
		}
		k = i; l = j;
		while(k<board.length&&l>=0) {
			if(board[k++][l--] == -1) return false;
		}
		k = i; l = j;
		while(k>=0&&l<board.length) {
			if(board[k--][l++] ==-1) return false;
		}
		return true;
	}
}