N - Queen

0. 참고 문헌

<뇌를 자극하는 알고리즘>

 

1. 문제

<퀸 사진 출처:  http://terms.naver.com/entry.nhn?docId=1839607&cid=49110&categoryId=49110 >

2. 문제 분석

퀸은 8가지 방향으로 움직이며 공격을 할 수 있고, 이동 범위도 체스판 전체이다.

8개의 퀸 문제는 8 X 8 크기의 체스판을 염두에 두고 제안됐지만 다른 크기의 체스 판으로도 문제의

확장과 축소가 가능하다.

4 X 4 이상의 크기라면 이 문제를 적용할 수 있는데, 그래서 8개의 퀸 문제를 N 개의 퀸 문제라 부르기도 한다.

퀸을 체스판에 배치할 때, 행을 기준으로 배치하는 것으로 약속을 하도록 하자.

그리고 체스판은 4 X 4로 고정하고 문제 풀이에 접근한다.

당연히 퀸은 하나의 행에 하나만 배치가 가능하다. (퀸의 공격 범위가 가능하므로)

아래의 [그림 1 ~ 4]는 체스판의 크기가 4 X 4일 때의 퀸을 놓는 방법을 나타낸 것이다.

별 모양이 퀸이다.

 

[그림 1]

 

[그림 2]

 

[그림 3]

 

[그림 4]

3. 자료 구조 정의

N 개의 퀸 문제를 풀려고 하는데, 퀸을 배치할 자료구조로 체스판과 같은 N X N 크기의 이차원 배열이

필요할 것이라고 예상을 할 것이다.

N개의 퀸 문제의 해를 담는 데에는 그냥 N개의 배열 하나면 충분하다.

아래와 같은 N개의 배열에서 인덱스는 행(row)으로, 배열에 저장된 값은 열(column)로 사용하면 된다. 

즉, 일차원 배열 하나로 이차원 배열의 역할을 충분히 할 수 있다.

퀸의 개수를 4개로 고정시켰으므로, 4칸짜리 배열이 4 X 4 체스판 역할을 할 수 있다.

4. 필요한 함수

함수는 퀸을 배치하는 함수와 체스판에 배치한 퀸들이 서로 공격이 가능한지 체크하는 함수 이렇게 2개가 필요하다.

위의 그림에서 보다시피 퀸을 배치하는 일련의 과정들은 재귀함수의 호출을 통해 구현하리라는 것을 알게 된다.

그리고 퀸들이 서로 공격이 가능한지 체크하는 함수를 구현할 때, 퀸들의 가로(열) 체크는 하지 않아도 된다.

그 이유는 위에서 퀸을 각 행에 하나씩 배치한다고 하였기 때문이다.

체크를 하는 부분은 각 퀸들의 세로 방향과 대각선 방향만 체크하면 된다.

[0행 3열]과 [2행 1열]에 위치한 퀸들은 서로 대각선으로 공격 가능한 상태이다.

즉, 두 행의 차의 절대값과 두 열의 차의 절대값이 서로 같으면 대각선에 놓여있음을 알 수 있다.

다른 예를 들어보자.

[1행 0열]과 [2행 1열]은 서로 대각선이다. 위의 식에 대입하여 검토해보자.

abs(1-2)와 abs(0-1)은 서로 같으므로 대각선이다.

아래의 함수는  퀸을 배치하는 함수이다.

 

5. 구현

프로그램 실행결과

6. 소스 파일

main.c

0.00MB