N queens problem 백트래킹

n queens 문제는 체스판의 각 행마다 말을 하나씩 놓는데 이 말들이 같은 열과 같은 대각선상에 놓여있지 않아야 한다.

상태공간트리를 만들어 조건이 맞는지 탐색해보는데 중간에 조건에 맞지 않으면 False를 리턴한다. False를 리턴하게 되면 이전 행으로 올라간다고 생각하면 되는데 그래서 Back Tracking이라고 부른다. 처음부터 마지막 행까지 가지 않아도 조건에 맞지 않다면 중간에 다시 올라온다.

n=int(input('체스판의 가로 수 입력'))
cols = [0 for i in range(n+1)]
def promising(level): #유망성 따지기
    for i in range(1,level): #첫 행부터 현재 행의 위의 행까지
        if cols[level] == cols[i]:return False #현재 행의 말의 위치와 같은 열에 말이 있다면
        elif level - i == abs(cols[level] - cols[i]):return False #행의 간격과 열의 간격이 같다면 즉, 대각선 상에 있다면
    return True #위 경우가 아니라면 조건에 만족하므로 True
def queens(level):
    if not promising(level):return False #유망성 함수가 False라면 False
    elif level == n: #level이 n에 도달했다면 즉, 끝까지 탐색을 했다면 결과와 True 리턴
        print(cols)
        return True
    for i in range(1,n+1): #전체 행을 돌면서
        cols[level+1] = i #각 행에 열들을 대입하면서
        if queens(level+1): #다음 행이 True면
            return True #True 리턴
    return False #True가 아니면 False 리턴
queens(0)

출력을 체스판처럼 만들었다.

n=4
cols = [0 for i in range(n) for i in range(n)]
def promising(level):
    for i in range(1,level): #각 행을 돌면서
        if cols[i] == cols[level]: return False #같은 열에 말이 있으면 False
        elif level-i == abs(cols[level]-cols[i]):return False #동일 대각선에 말이 있으면 False
    return True #나머진 True
def queens(level):
    if not promising(level): #조건에 만족하지 않으면 False
        return False
    elif level == n: #level이 끝까지 갔다면
        #for i in range(1,n+1):
        #    print('(',i,',',cols[i],')')
        #    print(cols)
        for i in range(1,n+1):
            for j in range(1,cols[i]):
                print('□',end='')
            print('■',end='')
            for k in range(cols[i]+1,n+1):
                print('□',end='')
            print()
        return True
    for i in range(1,n+1):
        cols[level+1] = i #level+1 행의 i번째 열에 말을 놓는다
        if queens(level+1):return True #아래 행들에 말을 놓으면서 끝까지 가면 True
    return False #조건에 만족하지 않으면 False
queens(0)