| 6 | } |
| 7 | |
| 8 | fun dfs( |
| 9 | r: Int, |
| 10 | diagonalsSet: MutableSet<Int>, |
| 11 | antiDiagonalsSet: MutableSet<Int>, |
| 12 | colsSet: MutableSet<Int>, |
| 13 | n: Int, |
| 14 | res: MutableList<Int> |
| 15 | ) { |
| 16 | // Termination condition: If we have reached the end of the rows, |
| 17 | // we've placed all 'n' queens. |
| 18 | if (r == n) { |
| 19 | res[0] = res[0] + 1 |
| 20 | return |
| 21 | } |
| 22 | for (c in 0 until n) { |
| 23 | val currDiagonal = r - c |
| 24 | val currAntiDiagonal = r + c |
| 25 | // If there are queens on the current column, diagonal or |
| 26 | // anti−diagonal, skip this square. |
| 27 | if (c in colsSet || currDiagonal in diagonalsSet || currAntiDiagonal in antiDiagonalsSet) { |
| 28 | continue |
| 29 | } |
| 30 | // Place the queen by marking the current column, diagonal, and |
| 31 | // anti −diagonal as occupied. |
| 32 | colsSet.add(c) |
| 33 | diagonalsSet.add(currDiagonal) |
| 34 | antiDiagonalsSet.add(currAntiDiagonal) |
| 35 | // Recursively move to the next row to continue placing queens. |
| 36 | dfs(r + 1, diagonalsSet, antiDiagonalsSet, colsSet, n, res) |
| 37 | // Backtrack by removing the current column, diagonal, and |
| 38 | // anti −diagonal from the hash sets. |
| 39 | colsSet.remove(c) |
| 40 | diagonalsSet.remove(currDiagonal) |
| 41 | antiDiagonalsSet.remove(currAntiDiagonal) |
| 42 | } |
| 43 | } |