| 7 | return res |
| 8 | |
| 9 | def dfs(r: int, diagonals_set: Set[int], anti_diagonals_set: Set[int], cols_set: Set[int], n: int) -> None: |
| 10 | global res |
| 11 | # Termination condition: If we have reached the end of the rows, |
| 12 | # we've placed all 'n' queens. |
| 13 | if r == n: |
| 14 | res += 1 |
| 15 | return |
| 16 | for c in range(n): |
| 17 | curr_diagonal = r - c |
| 18 | curr_anti_diagonal = r + c |
| 19 | # If there are queens on the current column, diagonal or |
| 20 | # anti−diagonal, skip this square. |
| 21 | if (c in cols_set or curr_diagonal in diagonals_set or curr_anti_diagonal in anti_diagonals_set): |
| 22 | continue |
| 23 | # Place the queen by marking the current column, diagonal, and |
| 24 | # anti −diagonal as occupied. |
| 25 | cols_set.add(c) |
| 26 | diagonals_set.add(curr_diagonal) |
| 27 | anti_diagonals_set.add(curr_anti_diagonal) |
| 28 | # Recursively move to the next row to continue placing queens. |
| 29 | dfs(r + 1, diagonals_set, anti_diagonals_set, cols_set, n) |
| 30 | # Backtrack by removing the current column, diagonal, and |
| 31 | # anti −diagonal from the hash sets. |
| 32 | cols_set.remove(c) |
| 33 | diagonals_set.remove(curr_diagonal) |
| 34 | anti_diagonals_set.remove(curr_anti_diagonal) |