[LeetCode][Python3] 52. N-Queens II

Problem :

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

My Solution :

class Solution:

def totalNQueens(self, n):

def dfs(r):

if r == n:

self.ans += 1

return

for c in column:

if r+c not in up_right and r-c not in up_left:

column.remove(c)

up_right.add(r+c)

up_left.add(r-c)

dfs(r+1)

column.add(c)

up_right.remove(r+c)

up_left.remove(r-c)

self.ans = 0

up_left, up_right, column = set(), set(), set(range(n))

dfs(0)

return self.ans

Comment :

일단 체스의 퀸이 어떻게 움직일 수 있는지 알아야 한다. 가로, 세로, 대각선 모두 움직일 수 있다.

출처 : https://en.wikipedia.org/wiki/Queen_(chess)

좌상-우하 대각선은 x, y 좌표 값의 차가 같은 점들이고

우상-좌하 대각선은 x, y 좌표 값의 합이 같은 점들이다.