voiddfs(int n, int currRow, vector<string>& queens, vector<vector<string>>& results){ if (currRow == n) { results.push_back(queens); return; }
for (int i = 0; i < n; ++i) { if (isValid(n, queens, currRow, i)) { queens[currRow][i] = 'Q'; dfs(n, currRow + 1, queens, results); queens[currRow][i] = '.'; } } }
// row, col: new queen's position boolisValid(int n, vector<string>& queens, int row, int col){ // check if queen on the same columns for (int i = 0; i < row; ++i) { if (queens[i][col] == 'Q') { returnfalse; } } // check if queen on left-top for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; --i, --j) { if (queens[i][j] == 'Q') { returnfalse; } } // check if queen on right-top for (int i = row - 1, j = col + 1; i >= 0 && j < n; --i, ++j) { if (queens[i][j] == 'Q') { returnfalse; } }
defdfs(self, n, currRow, queens, results): if currRow == n: results.append([''.join(i) for i in queens]) return for i inrange(n): if self.isValid(n, queens, currRow, i): queens[currRow][i] = 'Q' self.dfs(n, currRow + 1, queens, results) queens[currRow][i] = '.'
defisValid(self, n, queens, row, col): """ row, col: new queen's position """ # check if queen on the same columns for i inrange(row): if queens[i][col] == 'Q': returnFalse # check if queen on left-top i, j = row - 1, col - 1 while i >= 0and j >= 0: if queens[i][j] == 'Q': returnFalse i -= 1 j -= 1 # check if queen on right-top i, j = row - 1, col + 1 while i >= 0and j < n: if queens[i][j] == 'Q': returnFalse i -= 1 j += 1 returnTrue