nQueen - 백트래킹

 

def dfs(positions, row) :
    n = len(positions)
    if n == row:
        #끝까지 왔으므로 1
        return 1
    count = 0
    for col in range(n) :
        positions[row] = col
        if check(positions, row):
            count += dfs(positions, row + 1)
    return count


def check(pos, row) :
    for i in range(row):
        if pos[i] == pos[row] or (row-i == abs(pos[i] - pos[row])):
            return False
    return True

def solution(n):
    ans = [0] * n
    return dfs(ans, 0)
    
    
# 1~12까지
for i in range(1, 13):
    print(solution(i))

오랜만에 다시 풀어본 nQueen 문제. 처음 풀었을 때보다 check 하는 로직을 더 간단하게 짜봤다.