N-Queen

문제 설명

가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다.

예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은 서로를 한번에 공격 할 수 없습니다.

 

체스판의 가로 세로의 세로의 길이 n이 매개변수로 주어질 때, n개의 퀸이 조건에 만족 하도록 배치할 수 있는 방법의 수를 return하는 solution함수를 완성해주세요.

제한사항

• 퀸(Queen)은 가로, 세로, 대각선으로 이동할 수 있습니다.
• n은 12이하의 자연수 입니다.

입출력 예

n	result
4	2

입출력 예 설명

입출력 예 #1
문제의 예시와 같습니다.

 

#코드

# n_queens
def check(i, col):
    global answer
    
    n = len(col) - 1     
    
    if promising(i, col):
        if i == n: # 답
            answer += 1
        else:
            for j in range(1, (n + 1)): # 열을 체크한다.
                col[i + 1] = j
                check(i + 1, col)
    
 
def promising(i, col):      
    k = 1    
    while k < i:
        # 열검사     : col[i] => Queen이 놓여있는 열
        # 대각선 검사 : 대각선 조건은 "열의 차이가 행의 차이와 같다." 이다.        
        #                    열의 차이               행의 차이
        #            |col[i] - col[k]| = |i - k|        
        if col[i] == col[k] or abs(col[i] - col[k]) == (i - k):
            return False
        k += 1    
    return True  
 
def solution(n):
    global answer    
    answer = 0
    
    col = [0] * (n + 1)
    check(0, col)
    
    return answer