N-Queen

int [] cols = new int[N+1];

return type queens(int level){

    if(non-promissing(level))
    	report failure and return;
    else if(level == N)
    	report answer and return;
    else
    	visit children recursively;
}

 

1. 현재 내가 도착한 노드한 꽝이라면(non-promissing())이면 - 실패
2. 내가 도착한 노드가 최종적 답이라면 - 성공
3. 다음 level에 내가 갈 수 있는 노드들을 가보자

int [] cols = new int[N+1];
boolean queens(int level) {

    if(!promising(level)
    	return false;
    else if (level == N)
    	return true;
     
    for(int i = 1; i <= N; i++){
    	cols[level+1] = i;
        if(queens(level+1))
            return true;
    }
    return false;
}

 

boolean promising(int level){

	for(int i = 1; i < level; i++){
    
    if(cols[i] == cols[level])
    	return false;
    else if (level - i == Math.abs(cols[level] - cols[i]) //같은 대각선에 놓였는지 검사
    	return false;
    }
    return true;
}

https://www.acmicpc.net/problem/9663