💁‍♀️ N-Queens?

• N-Queens 문제란, N x N 크기의 체스판에 N개의 퀸을 서로 공격하지 않도록 놓는 문제입니다. 여기서 퀸은 가로, 세로, 대각선 방향으로 모두 공격이 가능합니다.

• 백트래킹 알고리즘을 사용하여 문제를 해결했습니다.
  
  

  ---

💁‍♀️ 백트래킹(backtracking) ?

• 백트래킹 알고리즘은 완전탐색을 기반으로 하는 알고리즘으로, 해를 찾기 위해 모든 경우의 수를 탐색하면서, 현재 경로가 해가 될 가능성이 없다고 판단되면 이전 단계로 돌아가 다른 경로를 탐색하는 방법입니다. 즉, 현재 경로에서 더 이상 해를 찾을 수 없다고 판단되면, 이전 단계로 돌아가서 다른 가능성 있는 경로를 찾습니다.

• 백트래킹 알고리즘은 주로 조합, 순열, 그래프 탐색, 제약 충족 문제등의 문제에서 사용됩니다.

• 백트래킹 알고리즘의 장점은 모든 경우의 수를 검사하므로 해가 반드시 존재할 때 정확한 해를 찾아낼 수 있다는 것입니다. 또한, 상황에 따라 최적의 결과를 찾을 수 있는 경우도 있습니다.

• 하지만, 경우의 수가 많을 경우에는 많은 시간이 소요될 수 있다는 단점이 있스니다. 따라서, 백트래킹 알고리즘을 사용할 때는 가능한 모든 경우의 수를 탐색하지 않고, 불필요한 경우의 수를 배제하는 등의 최적화 기법을 사용하여 실행 시간을 단축시켜야 합니다.
  
  

  ---

💁‍♀️ 코드

def promising(i, j):![](https://velog.velcdn.com/images/123xxx/post/1cf4b4eb-e8f1-406b-a8b6-de4f42eeb366/image.jpg)

    for di, dj in [[-1, -1], [-1, 0], [-1, 1]]:
        ni, nj = i+di, j+dj
        while 0 <= ni < N and 0 <= nj < N:
            if board[ni][nj]:   # 다른 퀸이 있으면
                return 0    # 실패!
            ni, nj = ni+di, nj+dj
    return 1    # i, j에 퀸을 놓을 수 있음


def f(i, N):
    global cnt
    if i == N:  # N개의 퀸을 놓은 경우
        cnt += 1
    else:
        for j in range(N):
            if promising(i, j):
                board[i][j] = 1
                f(i+1, N)
                board[i][j] = 0


T = int(input())
for tc in range(1, T+1):
    N = int(input())
    board = [[0]*N for _ in range(N)]
    cnt = 0
    f(0, N)
    print(f'#{tc} {cnt}')

개요

• 이 코드는 백트래킹 알고리즘을 사용하여, 체스판의 각 행에 하나씩 퀸을 놓습니다. 각 행에 퀸을 놓을 때, 해당 행에서 가능한 모든 열을 탐색하면서 퀸을 놓을 수 있는지 확인합니다. 퀸을 놓을 수 있다면, 해당 위치에 퀸을 놓고 다음 행으로 진행합니다. 퀸을 놓을 수 없다면, 다음 열을 탐색합니다.

f 함수

• f 함수는 첫 번째 행부터 시작하여 마지막 행까지 하나씩 퀸을 놓는 함수입니다. 첫 번째 행부터 시작하여 각 행에 퀸을 하나씩 놓으며, 이때 promising 함수를 사용하여 해당 위치에 퀸을 놓을 수 있는지 여부를 확인합니다. 만약 해당 위치에 퀸을 놓을 수 있다면, 해당 위치에 퀸을 놓고 다음 행으로 넘어갑니다. 만약 해당 위치에 퀸을 놓을 수 없다면 다음 열을 탐색합니다.

promising 함수

• promising 함수는 현재 위치 (i, j)에 퀸을 놓을 수 있는지 여부를 확인하는 함수입니다. 이 함수는 현재 위치에서 가로, 세로, 대각선 방향으로 다른 퀸이 있는지를 확인하여, 다른 퀸이 없으면 1을 반환하고, 다른 퀸이 있으면 0을 반환합니다.

cnt 변수

• cnt 변수는 가능한 경우의 수를 세는 변수입니다. 모든 경우의 수를 탐색한 후 cnt 변수에 저장된 값을 출력합니다.