[LeetCode] 51. N-Queens (Python / JavaScript)

LeetCode 51. N-Queens (Python / JavaScript)

https://leetcode.com/problems/n-queens/description/

N-Queens - LeetCode

 

Python

def solveQueens(n):
    col = set()
    posDiag = set() # (r + c)
    negDiag = set() # (r - c)
    
    res = []
    board = [["ㅁ"] * n for i in range(n)]
    
    def backtrack(r):
        if r == n:
            copy = ["".join(row) for row in board]
            res.append(copy)
            print('res', res)
        
        for c in range(n):
            if c in col or (r+c) in posDiag or (r-c) in negDiag:
                continue
            
            col.add(c)
            posDiag.add(r+c)
            negDiag.add(r-c)
            board[r][c] = "Q"
            
            backtrack(r+1)
            
            col.remove(c)
            posDiag.remove(r + c)
            negDiag.remove(r - c)
            board[r][c] = "ㅁ"
            
    backtrack(0)
    return len(res)

 

JavaScript

function solveQueens(n){
    const cols = new Set();
    const posDig = new Set();
    const negDig = new Set();
    
    const res = []
    const board = [];
    for(let i=0; i < n; i++){
        board[i] = []
        for(let j=0; j < n; j++){
            board[i][j] = '.';
        }
    }
    
    function backTrack(r){
        if(r === n){
            for(let i=0; i<n; i++){
                res.push(board[i].join(''))
            }
            console.log(res);
        }
        
        for(let c=0; c < n; c++){
            if(cols.has(c) || posDig.has(r+c) || negDig.has(r-c)){
                    continue;
            }            
            else{
                cols.add(c);
                posDig.add(r+c);
                negDig.add(r-c);
                board[r][c] = "Q";
                
                backTrack(r+1);
                
                cols.delete(c);
                posDig.delete(r+c);
                negDig.delete(r-c);
                board[r][c] = "."
            }
        }
    }     
            
    
    backTrack(0)
    return res
}