[TIL] 백트래킹 - N-Queen 문제

백트래킹(Backtracking)

• 제약 조건 만족 문제에서 해를 찾기 위한 전략 
• 해를 찾기 위해 답이 될 수 있는 후보군의 제약 조건을 체크하다가 만족할 수 없는 경우 즉시 backtrack하고 다른 후보군으로 넘어간다.
• 고려할 수 있는 경우의 수를 상태공간트리(State Space Tree)를 통해 표현한다.
• DFS 방식으로 확인한다.
• promising (해당 루트가 조건에 맞는지를 검사하는 기법)
• pruning(가지치기 : 조건에 맞지 않으면 포기하고 다른 루트로 돌아서서 탐색의 시간을 절약하는 기법)

 

 

N-Queen 문제

백트래킹의 대표적인 문제

- N*N 크기의 체스판에 N개의 퀸을 서로 공격할 수 없도록 배치한다.

- 퀸은 수직, 수평, 대각선으로 이동 가능하다.

 

ex)N이 4일 경우 다음과 같이 배치할 수 있다.

 

해결방법

1. 한 행에는 하나의 퀸만 가능하다 (수평 이동)

2. 맨 위에 있는 행부터 퀸을 배치하고 다음행의 조건을 검사한다.

3. 수직체크와 대각선 체크를 하여 퀸을 배치할 수 있는지 파악한다.

4. 수직 체크 -> 퀸의 위치가 (0,1) 일때 현재 행의 열이 (1,1)이라면 퀸이 공격가능하다. 

    즉, 퀸의 위치의 열 != 현재 행의 열 이 성립해야한다.\

5. 대각선 체크 -> 퀸의 위치가 (0,1)일때 현재 위치가 (1,0) 또는 (1,2)라면 퀸이 공격 가능하다.

   즉, abs(퀸의 위치의 열 - 현재 열) != (현재 행 -  퀸의 행) 이 성립해야 한다.

   대각선에 위치할 경우 각 행열의 차에 대한 절댓값이 같다.

 

 

구현

def check(q_lst, now_col):
    row = len(q_lst)		# 현재 행  (현재 행 = 후보군 리스트의 길이)
    for q_row in range(row):
    	if q_lst[q_row] == col		# 수직 검사
        	or abs(q_lst[q_row] - col) == row-q_row:	# 대각선 검사
            	return False
	return True
    
    
def DFS(N, row, q_lst, rst):
	if row == N:
        rst.append(q_lst[:])
        return
        
	for col in range(N):
    	if check(q_lst, col):
            q_lst.append(col)			# 퀸의 후보군 리스트
            DFS(N, row+1, q_lst, rst)
            q_lst.pop()			# 조건 만족 x - 백트래킹
    	

def n_queens(N):
    rst =[]
    DFS(N, 0, [], rst)
    return rst
    
    
n_queens(4)

#[[1, 3, 0, 2], [2, 0, 3, 1]]