Recursion - N Queens Problem

n queens problem

체스판에 퀸의 동선이 겹치지 않게 놓는 문제

백 트래킹

백 트래킹은 퇴각 검색이라고 해석되며 트리에서 내가 원하는 해를 검색하는 알고리즘인데

검색할 때 내가 원하지 않는 노드를 만나게 되면 그 노드와 자식들은 검색할 필요가 없으므로

그 노드의 부모로 퇴각한 후 다른 자식을 검사하러 간다

접근 방법

2차원 배열을 선언하고 시작하려 했지만 필요가 없었다

어짜피 한줄에 하나의 말만 놓이게 되기 때문에 인덱스가 행을 안의 값이 열을 나타내는 것

예를 들어 board[2] = 3 은 3번째 줄에 3번째 열에 퀸이 있는 것

board = [1,3,3,3]은 보드판으로 나타내면 아래와 같다

1 0 0 0
0 0 1 0
0 0 1 0
0 0 1 0

내가 푼 코드

나는 풀다가 포기하고 결국 영상을 끝까지 봤다..

베이스 케이스를 구현하지도 않고 시작했기 때문일까 갈피를 못 잡고 흐지부지..

노드의 유망성 검사도 제대로 이해하지 못해서 promising도 맞추질 못했다

코드 구현

function promising(level) {

    for(let i=0; i<level;i++){
        if(board[i] === board[level]) return false;

        if(level - i === Math.abs(board[i]-board[level])) return false;
    }

    return true;
}

function queen(level) {
    if (!promising(level-1)) return false;
    if (level === n) return true;

    for (let i = 1; i <= n; i++) {
        board[level] = i;
        if (queen(level + 1)) return true;
    }
    return false;
}

---

    if (!promising(level-1)) return false;
    if (level === n) return true;

두개의 베이스 케이스

하나는 노드의 유망성을 검사해 유망하지 않으면 백, 다른 하나는 백 하지 않고 끝까지 가서 퀸들을 모두 놓았을 때 true를 반환하게 했다

    for(let i=0; i<level;i++){
        if(board[i] === board[level]) return false;

        if(level - i === Math.abs(board[i]-board[level])) return false;
    }

유망성 검사 코드

이전에 놓았던 말들의 위치와 가장 최근에 놓은 말의 위치를 비교해서

if(board[i] === board[level]) return false;

직선상에 있는지

    if(level - i === Math.abs(board[i]-board[level])) return false;

대각선상에 있는지

검사하는 코드이다

    for (let i = 1; i <= n; i++) {
        board[level] = i;
        if (queen(level + 1)) return true;
    }

현재 level에 말을 놔둔 후 level에 +1을 한 뒤 재귀호출하는 부분