순환(Recursion)의 응용(2), n queens problem

Design Recursion

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];
return-type queens(int level)
{
    if non-promising
        report failure and return;
    else ifsuccess
        report answer and return;
    else
        visit children recursively;    
}

• 매개변수 level은 현재 노드의 위치를 표현하고, 1번에서 level번째 말이 어디에 놓였는지
  전역변수 배열 cols로 표현하자.
  cols[i] = j는 i번 말이 (i행, j열)에 놓였음을 의미한다.

int[] cols = new int [N+1];
boolean queens( int level )
{
    if non-promising
        report failure and return;
    else ifsuccess
        report answer and return;
    else
        visit children recursively;    
}

• return-type은 일단 boolean(true or false)으로 지정하자
  즉, 성공이냐 실패냐를 반환한다.

int[] cols = new int [N+1];
boolean queens( int level )
{
    if (!promising(level))
        return false;
    else if success
        report answer and return;
    else
        visit children recursively;    
}

• 노드가 어떤 경우에 non-promising(꽝!)할까? 일단 이 문제는
  나중에 생각하자.

int[] cols = new int [N+1];
boolean queens(int level)
{
    if(!promising(level))
        return false;
    else if (level==N
        return true;
    else
        visit children recursively;    
}

• promising 테스트를 통과했다는 가정하에 level==N이면 모든 말이 놓였다는 의미이고 따라서 성공이다.

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;
}

• level+1번째 말을 각각의 열에 놓은 후 recursion을 호출한다.

Promising Test

boolean promising(int level)
{
    for (int i = 1; i < level; i++) {
        if (**cols\[i\] == cols\[level\]**) // 같은 열에 놓였는지 검사
            return false;
        else **if on the same diagonal** // 같은 대각선에 놓였는지 검사
            return false;
    }   
    return true;
}

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;
}

N-Queen problem 풀이

int [] cols = new int [N+1];
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;
}

Reference

• 인프런, "영리한 프로그래밍을 위한 알고리즘 강좌, 제2-3강 Recursion의 응용: "n queens problem",https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B0%95%EC%A2%8C/dashboard(2020.05.12)