[알고리즘] 되추적 - n_Queens 코드 (Back_Tracking - n_Queens Code)

문제)

Description

교재와 강의자료를 참고하여n-Queens 문제를 해결하는Algorithm 5.1을 완성하시오.

n의 값이 주어질 때, n-Queens 문제를 해결하는 보드의 배치가 총 몇 개인지를 카운트하고,

col 배열의 값을 숫자의 문자열로 취급했을 때 가장 큰 값을 출력하도록 수정하시오.

예)

n = 4일 때 가능한 보드의 배치는 다음과 같이 총 2개가 있다.

col1 = [2, 4, 1, 3]

col2 = [3, 1, 4, 2]

위 배치의 col 배열을 숫자의 문자열로 취급하면 각각 2413, 3142의 값을 갖는다.

따라서 이 문제의 출력은 다음과 같다.

2 ; 가능한 보드 배치의 갯수

3142 ; 가능한 보드 배치 중에서 숫자의 문자열이 가장 큰 값

Input

첫 줄에 n의 값이 주어진다.

단, n은 4보다 크거나 같다.

Output

첫 줄에 가능한 보드의 배치 개수를 출력한다.

둘째 줄에 col 배열의 값을 숫자의 문자열로 취급했을 때 최대값을 출력한다.

Sample Input 1

4

Sample Output 1

2
3142

Sample Input 2

9

Sample Output 2

352
974286135

Sample Input 3

12

Sample Output 3

14200
975811210364211

코드)

def promising(i):
    k = 1

    while k < i:
        if col[i] == col[k] or abs(col[i] - col[k]) == i - k:
            return False
        k += 1

    return True


def queens(i):
    global cnt
    global max_value
    if promising(i):
        if i == n:
            cnt += 1
            temp = int(''.join(map(str, col)))
            if temp > max_value:
                max_value = temp
        else:
            for j in range(1, n + 1):
                col[i + 1] = j
                queens(i + 1)


if __name__ == "__main__":
    n = int(input())
    cnt = 0
    col = [0] * (n + 1)
    max_value = 0
    queens(0)

    print(cnt)
    print(max_value)

 

2번째 코드)

def promising(i):
    for k in range(1, i):
        # 1 ~ i-1까지 봤을 때, 같은 열, 같은 대각선이 아니라면 유망함
        if col[i] == col[k] or abs(col[i] - col[k]) == i - k:
            return False
    return True


def queens(i):
    global col, n, max_value, cnt

    if promising(i):
        # 만약 i번째 row가 유망하다면
        if i == n:
            # state space의 끝에 도달함
            cnt += 1
            temp = int(''.join(map(str, col)))
            if temp > max_value:
                max_value = temp
        else:
            # state space의 끝에 도달하지 않음
            for j in range(1, n + 1):
                # 모든 column을 넣어봄
                col[i + 1] = j      # i번째까지 유망하므로, i + 1에 j를 넣음
                queens(i + 1)


n = int(input())        # 보드의 크기
col = [0] * (n + 1)     # 각 row에서의 queen의 column
max_value = 0
cnt = 0

queens(0)

print(cnt)
print(max_value)