[프로그래머스] N-Queen python

N-Queen

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

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

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

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

n = 4일때, 예시를 만족하는 리스트를 [2, 0, 3, 1]처럼 1차원으로 표현한다. 각각이 의미하는 숫자는 board[0][2], board[1,1] .. 으로 0번째 cloumn에는 2번째 row에 퀸이 존재한다는 표현이다.

1. DFS를 이용해서 모든 경우를 탐색한다.
2. col을 돌면서 모든 row에 대해서 검사한다.
3. 모든 row를 돌면서 조건을 만족하고 마지막까지 도달하면 카운트에 1을 더 하도록 반환한다.

def dfs(queen, row, n):
    count = 0
    if n == row:
        return 1
    for col in range(n):
        queen[row] = col
        for i in range(row):
            if queen[i] == queen[row]:
                break
            if abs(queen[i]-queen[row]) == row - i:
                break
        else:
            count += dfs(queen, row + 1, n)
    return count
def solution(n):
    return dfs([0]*n, 0, n)