N-Queen 파이썬 풀이

백트레킹으로 푸는 문제라고 한다 근데 백트레킹이 뭔지는 아직도 잘모르겠다 그냥 재귀함수 아닌가...?

쨋든

 

이문제를 푸는데 3일정도 걸렸다 문제를 이해하고 처음 코드를 적기까지 2일 그리고 제출하기까지 하루가 걸렸다

입력 예제 에서 8*8체스판에 퀸 8를 서로 공격하지 않토록 놓을수 있는 경우의 수가 92개라고 하길래

그렇게 많아? 하면서 겹치지않게 8개를 놓아보려고 시도를 했으나 한번도 성공하지못했다(물론 지금도)

 

문제 말도 안되는것같은데 하면서 유튜브에 퀸 8개 놓기라고 검색해보았고 실제로 손쉽게 성공시키는 분을 보며

불가능하지는 않다고 결론내렸다

 

내가 문제를 이해하는데에만 이틀동안 걸린이유는

이걸 프로그래밍으로 모든 경우의 수를 찾게 구현할때

퀸을 어디에다 놓느냐에 따라 거기서 퍼지는 경우의수의 가짓수가 각각 달라지는데 이것은 정형화된 틀속의 반복문으로 구현할수없는것이다

예를들어 퀸을 사이드에놓으면 다음줄은 윗줄의 퀸으로인해 2개를 이용할수없지만 

사이드를 제외한 곳에 놓으면 3칸을 이용할수없다

그래서 재귀함수로 구현해볼까 생각도했지만 마땅히 떠오르지않았던것같다

 

그래서 수학적으로 접근하려고 노력했다

완성되는 규칙을 찾으면 쉽게 풀수 있을것이라고 생각했던것이였다

다만 아까도 말했다싶이 8*8체스판에서 8개의 퀸을 놓는경우를 나는 하나도 구현하지못했다 

 

결국 답을 한번 찾아보았는데

 

다른사람의 코드를 봐도 전체과정이 이해가 잘되지않았다 

아니 일부러 제대로 보지않은것일수도 있겠다

 

뭔가 백트레킹을 제대로 활용해야 풀수있는 문제같다는 생각이 들었고  

이문제를 풀기전 전에 풀었던 백트레킹 문제를 살펴보았다

 

수열과 조합에 관한문제였다 

이것을보고 뭔가를 느낀나는 첫번째 제출을 해보게된다

def 수열(thelist,M):
    chosen=[]
    if len(thelist)<M:
        return
    elif M == 1: # 재귀끝
        for i in thelist:
            chosen.append([i])
        return chosen
    elif M > 1: # 재귀 구현
        for i in thelist:
            for j in 수열([k for k in thelist if k!=i],M-1):
                chosen.append([i]+j)
        return chosen
    
def 조합(thelist,num):
    chosen=[]
    if len(thelist)<num:
        return
    elif num == 1: # 재귀끝
        for i in thelist:
            chosen.append([i])
        return chosen
    elif num > 1: # 재귀 구현
        for i in range(len(thelist)-(num-1)):
            for j in 조합(thelist[i+1:],num-1):
                chosen.append([thelist[i]]+j)
        return chosen

# # 같은수가 중첩되지않는 [0,1,2,3] 순서쌍 찾기
# 수열(list(range(8)),8)

N=int(input())
# 경우의 수 안의 모든 조합을 구한뒤 if 문을활용하여 모든조합에서 이상없을시 count 하나라도 틀릴경우 break
ans=0
# 체스판의 경우의수
for i in 수열(list(range(N)), N):
    # 각각의 체스판의 경우의수에서 대각선이 겹치는 경우가 있는지 확인
    cnt=0
    for j in 조합(list(enumerate(i)), 2):
        if abs(j[0][0]-j[1][0]) == abs(j[0][1]-j[1][1]):
            break
        else:
            cnt+=1
    if cnt==sum(list(range(N))):
        ans+=1

print(ans)

1. 체스판에 퀸의 행과 열이 겹치지않게 놓을수있는 모든 경우의 수를 구한다(수열)

2. 거기서 체스말 서로끼리의 모든 조합을 찾아낸다(조합)

3. 그 조합에서 서로의 말이 대각선에 위치한경우 반복문이 해제된다

4. 만약 모든말이 대각선에 위치하지 않음을 확인한경우 ans에 1이 추가 된다

 

여기서 비효율적인 부분은 모든경우의 수를 일단 찾아낸후에 소거하는식으로 진행된다는점

메모리적인 측면과 시간적인측면 모두에서 비효율적이다

 

또한 대각선을 구할때 

먼저 조합을 모두 구해보는것역시 메모리적인 측면에서 좋지않다

 

8을 넣었을때 92가 되는것을 확인하고 제출하였지만 메모리 초과가 떳다

뭔가 예상되는 결과였다

 

수열의 경우의수는 N이 14일경우 14!이다 

즉 800억정도의 엄청큰수인데 이걸 일일이 다 찾고 있으니 메모리초과가 나는건 당연하다 

 

메모리 초과가날때는 해당 알고리즘을 갈아엎어야된다는 사실을 알고있었기때문에

잠시 재충전의 시간을 가진후 N-queen에대해서 인싸이트를 얻고자 더 검색을 해보았다

 

아래는 두번째로 제출한 답안이다

import copy
ans=0
def n_queen(board,row):
    global ans
    for i in range(N): # row가 행 i가 열
        if board[row][i]: # 놓을게있다
            new_board=copy.deepcopy(board) 
            if row==N-1:
                ans+=1
            else:
            # 대충 보드수정
                # 행 수정
                new_board[row]=[False]*N
                # 열 수정
                for j in range(N):
                    new_board[j][i]=False
                # 위 대각선들
                for z in range(1,row+1):
                    if i+z<N:
                        new_board[row-z][i+z]=False
                    if i-z >= 0:        
                        new_board[row-z][i-z]=False
                # 아래 대각선들
                for y in range(1,N-row):
                    if i+y<N:
                        new_board[row+y][i+y]=False
                    if i-y >= 0:
                        new_board[row+y][i-y]=False    

                n_queen(new_board,row+1)
                 
N=int(input())
board=[]
for i in range(N):
    board.append([True]*N)
n_queen(board, 0)
print(ans)

코드를 작성하면서 조건문을 표현한 재귀방식에대해서 뭔가 더감이 잡힌것같았다 

더 깊은 재귀로 가지를 뻗을것이냐 안뻗을것이냐를 조건문에 맞게하면

노드에따라 브랜치의 개수가 다른경우도 구현할수있다(이렇게 표현하는거 맞나...?)

 

2차원으로 구현한 체스판을 점점 수정하면서 놓을수있는 공간이있으면 해당 공간에대해 모든 경우의 수를 시험해본다

놓을수없는 공간이없다면 해당 경로는 거기서 끝이나게된다

 

또한 반복문에서 다음 경우의수를 시험할때는 체스판이 다시 원상태로 돌와야되는데 이를 구현하기위해 깊은 복사를 이용했다

난지금까지 깊은 복사를 하기위해서는 그냥 뒤에 .copy()쓰면되는줄알았는데(사실이것도 그냥 판다스 문법임)

copy라는 모듈을 다운받은후 deep.copy(list)를 사용하는지는 모르고있었다 따라서 많은 시간을 허비한후에야 무엇이 원인이었는지 이해하게되었다 오늘도 맞으면서 배웠지만 그래서 오랫동안 까먹진않을것같다

 

체스판을 시각적으로 구현했다는점에서 맘에들었지만 답을 막상 제출해보니 시간 초과가 떳다

 

마지막으로 제출한답은 다른분의 정답을 이해한후 제출하였다

https://seongonion.tistory.com/103

n = int(input())

ans = 0
row = [0] * n

# 놓을수있는지 확인(판별기)
def is_promising(x):
    for i in range(x):
        # 각각 열이 같을때, abs(열-열)과 abs(행-행)이 같은경우 즉 대각선에 있는경우 False return
        if row[x] == row[i] or abs(row[x] - row[i]) == abs(x - i):
            return False
    return True

# 퀸을 행순으로 놓아간다
def n_queens(x):
    global ans
    # 끝단계까지 놓은경우 n은 최대행보다 1이 더 크다
    if x == n:
        ans += 1
        return

    else:
        for i in range(n):
            # [x, i]에 퀸을 놓겠다.
            row[x] = i
            # 놓을수있는경우 다음단계로 넘어가겠다
            if is_promising(x):
                n_queens(x+1)

n_queens(0)
print(ans)

퀸을 놓는 함수와 퀸을 놓을수있는지 판별하는 판독기를 따로 배치했다는점에서 인상적이었다

확실히 함수를 두개쓰면 어떤 구조인지 다른사람이 볼때도 파악하기 좋은것같다

 

파이썬에선 시간초과 pypy에서는 맞았습니다 처리가된다

질문방에서 어떤분이 파이썬으로는 풀수없는 문제냐고 질문하신게 어떤뜻인지 알것같았다

 

내가 두번째로 낸 답안과는 다르게 

퀸의 위치에서 대각선을 검사할때 단 한번의 반복문밖에 사용하지 않는다

나는 그에비해 3번의 반복문을 사용했다

 

하지만 내가 두번째로 제출한 답안은 나보다 위에 있는줄들의 이동경로인경우 이미 False로 표시가 되어있기때문에

애초에 검사를 하지않기때문에 또 시간이 절약되기는 한다

 

하지만 마지막에 제출한답은 대각선이나 같은 열에있는경우 바로 False를 return하기때문에 어쩌면 많은 시간이 걸리지않을지도 모른다

 

다른분의 답안을보고 이해한후 제출하는것으로 일단 만족은 되었다 나나름대로 답안을 만들어보기도했고

 

문제와는 별개로 N-queen의 단순한 경우의수말고도 직접 해당 체스판을 보고싶다는 생각이들었고 그것은 아래의 코드와 같다

import numpy as np
import copy
ans=0
def n_queen(board,row):
    global ans
    for i in range(N): # row가 행 i가 열
        if board[row][i]: # 놓을게있다면
            new_board=copy.deepcopy(board) 
            if row==N-1:
                ans+=1
                print(np.reshape(new_board,(N,N)))
                print('-'*28)
            else:
            # 대충 보드수정
                # 행 수정
                new_board[row]=[False]*N
                new_board[row][i]=[True]
                # 열 수정
                for j in range(N):
                    new_board[j][i]=False
                new_board[row][i]=True 
                # 위 대각선들
                for z in range(1,row+1):
                    if i+z<N:
                        new_board[row-z][i+z]=False
                    if i-z >= 0:        
                        new_board[row-z][i-z]=False
                # 아래 대각선들
                for y in range(1,N-row):
                    if i+y<N:
                        new_board[row+y][i+y]=False
                    if i-y >= 0:
                        new_board[row+y][i-y]=False    

                n_queen(new_board,row+1)
                 
N=int(input())
board=[]
for i in range(N):
    board.append([True]*N)
n_queen(board, 0)
print(f'N-Queen 모든 경우의수는 {ans}개입니다')

위 코드를 실행하면 모든 경우의 수와 조건을 만족하는 2차원 체스판의 배열도 함께나온다 

만족스러웠다

 

다음포스팅은 아마 딥러닝관련이 될것같다 재밌었다