[Algorithm] N-Queens Problem with backtracking

n-queens problem은 크기가 N인 체스판에, 여왕말 N개를 서로를 공격할 수 없게 두는 것이다. 

이건 꽤 흥미로운데, 왜냐면 

 

 

queen은 좌우상하 대각선4방향 전부 다 되기 때문...!!! 그래서 생각보다 놓을 수 있는 곳이 한정적이다. 

 

되는 예제 1가지!

이걸 풀기 위해서 backtracking이라는 기법을 적용했다. 

백트래킹(backtracking)이란? : 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법을 말합니다. 최적화 문제와 결정 문제를 푸는 방법이 됩니다.

출처: https://chanhuiseok.github.io/posts/algo-23/

일단 어떻게 거기 놓을 수 있는지 판단하는 방법부터 알아보자. 

 

 

다음과 같이 (1,2)에 놓인 queen이 있다. (왼쪽 위는 0,0이라고 가정한다.)

 

상하좌우 대각선을 다 검색해야 하는데, 

 

row: (1,0) (1,1) (1,3)

col: (0,2) (2,2) (3,2)

diagnol: (0,1) (2,3)

diagnol: (0,3)(2,1)(3,0)

 

row는 row같고 col만 1씩 차이나게

col은 col같고 row만 1씩 차이나게

diagnol은 row-col이 -1이게

다른 diagnol은 row+col 이 3이게

 

 

 

 

 

 

이렇게 놓고 나니 2번째 줄에는 더이상 둘곳이 없다. 이럴 경우 backtracking!

 

이렇게 했더니 3번째 줄에는 또 둘곳이 없다. 이 경우 backtracking!

 

Backtracking 하다보니, 1번째 row에서는 더 이상 뒤로 갈 수가 없다. 그러면 0번째 row를 한 칸 더 이동시켜준다. 

 

 

 

=== 이런식으로 쭉 해주면 된다. 

근데 코드는 어떻게 짤까??????

 

일단, 백준 9663번 기준 이중for문으로 파이썬에서 위 예시처럼 체스판을 돌면서 하나씩 확인을 하면 백퍼 타임아웃이 난다. 따라서 알고리즘을 수정해야 한다.

 

 

일단, 한 행에서는 체스 말을 하나씩만 둔다. 따라서 행에서 겹치는 경우는 고려하지 않아도 된다. 

 

그리고 check_col, check_diagnol, check_diagnol2라는 배열 3개를 만든다. 행, 열, 대각선에 말이 들어가면 체크해줘서 굳이 체스판을 하나씩 돌면서 확인하지 않아도 되게 하는 용도이다. 

 

check_col[col] = 1
check_diagonal[row+col] = 1
check_diagonal2[row-col + (N-1)] = 1

 

backtracking은 어떻게 구현할까??

dfs 로 하면 될것같았는데 되게 어려웠다. 근데 어떤 천재가 구현해둔걸 봤는데 개쩔어서 공유한다..

 

import sys
n, ans = int(sys.stdin.readline()), 0
a, b, c = [False]*n, [False]*(2*n-1), [False]*(2*n-1)

def solve_dfs(i):
    global ans
    if i == n:
        ans += 1
        return
    for j in range(n):
        if (not a[j] and not b[i+j] and not c[i-j+n-1]) :
            a[j] = b[i+j] = c[i-j+n-1] = True
            solve_dfs(i+1)
            a[j] = b[i+j] = c[i-j+n-1] = False

solve_dfs(0)
print(ans)

 

파이썬 코드 출처: wlstyql.tistory.com/96

 

 

 

 

 

check_col, check_diagonal, check_diagonal2는 나와 같은데 dfs를 구현한 방식이 개쩐다. 

 

 

이렇게 하면 밑에줄부터 키워가면서 구할 수 있고 코드도 엄청 깔끔하다. 

N까지 i가 가면 모든 줄을 다 채운거니까 ans에 1 더해주고 return하고, 그러면 그 부모 함수에서 check변수들을 비워준다음에 j를 1키워서 자기 줄에서 또 함수를 콜 해줄수 있는지 확인한다. 없으면 함수가 끝나서 걔를 콜해준 부모에서 또 check변수를 지우고 j를 1 키워서 확인하고, 있으면 다시 함수 스택 쌓고..이런식으로 한다. 존나 천재;;;진짜 깔끔한 dfs다.