[재귀함수/backtracking] n queens problem

수도코드

return-type  queens( arguments){

 

    if non-promising

        report failure and return;

    else if success

        report answer and return;

    else

        visit children recursively;

}

int[] cols = new int [N+1]; // level마다 말이 놓여진 위치 표시

boolean queens( int level )
{
	if(!promising(level)){
    	return false;
    } else if (level = N){
    	for(int i=1; i<=N; i++)
        	System.out.println("(" + i + ", " + cols[i] + ")");
    	return true;
    } 
    
    for(int i=1; i<=N; i++){
    	cols[level+1] = i; // 다음 자리로 말을 옮김
        if(queens(level+1)) // 하나 더 놓은게 성공하면 성공
        	return true;
    }
    return false;  //아니면 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;
    }
}