N-Queens를 공격 범위를 칠하며 푸는 방식

8x8에 퀸 8개를 서로 공격하지 않게 놓는 문제다. 한 행에 하나씩 놓는다고 보면 행마다 열을 고르는 문제가 된다.

놓을 수 있는지 매번 확인하는 대신, 놓을 때 공격 범위를 판에 칠해두는 방식으로 갔다.

def rec(board, n):
    if n == 8:
        ans.append(board)
        return

    for i in range(8):
        if board[n][i] == 0:
            temp = copy.deepcopy(board)

            for j in range(n, 8):
                temp[j][i] = 1
                if i - (j - n) >= 0:
                    temp[j][i - (j - n)] = 1
                if i + j - n < 8:
                    temp[j][i + j - n] = 1

            temp[n][i] = 2
            rec(temp, n + 1)

board[n][i] == 0 이면 그 칸은 아직 아무에게도 공격받지 않는다는 뜻이다. 확인이 이 한 줄로 끝난다.

아래쪽만 칠한다

for j in range(n, 8) 이라 지금 행부터 아래로만 칠한다. 위쪽은 이미 지나온 행이라 다시 볼 일이 없다.

j 가 아래로 내려갈수록 j - n 만큼 벌어진다. i - (j - n) 이 왼쪽 대각선, i + j - n 이 오른쪽 대각선이다. temp[j][i] 는 세로줄이다. 가로줄은 행마다 하나씩만 놓으므로 칠할 필요가 없다.

두 개의 if 는 판 밖으로 나가는 걸 막는다. 왼쪽 대각선은 0보다 작아지면 멈추고 오른쪽은 8 이상이면 멈춘다.

temp[n][i] = 2 로 퀸 자리를 따로 표시한다. 바로 앞에서 temp[j][i] = 1 이 j = n 일 때 이 칸을 1로 칠했으므로 덮어쓰는 것이다. 1은 공격받는 칸, 2는 퀸이 놓인 칸으로 구분된다.

되돌리지 않고 복사한다

백트래킹은 보통 놓고, 내려가고, 돌아와서 되돌린다. 여기서는 되돌리지 않는다.

temp = copy.deepcopy(board)

행마다 판을 통째로 복사한다. 아래로 넘긴 판이 어떻게 바뀌든 이 층의 board 는 그대로다.

되돌리는 코드를 안 써도 되는 대신 판 복사가 계속 일어난다. 8x8 리스트를 노드마다 하나씩 만드는 셈이다.

칠하는 방식에서는 되돌리기가 간단하지 않은 것도 이유가 된다. 퀸을 뺄 때 그 자리를 0으로 되돌리면 안 된다. 다른 퀸도 그 칸을 공격하고 있을 수 있어서다. 개수를 세는 판을 따로 두거나 어느 퀸이 칠했는지 기록해야 하는데, 복사가 그걸 다 피해간다.

결과

92개가 나온다. 8-퀸의 답 개수와 맞다. 판을 그대로 ans 에 담으므로 배치도 남는다.

ans.append(board) 에서 그대로 넣어도 되는 것 역시 매 층에서 새 판을 만들어 넘겼기 때문이다. 되돌리는 방식이었다면 복사해서 넣어야 한다.