N-Queens

2020-04-27

간단하지만 재귀의 핵심개념이라 할 수 있는 N-Queens(백트래킹)에 대해서 설명합니다.

백트래킹

백트래킹은 모든 경우의 수를 검색하는 것보다,

특정조건을 만족하는 모든 경우의 수를 찾을 때 사용하기에 유용한 알고리즘입니다.

N-Queens 은 백트래킹을 설명하기 가장 좋은 문제입니다.

N-Queens Problem

체스의 퀸은 가로방향,세로방향,대각선방향으로 이동할 수 있다.
이때, N*N크기의 체스판이 있다고 할때 N개의 퀸을 서로 잡아먹지 못하게 배치하는 방법을 찾아라.

N-Queen Problem이 위반되지 않는 조건은 아래와 같다.

  • 한 행에 퀸이 두개 놓일 수 없다.

  • 한 열에 있지 않아야 한다. (b != d)

  • 한 행에 있지 않아야 한다. (a != c)

  • 대각선에 있지 않아야 한다 ( a-c !- [b-d])

java

public class NQueenProblem {

    private int N = 4;
    private int cols[] = new int [4];
    
    public static void main(String [] args) {
        NQueenProblem solution = new NQueenProblem();
        solution.backTracking(0);
    }
    public void backTracking(int row) {

        if(row == N) {
            for(int i = 0; i < N; i++) {
                System.out.println(cols[i]);
            }
            System.out.println("");
        }
        else {
            for(int i = 0; i < N; i++) {
                cols[row] = i;
                if(isPossible(row)) backTracking(row+1);
            }
        }
    }
    public boolean isPossible(int row) {
    
        for(int i = 0; i < row; i++) {
            if(cols[i] == cols[row] || Math.abs(row-i) == Math.abs(cols[row]-cols[i])) {
                return false;
            }
        }
        return true;
    }   
}

참고자료 : https://bumbums.tistory.com/3