|
| 1 | +publicclassSolution{ |
| 2 | +publicIList<IList<string>>SolveNQueens(intn) |
| 3 | +{ |
| 4 | +varresult=newList<IList<string>>(); |
| 5 | +IList<StringBuilder>board=newList<StringBuilder>(); |
| 6 | +for(inti=0;i<n;i++) |
| 7 | +{ |
| 8 | +board.Add(newStringBuilder(n)); |
| 9 | +board[i].Append('.',n); |
| 10 | + |
| 11 | +} |
| 12 | +backtrackingNQueens(n,0,board,result,newHashSet<(inti,intj)>(),newHashSet<(inti,intj)>(),newHashSet<(inti,intj)>()); |
| 13 | +returnresult; |
| 14 | +} |
| 15 | + |
| 16 | +privatevoidbacktrackingNQueens(intn,introw,IList<StringBuilder>board,List<IList<string>>result,HashSet<(inti,intj)>col,HashSet<(inti,intj)>positiveDiag,HashSet<(inti,intj)>negativeDiag) |
| 17 | +{ |
| 18 | +if(n==0) |
| 19 | +{ |
| 20 | +result.Add(board.Select(s=>s.ToString()).ToList()); |
| 21 | +return; |
| 22 | +} |
| 23 | +if(row==board.Count)return; |
| 24 | + |
| 25 | +for(intc=0;c<board.Count;c++) |
| 26 | +{ |
| 27 | +(inti,intj)column=(0,c); |
| 28 | +intm=Math.Min(row,c); |
| 29 | +(inti,intj)diag1=(row-m,c-m); |
| 30 | +m=Math.Min(row,board.Count-1-c); |
| 31 | +(inti,intj)diag2=(row-m,c+m); |
| 32 | + |
| 33 | +if(col.Contains(column)||positiveDiag.Contains(diag1)|| |
| 34 | +negativeDiag.Contains(diag2))continue; |
| 35 | + |
| 36 | +col.Add(column); |
| 37 | +positiveDiag.Add(diag1); |
| 38 | +negativeDiag.Add(diag2); |
| 39 | + |
| 40 | + |
| 41 | +board[row][c]='Q'; |
| 42 | +backtrackingNQueens(n-1,row+1,board,result,col,positiveDiag,negativeDiag); |
| 43 | + |
| 44 | +board[row][c]='.'; |
| 45 | +col.Remove(column); |
| 46 | +positiveDiag.Remove(diag1); |
| 47 | +negativeDiag.Remove(diag2); |
| 48 | +} |
| 49 | +} |
| 50 | + |
| 51 | +} |