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 좌표 값의 합이 같은 점들이다.