[Algorithm] - N Queens - Recursion

N Queens라는 알고리즘 문제는 N*N 정사각형 배열에 N개의 말을 놓는데,

놓는 방법은 인접한 대각선이나, 같은열이 하나라도 있으면 안된다는 것이다.

Backtracking 방식이라고 하며, 깊이우선탐색 개념이 된다고 한다.

Recursion과 Stack을 이용해서 풀 수 있는데 이번엔 Recursion으로 풀어보았다.

package recursive;

import java.util.Scanner;

public class Queens {

//말을 4개로 가정

static int Horse;

static int[] cols;

public static void main(String[] args){

Scanner in = new Scanner(System.in);

int N = in.nextInt();

Horse = N;

cols = new int[Horse+1];

//정사각형을 전제로.

queens(0);

}

static boolean queens(int level){

//말이 놓일수 없으면 false

if(!promising(level)) return false;

else if(level == Horse){ //말수와 레벨이 같다면 다 놓은 것.

for(int i=1; i<=Horse; i++) System.out.print(cols[i] + " ");

return true;

}

//재귀 호출

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

cols[level+1] = i;

if(queens(level+1)) return true;

}

return false;

}

//말이 놓일수 있는지 체크

static boolean promising(int level){

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

//같은 열이면 false

if(cols[i] == cols[level]) return false;

//인접한 대각선이면 false : 레벨차이도 1, 절대값 차이도 1 이면 인접한 대각선

else if(level-i == Math.abs(cols[level] - cols[i])) return false;

}

return true;

}

}