백트랙킹(N Queens)

N Queens 문제는 NxN 매트릭스에 N개의 queen을 서로 공격할 수 없는 위치에 놓는 모든 방법을 구하는 문제이다.

참고로 queen은 가로, 세로, 대각석으로 공격이 가능하다.

 

basic solution

매트리스 모든 위치를 decision space로 생각하고 백트래킹 적용한다. 단, 중복 확인을 피하기 위해 현재 decision space 는 이전 위치의 다음 위치부터로 하는 제한을 둔다.

 

queen은 각 행에 1개씩만 올 수 있다는 사실을 이용하여 1단계 더 최적화 가능하다.

 

queen의 위치 위반 규칙을 이용하여 1단계 더 최적화 가능하다.

hash set을 사용하여 칼럼과 대각선이 규칙을 위반하는지 체크가능하다. 로우는 위에서 한 작업 덕분에 체크하지 않아도 된다.

 

 

# Title : N-Queens problem
# Chapter : Backtracking
# 문제 : 주어진 n을 기반으로 n * n size의 matrix board가 만들어진다. 이 board에 n개의 Queen이 서로를 공격하지 못하는 상태를 모두 return 하여라
# 예제: n = 4
# 답: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]

from typing import List

class NQueens:
    def solve(self, n:int) -> List[List[str]]:
        self.__results = []
        self.__col_set = set() #column duplicates
        self.__diag_set1 = set() #row-col duplicates
        self.__diag_set2 = set() #row+col duplicates
        self.__n = n #length

        for x in range(n):
            self.__bt(0, x, [])

        return self.__results

    #python str is immutable
    def __create_str_row(self, col:int) ->str:
        str_list = ['.'] * self.__n
        str_list[col] = 'Q'
        return ''.join(str_list)


    def __bt(self, row:int, col:int, board:List[str]):
        #exit conditions
        if row == self.__n or col == self.__n:
            return
        if col in self.__col_set:
            return
        diag1_info = row - col
        diag2_info = row + col
        if diag1_info in self.__diag_set1:
            return
        if diag2_info in self.__diag_set2:
            return

        #process
        str_line = self.__create_str_row(col)
        board.append(str_line)

        if len(board) == self.__n:
            self.__results.append(board.copy())
            board.pop()
            return

        #duplicates sets
        self.__col_set.add(col)
        self.__diag_set1.add(diag1_info)
        self.__diag_set2.add(diag2_info)

        #recursive call
        for x in range(self.__n):
            self.__bt(row  +1, x, board)
        
        #dupcliates sets pop
        self.__col_set.remove(col)
        self.__diag_set1.remove(diag1_info)
        self.__diag_set2.remove(diag2_info)
        board.pop()
nQsolver = NQueens()
print(nQsolver.solve(6))

 

 

참조 : (3) 코딩테스트, 상급 , 여왕말, N Queens문제 - YouTube