[Java] N_Queens Algorithm 문제

N X N 체스판에 N개의 Queen들이 같은 열과 대각선에 위치하지 않도록 하는 좌표 출력

 

 
import java.io.IOException;
import java.util.Arrays;
import java.util.Scanner;

public class Nqueens {
	private static int[] cols;
	private static int n;
	private static int level;

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		// BufferedReader br = new BufferedReader(new
		// InputStreamReader(System.in));
		Scanner s = new Scanner(System.in);
		n = s.nextInt();
		level = 0;
		cols = new int[n + 1];
		queens(level);

		s.close();
	}

	public static boolean queens(int level) {
		if (!feasible(level)) {
			return false;
		} else if (level == n) {
			for (int i = 1; i <= n; i++) {
				System.out.println(i + " " + cols[i]);
			}
			return true;
		}

		for (int i = 1; i <= n; i++) {
			cols[level + 1] = i;
			if (queens(level + 1)) {
				return true;
			}
		}
		return false;
	}

	public static boolean feasible(int level) {
		for (int i = 1; i < level; i++) {
			if (cols[level] == cols[i]) {
				return false;
			} else if ((level - i) == Math.abs(cols[level] - cols[i])) {
				return false;
			}
		}
		return true;
	}

}