[ 알고리즘 ] Back tracking : N-Queen

1. 문제 정의

 

N x N 크기의 체스판이 있을 때 N개의 퀸을 서로가 공격할 수 없도록 올려놓는 경우의 수를 구하는 문제이다.

체스판

2. idea

N이 4일 때를 기준으로 생각해 보겠다.

 

2.1 다해본다

16C4 * 16 

 

2.2 겹치는 경우는 뺀다. 

한 열에 하나 씩 배치 4^4

 

2.3 cut off

 

(1,1) 에 퀸을 배치하고 그 퀸이 갈 수 있는데를 다 표시한다.

표시되지 않은 칸들 중 하나에 퀸을 배치하고 또 그 퀸이 갈 수 있는데를 다 표시한다.

 

이런식으로 (1,1) 부터 (1,n)까지 시도해본다.

 

사실 오른쪽과 왼쪽은 대칭이기 때문에 왼쪽 반만하고 곱하기 2를 해줘도된다.