N-Queen

 

https://school.programmers.co.kr/learn/courses/30/lessons/12952

프로그래머스

 

 

다른 곳에서도 본 문제다. n*n 크기 체스판 위에 퀸 n 개를 서로 공격하지 못하게 배치하는 문제

일단 퀸 이 대각선과 수평수직 공격을 하니까 같은 줄 같은 열 같은 대각선에는 배치하지 못한다 이 조건을 써서 위에부터 한 마리씩 배치하면서 만약 불가능한 배치 면 다시 돌아가서 배치함 반복적으로 하니까 재귀 함수 사용하면 간단하다

모든 가능한 구역에서 위에 떨어져 있는 만큼 +- n을 해주면 대각선을 제거되고 본인의 위치를 제거하면 열까지 제거 가능 남은 구역만 계속 가다가 끝까지 도달하면 return

 

def solution(n):
    def f(p=[],m=0):
        s=0
        if m==n:return 1
        u=set(range(n))
        for k,i in enumerate(p):
            u-={i-(m-k),i+(m-k),i}
        for i in u :
            s+=f(p+[i],m+1)
        return s
    return f()