백트래킹 알고리즘

깊이탐색을 기본으로 하는 알고리즘

모든 경우를 조사함으로 "가지치기"(필요없는 루프는 잘라내기)를

잘 해야 빠르게 결과값을 얻을 수 있다.

bool finished = false;     // 모든 풀이를 찾았는지 여부 //
backtrack(int a[], int k, data input)
{
        int c[MAXCANDIDATES]; // 다음 위치가 될 수 있는 후보 위치 //
        int ncandidates;          // 다음 위치가 될 수 있는 후보 개수 //
        int i;                         // 카운터 //

        if ( is_a_solution(a, k, input) )
                process_solution(a, k, inpit);
        else
        {
                k++;
                construct_candidates(a, k, input, c, &ncandidates);
                for(i=0; i<ncandidates; i++)
                {
                        a[k] = c[i];
                        backtrack(a, k, input);
                        if(finished) return;  // 일찍 종료함 //
                }
        }

}