(Leet Code JS)N-Queens

51. N-Queens

 

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle. You may return the answer in any order.

Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space, respectively.

 

Example 1:

Input: n = 4 Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]] Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above

Example 2:

Input: n = 1 Output: [["Q"]]

 

Constraints:

• 1 <= n <= 9

DFS와 백트랙킹을 이용한 문제 풀이.

우선 n x n 크기의 board와 답을 넣어주는 answer 배열을 선언한다.

 

isPossible() 함수는 현재 x, y 좌표에서 퀸을 놓을 수 있는지 확인하는 함수다.

dfs() 함수는 queen를 놓을 수 있는 모든 경우의 수를 찾는 함수다.

 

한 행(row)에 하나의 퀸만 놓을 수 있기 때문에 dfs()의 매개변수로 row와 놓을 수 있는 퀸의 갯수를 넘겨준다.

 

DFS():

매개변수로 받은 queen이 0개면 answer에 board를 넣어준다.

단, board는 계속 사용해야 하므로 slice()로 깊은 복사를 해준 뒤, join("")을 통해 답과 같은 형태로 push하면 된다.

 

for문으로 현재 x 좌표에서 column을 순회한다.

isPossible 함수를 통해 현재 순회하고 있는 x, y 좌표에 퀸을 놓을 수 있다면,

해당 좌표를 "Q"로 바꾼 후, DFS를 진행.

DFS가 끝나면 다시 "."으로 바꾼 후, 다른 경우의 수를 찾으면 된다.

const solveNQueens = (n) => {
    const answer = [];
    let board = Array.from({length: n}, () => Array(n).fill("."));
    
    const isPossible = (x, y) => {
        //up
        for(let i = x - 1; i >= 0; i--){
            if(board[i][y] === "Q"){
                return false;
            }
        }
        
        //down
        for(let i = x + 1; i < n; i++){
            if(board[i][y] === "Q"){
                return false;
            }
        }
        
        //left
        for(let i = y - 1; i >= 0; i--){
            if(board[x][i] === "Q"){
                return false;
            }
        }
        
        //right
        for(let i = y + 1; i < n; i++){
            if(board[x][i] === "Q"){
                return false;
            }
        }
        
        //upper left
        for(let i = x - 1, j = y - 1; i >= 0 && j >= 0; i--, j--){
            if(board[i][j] === "Q"){
                return false;
            }
        }
        
        //upper right
        for(let i = x - 1, j = y + 1; i >= 0 && j < n; i--, j++){
            if(board[i][j] === "Q"){
                return false;
            }
        }
        
        //lower left
        for(let i = x + 1, j = y - 1; i < n && j >= 0; i++, j--){
            if(board[i][j] === "Q"){
                return false;
            }
        }
        
        //lower right
        for(let i = x + 1, j = y + 1; i < n && j < n; i++, j++){
            if(board[i][j] === "Q"){
                return false;
            }
        }
        
        return true;
    }
    
    const dfs = (x, queen) => {
        if(!queen){
            answer.push(board.slice().map(b => b.join("")));
            return;
        }
        
        for(let j = 0; j < n; j++){
            if(isPossible(x, j)){
                board[x][j] = "Q";
                dfs(x + 1, queen - 1);
                board[x][j] = ".";
            }
        }
    };
    
    dfs(0, n);
    
    return answer;
};