๐ง๐ป๐ป ์ฝ๋ฉํ
์คํธ/LeetCode
[LeetCode] 51. N-Queens (Python / JavaScript)
10000COW
2023. 1. 9. 16:09
728x90
LeetCode 51. N-Queens (Python / JavaScript)
https://leetcode.com/problems/n-queens/description/
N-Queens - LeetCode
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 solut
leetcode.com
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
}728x90