1+ package kotlin
2+
3+ class Solution {
4+ fun solveNQueens (n : Int ):List <List <String >> {
5+ if (n== 1 )return listOf (listOf (" Q"
6+ val resultantList= mutableListOf<List <String >>()
7+ val board= MutableList (n) {
8+ StringBuilder (" ."
9+ }
10+ val unavailableColumnPositions= hashSetOf<Int >()
11+ val unavailableLeftDiagonalPositions= hashSetOf<Int >()
12+ val unavailableRightDiagonalPositions= hashSetOf<Int >()
13+
14+ // Queens indexed from 0. ie : Q_0,Q_1,Q_2....Q_n
15+ @Suppress(" UnnecessaryVariable"
16+ fun dfs (nthQueen : Int = 0):Boolean {
17+ if (nthQueen== n) {
18+ val list= mutableListOf<String >()
19+ board.forEach { list.add(it.toString()) }
20+ resultantList.add(list)
21+ return false
22+ }
23+ // nthQueen needs to be inserted in the nth row. Therefore,
24+ // the parameter "nthQueen" can also be considered as the row
25+ // index.
26+ val row= nthQueen
27+ for (columnin 0 until n) {
28+ if (
29+ unavailableColumnPositions.contains(column)||
30+ unavailableLeftDiagonalPositions.contains(row- column)||
31+ unavailableRightDiagonalPositions.contains(row+ column)
32+ )continue
33+
34+ // place queen
35+ board[row][column]= ' Q'
36+ unavailableColumnPositions.add(column)
37+ unavailableLeftDiagonalPositions.add(row- column)
38+ unavailableRightDiagonalPositions.add(row+ column)
39+
40+ // try placing the next queen
41+ val isQueenPlaced= dfs(nthQueen+ 1 )
42+ if (isQueenPlaced)return true
43+
44+ // remove queen
45+ board[row][column]= ' .'
46+ unavailableColumnPositions.remove(column)
47+ unavailableLeftDiagonalPositions.remove(nthQueen- column)
48+ unavailableRightDiagonalPositions.remove(nthQueen+ column)
49+ }
50+ return false
51+ }
52+ dfs()
53+ return resultantList
54+ }
55+ }
