0051-n-queens.cs

publicclassSolution{
publicIList<IList<string>>SolveNQueens(intn)
{
varresult=newList<IList<string>>();
IList<StringBuilder>board=newList<StringBuilder>();
for(inti=0;i<n;i++)
{
board.Add(newStringBuilder(n));
board[i].Append('.',n);

}
backtrackingNQueens(n,0,board,result,newHashSet<(inti,intj)>(),newHashSet<(inti,intj)>(),newHashSet<(inti,intj)>());
returnresult;
}

privatevoidbacktrackingNQueens(intn,introw,IList<StringBuilder>board,List<IList<string>>result,HashSet<(inti,intj)>col,HashSet<(inti,intj)>positiveDiag,HashSet<(inti,intj)>negativeDiag)
{
if(n==0)
{
result.Add(board.Select(s =>s.ToString()).ToList());
return;
}
if(row==board.Count)return;

for(intc=0;c<board.Count;c++)
{
(inti,intj)column=(0,c);
intm=Math.Min(row,c);
(inti,intj)diag1=(row-m,c-m);
m=Math.Min(row,board.Count-1-c);
(inti,intj)diag2=(row-m,c+m);

if(col.Contains(column)||positiveDiag.Contains(diag1)||
negativeDiag.Contains(diag2))continue;

col.Add(column);
positiveDiag.Add(diag1);
negativeDiag.Add(diag2);


board[row][c]='Q';
backtrackingNQueens(n-1,row+1,board,result,col,positiveDiag,negativeDiag);

board[row][c]='.';
col.Remove(column);
positiveDiag.Remove(diag1);
negativeDiag.Remove(diag2);
}
}

}