[Algorithm]백트래킹 - 2. 연습(N-퀸 문제)

N-퀸 문제

• N-퀸 문제는 NxN의 크기 체스판에 서로 공격하지 못하게 퀸을 최대한 많이 놓을 수 있는 자리를 탐색하는 문제 이다.
• 퀸의 경로는 직선과 대각선으로 움직일 수 있다.

• 첫번째 row[0], column[0] 에 퀸을 두면 row[0]은 더이상 퀸을 두지 못하고 row[1]에 퀸을 두어야 한다.

• row[1]에서도 row[1]의 column[0] 과 column[1]은 각각 직선방향 대각선 방향으로 퀸이 공격할 수 있기 때문에 다른퀸을 두지 못하고 column[2], column[3]에 퀸을 둘수 있다. column[3]에 퀸을 먼저 두어도 되지만 순서상 column[2]에 먼저 퀸을 두고 다음 row로 넘어 간다. 이후 문제가 발생할 시에 백트래킹으로 돌아와 column[3]에 퀸을 두면 된다.

• 두번째퀸을 row[1]의 column[2]에 두게 되면 row[2]에 세번째 세번째 퀸을 둘 수 없다. 원리상 4x4이상의 체스판에서는 각 row 마다 퀸 하나씩을 둘 수있는데 row[2]에 퀸을 둘 수 없다면 이전에 놓여있던 퀸의 자리가 잘못된 것이다. 여기서 백트래킹이 발생한다.

• 백트래킹 해서 row[1]의 퀸 자리를 column[2]에서 column[3]으로 이동 후 다시 탐색을 진행한다. 

• 백트래킹 해서 row[2]의 column[1] 자리에 퀸을 두게 되면 row[3]에 퀸을 둘 수 없으므로 또다시 백트래킹이 발생한다.

• 백트래킹 해서 row[2]로 돌아와도 더이상 둘곳이 없으므로 또 다시 백트래킹이 발생해 row[1]로 돌아간다.

• row[1]도 더이상 둘곳이 없으므로 백트래킹 되어 row[0]으로 돌아가 row[0]의 column[0]에 있는 퀸을 row[0]의 column[1]로 퀸을 옮긴다.

• 이런식으로 계속 반복하다 보면 아래 그림 처럼 4x4 체스판에 각 row 마다 하나씩 퀸을 둘 수 있게 되고 각 퀸들은 다른 퀸들을 공격할 수 없다.

< 최종 결과 >

소스(Java)

import java.util.*;

class Solution {

    int[] pieces;
    int n = 0; // 체스판 크기

    public void solution(int n) {
        this.n = n;
        this.pieces = new int[n]; // 체스말의 위치
        Arrays.fill(this.pieces, -1); // 체스말의 위치를 -1로 초기화
        play(0); // row 0부터 시작

        System.out.println(Arrays.toString(this.pieces));
    }

    public boolean play(int row) {
        if(this.n == row) { // 모든 row가 다 채워 졌으면
            return true; // true 리턴
        }
        for(int c = 0; c < this.n; c++) { // 해당 row의 모든 column을 조회
            if(canPlay(row, c)) { // 체스말을 둘수있는 자리인지 확인
                pieces[row] = c; // 체스말을 둘수 있으면 체스말의 자리 저장
                if (play(row+1)) { // 다음 row의 말의 자리 찾으러 GO
                    return true; // 모든 row가 다 채워 졌으면 더 진행하지 않고 return
                }
                // 모든 row가 채워지지 않았다면 체스말의 자리 초기화 후 다음 column 조회
                pieces[row] = -1;
            }
        }
        // for문이 다 돌때까지 말 자리를 못찾았다면 이전 row로 돌아가 말 위치 재선정(백트래킹)
        return false;
    }

    public boolean canPlay(int row, int column) {
        // 0~ 현재 row 까지 반복 pieceRow는 이미 저장 되어있는 말의 row
        for(int pieceRow = 0; pieceRow < row; pieceRow++) {
            int pieceColumn = this.pieces[pieceRow]; // 저장 되어있는 말의 Column
            if(pieceColumn == column) { // 저장 되어있는 말의 Column과 현재 Column의 값이 같으면
                return false; // 말을 놓지 못함.
            }
            // (현재 컬럼) - (저장된 말의 컬럼)의 절대값과 (현재 로우) - (저장된 말의 로우)의 절대값이 같으면 대각선임.
            if(Math.abs(column - pieceColumn) == Math.abs(pieceRow - row)) {
                return false; // 대각선에는 말을 놓지 못함.
            }
        }

        return true; // 저장된 모든 말과 같은 컬럼도 아니고 대각선에 위치 하지 않았으면 말을 놓을 수 있음.
    }


    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.solution(4);
    }

}