N-Queen

N-Queen

---

n*n 체스판에서 n개의 여왕을 서로 공격할 수 없도록 배치하는 문제
어떤 두 여왕도 같은 행, 같은 열, 같은 대각선 상에 위치할 수 없음

→ N x N 보드에서, 서로 영향을 줄 수 없는 체스 여왕 배치 경우의 수

n이 4이상일 때만 해가 존재

@ NQ_0000, 8-여왕 문제 해답 예

Solve By BackTracking

---

상태 공간 트리

같은 줄에 두 여왕을 배치할 수 없음
→ 첫 번째 줄부터 한 줄에 한 여왕만 있을 수 있음

1~n번 행 순서대로 여왕이 어디 위치하고 있는지 저장하여 트리 구성

@ NQ_0001, 경우의 수 체스판 보드 예시 (Start으로부터 4개의 체스판, …)

각 여왕의 좌표는 (1, 3), (5, 3) 이런식으로 표현 가능

@ NQ_0002, Start 노드에서 시작해서 쭉 내려가는, 각 노드에 좌표를 적은 상태 공간 트리 예시
@ 최종 상태 체스판 보드 예시 (정답이 아닌 경우도 있고, 정답인 경우도 있고)

유망하지 않다 = 겹치는 경우가 있다 = (행이 겹친다, 열이 겹친다, 대각선으로 겹친다)

@ NQ_0003, 내려가다가 유망하지 않은 노드에는 x 표시하고 넘어간, 상태 공간 트리 예시

n-여왕 문제는 해답이 여럿 있을 수 있으므로 상태 공간 트리를 모두 뒤져야 한다
뒤지는 동안 각 행 (배열) 오르락 내리락하는 모습 (상상하세요)

알고리듬

Back-Tracking, 실제로 트리를 만들지는 않고, 각 레벨에 해당하는 상태 정보를 배열에 저장한다.

• 배열을 이용하여 상태 공간 트리를 관리하는 방법
  • 기억해야 할 정보는 “걸어온 길”
  • 레벨 i 노드는 i 번째 행까지 놓인 i 개의 여왕 위치를 기억해야 함
    • 해당 노드가 유망하여 자식 노드로 내려간다면, 다음 단계에 i + 1개의 여왕 위치를 기억
    • 해당 노드가 유망하지 않아 부모 노드로 되돌아간다면, 다음 단계에 i - 1개의 여왕 위치를 기억

인덱스	1	2	3	4
열	2	4	1	3

@ NQ_0004

• 배열 인덱스: 행
• 배열 값: 해당 행에서 놓인 여왕의 열 위치

∴ n 개의 열을 저장할 수 있는 1차원 배열이 필요

• 상태 공간 트리에 대응하는 배열 상태
  • 각 노드에 해당하는 배열의 값들은 부분해
    • 아래로 이동하면 다음 인덱스에 값을 저장하고 위로 이동하면 마지막에 저장된 배열 원소는 덮어쓰기가 가능 → 전진할 때 기억하고 후진할 때 기억에서 지움

@ NQ_0005, 알파고 경우의 수 사진

구현

QueenBT(0) 을 호출함으로써 시작

void QueenBT(int i) // 노드가 아니라 레벨, 레벨에 대한 처리
{
    if (!Promising(i)) // 유망하지 않으면 패스
        return;

    // 마지막 행이면 끝
    // 왜 바로 끝이냐면, 유망한 노드에 대해서만 검사를 하니까 (위에서 검사)
    if (i == n) 
    {
        OutputSolution(i);
    }
    // 마지막 레벨이 아니면
    // 자식 노드들에 대해서 검사
    else
    {
        for (int col = 1; col <= n; col++)
        {
            column[i + 1] = col;
            QueenBT(i + 1);
        }
    }
}

bool Promising(int i)
{
    // 유망하지 않은 경우
    // 1. 같은 행: 알고리듬 상 경우 없음
    // 2. 같은 열: column[i] == column[j]
    // 3. 같은 대각선 :
    // 서로를 잇는 선분의 기울기가 1 또는 -1 = x 차이 절댓값과 y 차이 절댓값이 똑같음
    for (int j = 0; j < i; j++)
    {
        if (column[i] == column[j] || Math.Abs(column[i] - column[j]) == i - j)
            return false;
    }
    return true;
}

분석

상태 공간 트리의 노드 수

\[1 + n + n^2 + ... + n^n = {(n^{n+1} - 1) \over (n-1)}\]

알고리듬 시간은, 상태 공간 트리의 노드 수에 비례 (최악의 경우 상태 공간의 모든 노드를 방문)
4-Queen: 341개, 8-Queen: 19,173,961개

유망한 노드 수 최대/상한

\[1 + n + n(n-1) + n(n-1)(n-2) + ... + n!\]

같은 열에 두 여왕을 배치할 수 없으므로, 상태 공간 트리에서 레벨이 하나씩 증가할수록 유망한 노드의 수는 하나씩 줄어듦.
4-Queen: 최대 65개, 8-Queen: 최대 109,601개

실제 방문하는 노드의 수 (N-Queen)

n	DFS (모든 노드 수)	Back-Tracking (실제 방문 노드 수)	유망한 노드 수
4	341	61	17
8	19,173,961	15,721	2,057
12	9.74 x 10^12	1.01 x 10^7	8.57 x 10^5

Solve By Genetic-Algorithms

---

유전 알고리듬을 문제에 적용하는 과정

1. 인코딩 Encoding, 적합도 함수
   • 문제를 컴퓨터가 이해하는 방식으로 → 각 여왕의 좌표를 배열로 저장
   • 적합도 함수 → 각 여왕이 다른 여왕과 가로, 세로, 대각선으로 만나는 지
2. 모집단 구성
3. 적합도 평가
   • 적합도 함수를 바탕으로 계산한 점수
   • 각 Solution의 점수를 점수 총합으로 나눈 비율을 바탕으로 임의의 Solution 선택
4. 선택 (- 재생산을 하기 위해)
   • 재생산 → 교차, 돌연변이
   • i.e. 다른 Solution과 일정 범위 여왕의 좌표 교체, 특정 여왕 좌표 변화
5. 답을 찾을 때 까지 반복