N-Queen

제약 조건

• 같은 행에 두지 못한다.
• 같은 열에 두지 못한다.
• 대각에 두지 못한다.
• 행과 열의 정보를 저장할 1차원 리스트를 만든다.
• 리스트의 인덱스는 행번호, 요소는 열번호
• 대각에 있는지 확인 여부는 행값의 차이와 열값의 차이가 같으면 대각에 있다.
• 또는, 대각에 있는지를 기록해 놓는 방법도 있다.
• N*N 배열에서 대각선은 2N-1개 있다.
• (r, c)의 좌표가 어느 대각의 줄에 있는지 알면 된다.
• r + c 를 해보면 구별이 된다.

• 대략 2N개 정도의 크기를 가지는 1차원 리스트를 만들어 대각의 방문 체크를 한다.
• 반대의 대각은 r - c를 하면 구별할 수 있다.
• -(N-1) ~ (N-1)까지의 숫자가 나온다.

 

• 여기서 r-c+(N-1)을 해준다.
• 이 대각의 방문표시를 해줄 리스트를 2N정도로 만들어 준다.
• 코드로 구현 하면 다음과 같다.

 

N-Queen 풀이 코드

# def nQueen(row, visit):
def nQueen(row):
    global cnt
    if row == N:
        cnt += 1
    else:
        # col은 열번호
        for col in range(N):
            val = (1<<col)
            # if visit & (1<<col): continue    # 같은 열은 제외
            if visit[col]: continue

            # 대각에 대해서 체크
            a = row + col
            b = row - col + (N-1)
            if line1[a] or line2[b]: continue

            line1[a] = line2[b] = 1
            visit[col] = 1
            # nQueen(row+1, visit | (1<<col))
            nQueen(row+1)
            line1[a] = line2[b] = 0
            visit[col] = 0

N = 8
visit = [0] * N
line1 = [0]*(N*N)   # /  (row + col)
line2 = [0]*(N*N)   # \  (row + col + (N - 1))
cnt = 0
# nQueen(0, 0)
nQueen(0)
print(cnt)

• 같은 열에 있는지 확인하는 visit은 비트연산자를 쓸 때와 리스트로 만들어 체크하는 두가지 버전이 있다.

 

N-Queen 풀이 코드 2

• 이번 풀이는 promising이란 유망성이 있는지 체크를 해주는 함수를 만들어 사용한 코드이다.
• 이 코드에서는 대각선 위치의 확인 여부를 행-열로 해준다. 좌대각, 우대각 모두 r-c의 절대값은 똑같다.

def n_queen(visit_j, depth):
    global cnt
    if promising(visit_j, depth):
        if depth == N:
            cnt += 1
        else:
            for j in range(1, N+1):
                visit_j[depth+1] = j
                n_queen(visit_j, depth+1)

def promising(visit_j, depth):
    k = 1
    flag = True
    while k < depth and flag:
        if visit_j[depth] == visit_j[k] or abs(visit_j[depth] - visit_j[k]) == (depth-k):
            flag = False
        k += 1
    return flag

for tc in range(int(input())):
    N = int(input())

    visit = [0]*(N+1)
    cnt = 0
    n_queen(visit, 0)
    print(f'#{tc+1}', cnt)