[BackTracking] 백준 NQueen 9663 python3 풀이

https://www.acmicpc.net/problem/9663

문제

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

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

입력

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

출력

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

예제 입력 1

8

예제 출력 1

92

 

def nqueens(tmp_store, curPos, cycleCount, stack):
    global totalCount
    tmp_store[curPos] = 1 
    cycleCount = cycleCount + 1
    stack.append((curPos, cycleCount-1))
    
    for j in range(0, N):
        if (valid(tmp_store, j, cycleCount, stack)):
            nqueens(tmp_store, j, cycleCount, stack)  
    
    if (cycleCount == N):
        totalCount = totalCount + 1
    
    tmp_store[curPos] = 0
    stack.pop()

def valid(tmp_store, x, y, stack):
    if (tmp_store[x] == 0 and checkNorthWest(stack, x, y) and checkNorthEast(stack, x, y)): return True
    else: return False
    
def checkNorthWest(stack, x, y):
    while (True):
        x = x - 1
        y = y - 1 
        if (x >= 0 and y >= 0):
            if (stack[y] == (x,y)):
                return False
        else: break
    return True
    
def checkNorthEast(stack, x, y):
    while (True):
        x = x + 1
        y = y - 1 
        if (x < N and y >= 0):
            if (stack[y] == (x,y)):
                return False
        else: break
    return True

N = int(input())
totalCount = 0 
for i in range(0, N):
    nqueens([0 for j in range(0, N)], i, 0, [])
print(totalCount)