n-queens problem (back tracking)

소개글

프로그래밍 기법 중 back tracking에 대한 내용입니다.
n-queens problem이라는 문제를 풀이함으로써 back tracking에 대한 개념을 설명합니다.
문제는 다음과 같습니다.

problem :
queen을 서로 상대방을 위협하지 않도록 n x n 서양장기판에 위치시키는 문제이다. 같은 행이나 같은열, 같은 대각선 상에 위치하면 안된다.


프로그램 개요
n-queens algorithm은 Back Tracking 이라는 개념을 도입해서 문제를 푼다. Back Tracking이란 상태공간트리에서 깊이 우선검색을 실시할 때에 유망하지 않은 즉, non-promising한 노드들을 가지쳐서(pruning) 검색하지 않고 promising한 노드만 검색하여 검색횟수를 줄여 효율적인 프로그램을 하는 방법이다.
보통 Back Tracking의 방법은 checknode와 expand의 두가지 방법으로 풀이할 수 있는데 checknode가 모든 유망성을 check함에 반해 expand는 decendant node의 유망성을 먼저 고려해 가지치는 횟수를 줄여 checknode보다 더 빠른 결과를 만들어 낸다.

*promising 정의 : 전혀 해답이 나올 가능성이 없는 노드는 유망하지 않고 그렇지 않으면 유망하다.

컴파일 실행환경

gcc 컴파일러 / Debian Linux

참고 자료

없음