[WEEK01] 백준 9663 N-Queen

문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N < 15)

출력

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

풀이

첫번째 행부터 아래로 내려가면서 둘것이다.
위에서 아래로 진행할 것이기 때문에 공격여부는 위쪽에 한해서만 검사하면 된다.

• 첫번째 행부터 일단 놓고 시작
• 해당 행에서 첫번째 열부터 끝 열까지 놓을 수 있나 검사
• 놓는데 성공하면 다음 행 진행

전체코드

n = int(input())
pos = [-1] * n
count = 0

def put_able(i):
	for j in range(j):
    	if pos[i] == pos[j] or i-j == abs(pos[i]-pos[j]):
        	return False
    return True

def set(i):
	global count
    
    if i > n-1:
    	count += 1
    else:
    	for j in range(n):
        	pos[i] = j
            
            if put_able(i):
            	set(i+1)
                
set(0)
print(count)