8.12 여덟개의 퀸

문제 

8*8 체스판 위에 여덟 개의 퀸(queen)이 서로 잡아 먹히지 않도록 놓을 수 있는 모든 가능한 방법을 출력하는 알고리즘을 작성하라.

즉, 퀸은 서로 같은 행, 열, 대각선 상에 놓이면 안된다. 여기서 '대각선'은 모든 대각선을 의미하는 것으로 체스판을 양분하는 대각선 두개로 한정하지 않는다. 

 

해결법

한 열에 하나씩 놓고 다음 놓는 말은 이전 열들과 규칙을 지키면서 놓을 수 있는 모든 경우의 수를 놓아가면서 가장 끝가지 경우를 만들어 가고 , 갈 곳이 없다면 다시 돌아와서 다른 경우의 길로 선택해 가는 것을 반복하는 backtracking 기법을 이용하면 해결 할 수 있다.

def Solution():
    result = []
    queens = [-1]*8

def isVaild(queens, index , place) :
    for i in range(index):
        if queens[i] == place :
            return False
        if index - i == abs(queens[i] - place):
            return False
    return True

def placeQueen(queens, index, result):
    if index == 8 :
        result.append(queens)
    for i in range(8)
        if isVaild(queens, index, i):
            queens[index] = i
            placeQueen(queens, index+1, result)