안녕하세요. 종만님책 애독자입니다 ^^;
책에서 "6.완전탐색"까지 공부한 뒤, 완전탐색법을 이용하여 NQUEEN 문제를 풀어보았는데 Time out 이 나네요ㅠ.ㅠ
완전탐색법으로는 해결할 수 없는 문제인지 아니면 제 구현방법이 잘못된 것인지 .. 도움 부탁드립니다. ㅠ.ㅠ
제 소스코드는 아래와 같구요,
제 알고리즘을 간단히 설명드리자면

1. 일단 NxN 을 0으로 초기화
2. (0,0)으로부터 시작하여 (N,N)까지 우측하단 대각선 방향으로 진행하면서 0을 만나면, 1을 더한뒤(Queen을 놓는다는 의미), Queen이 진행할수 있는 방향(오른쪽,아래쪽,우하단대각선,좌하단대각선)에 있는 좌표에다가 역시 1을 더한뒤 재귀호출 합니다.

• 이 때, 재귀호출에서 리턴된 뒤, 이전 상태에서 또 체크를 해야하므로 재귀호출에서 리턴하면 이전에 1을 더해주었던 자리에서 1을 빼줍니다.

• 루프특성상 오른쪽 및 아래쪽으로 진행하며 체크하므로,
  Queen이 진행할수 있는 방향을 표기하여 놓을 때,
  위쪽,왼쪽,좌상단대각선,우상단대각선 등은 표기하지 않았습니다

미리 감사드립니다 ~!

include

int c, N;
int sub(int sr, int sc, int now);
int board[12][12];

int main()
{
scanf("%d", &c);

for (int i=0; i<c; i++)
{
    scanf("%d", &N);
    for (int ii=0; ii<N; ii++) {
        for (int jj=0; jj<N; jj++) {
            board[ii][jj] = 0;
        }
    }
    printf("%d\n", sub(0, 0, 0));
}
return 0;

}

int sub(int sr, int sc, int now)
{
if (now == N) {return 1;}

int cnt=0;

for(int ii=sr; ii<N; ii++) {
    int c = (ii==sr)? sc: 0;
    for (int jj=c; jj <N; jj++) {
        if (board[ii][jj] == 0) { // available
            // there
            board[ii][jj] += 1;
            // right
            for (int kk=jj+1; kk<N; kk++) board[ii][kk] += 1;
            // down
            for (int kk=ii+1; kk<N; kk++)  board[kk][jj] += 1;
            // right-down
            for (int kk=1; kk<N; kk++) {
                if (ii+kk < N && jj+kk < N) board[ii+kk][jj+kk] += 1;
                else                        break;
            }
            // left-down
            for (int kk=1; kk<N; kk++) {
                if (ii+kk < N && jj-kk >=0) board[ii+kk][jj-kk] += 1;
                else                        break;
            }

            cnt += sub(ii+1, 0, now+1);

            // there
            board[ii][jj] -= 1;
            // right
            for (int kk=jj+1; kk<N; kk++) board[ii][kk] -= 1;
            // down
            for (int kk=ii+1; kk<N; kk++)  board[kk][jj] -= 1;
            // right-down
            for (int kk=1; kk<N; kk++) {
                if (ii+kk < N && jj+kk < N) board[ii+kk][jj+kk] -= 1;
                else                        break;
            }
            // left-down
            for (int kk=1; kk<N; kk++) {
                if (ii+kk < N && jj-kk >=0) board[ii+kk][jj-kk] -= 1;
                else                        break;
            }
        }
    }
}
return cnt;

}