백준 9663번 N-Queen 파이썬

nqueen 가지고 몇번을 시도 했는데 이렇게 직접 구현해 맞춘건 처음이여서 기쁘다.

 

---

문제

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

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

입력

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

출력

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

예제 입력 1

8

예제 출력 1

92

n = 01, solution count is 1.
n = 02, solution count is 0.
n = 03, solution count is 0.
n = 04, solution count is 2.
n = 05, solution count is 10.
n = 06, solution count is 4.
n = 07, solution count is 40.
n = 08, solution count is 92.
n = 09, solution count is 352.
n = 10, solution count is 724.
n = 11, solution count is 2680.
n = 12, solution count is 14200.
n = 13, solution count is 73712.

n = int(input())
maps = [[0] *n for i in range(n) ]

answer = 0
def fire(maps, history_column, mother,diff,plus):
    moves=[[1,0],[1,1],[1,-1]]
    if mother[0] == len(maps)-1:
        global answer
        answer+=1
        return
    for i in range(len(maps)): # column 만 볼거야
        if i in history_column:
            continue         
        else:
            new_mom = [mother[0]+1, i]
            # 1차원 diff 로 생각.
            if  new_mom[0]-new_mom[1] in diff:
                continue
            elif new_mom[0]+new_mom[1] in plus:
                continue
            
            # 조건에 부합함
            new_history_column = history_column[:]
            new_history_column.append(i)
            new_diff = diff[:]
            new_diff.append( new_mom[0]-new_mom[1])
            new_plus=plus[:]
            new_plus.append(new_mom[0]+new_mom[1])
            fire(maps, new_history_column, new_mom, new_diff, new_plus)
for i in range(n):
    fire(maps, [i],[0,i],[-i],[i])
print(answer)

 

 

참고 문헌

sooyoung32.github.io/dev/2016/03/14/n-queen-algorithm.html