[백트래킹] N-Queen ☆☆☆

[조건]
- 행번호의 차이와 열번호의 차이가 같다면 대각선이다.
- 같은 행이나 열에 놓이면 안된다.

1.

col 배열

import java.util.Scanner;

public class NQueenTest {

	static int N, col[], answer;
	public static void main(String[] args) {
		
		Scanner sc=new Scanner(System.in);
		N=sc.nextInt();
		col=new int[N+1];
		
		setQueen(1);
		System.out.println(answer);
		

	}
	
	static void setQueen(int rowNo) { //rowNo: 놓으려고 하는 행의 번호
		if(!isAvailable(rowNo-1)) return; //유망성 체크, 가능한가
		
		if(rowNo > N ) {
			answer+=1;
			return;
		}
		//유도
		for(int c=1;c<=N;c++) {
			col[rowNo]=c;
			setQueen(rowNo+1);
			
		}
		
	}
	
	private static boolean isAvailable(int rowNo) {
		
		for(int k=1; k<rowNo; k++) { //k: 비교 대상 queen의 행 
			if(col[k] == col[rowNo] || Math.abs(col[k]-col[rowNo])== rowNo-k)//같은 열에 있거나, 대각선에 있으면
				return false;
		}
		
		return true;
	}

}

2.

import java.util.Scanner;

public class Main {

	static int N, answer;
	static boolean col[], cross1[], cross2[];
	
	public static void main(String[] args) {
		
		Scanner sc=new Scanner(System.in);
		
		int T=sc.nextInt();
		
		for(int i=1;i<=T;i++) {
			
			answer=0;
			N=sc.nextInt();
			col=new boolean[N+1];
			cross1=new boolean[N*2];
			cross2=new boolean[N*2];
			setQueen(1);
			System.out.println("#"+i+" "+answer);
		}
		
		

	}
	
	static void setQueen(int rowNo) { //rowNo: 놓으려고 하는 행의 번호
		
		if(rowNo > N ) {
			answer+=1;
			return;
		}
		
		for(int c=1;c<=N;c++) {
			
			if(!isAvailable(rowNo, c)) continue;
	
			col[c]=true;
			cross1[N+rowNo-c]=true;
			cross2[rowNo+c-1]=true;
			
			setQueen(rowNo+1);
			
			col[c]=false;
			cross1[N+rowNo-c]=false;
			cross2[rowNo+c-1]=false;
			
		}
	}
	
	private static boolean isAvailable(int rowNo, int i) {
			if(!col[i] && !cross1[N+rowNo-i] && !cross2[rowNo+i-1]) return true;
			return false;		
	}

}