C# N-queen Simple solution ~600ms


  • 0
    public IList<IList<string>> SolveNQueens(int n) {
                var nqPos = new Dictionary<int, int>();
                IList<IList<string>> nqSlns = new List<IList<string>>();
                findAllNQSolutions(n, 0, nqPos, nqSlns);
                return nqSlns;
            }
            private static bool findAllNQSolutions(int n, int row, Dictionary<int, int> nqPos, IList<IList<string>> nqSlns)
            {
                if (n == row)
                {
                    var slList = new List<string>();
                    foreach (var kvNQ in nqPos)
                    {
                        var posString = new StringBuilder(new string('.',n));
                        posString[kvNQ.Value] = 'Q';
                        slList.Add(posString.ToString());
                    }
                    nqSlns.Add(slList);
                    return true;
                }
                for (int col = 0; col < n; col++)
                {
                    bool hasPlace = true;
                    foreach (var kvPos in nqPos)
                    {
                        if (col == kvPos.Value || row == kvPos.Key || (kvPos.Value - kvPos.Key) - (col - row) == 0 || (kvPos.Value + kvPos.Key) - (col + row) == 0)
                        {
                            hasPlace = false;
                            break;
                        }
                    }
                    if (hasPlace)
                    {
                        if (nqPos.Keys.Contains(row))
                            nqPos[row] = col;                    
                        else
                            nqPos.Add(row, col);                    
                        findAllNQSolutions(n, row + 1, nqPos, nqSlns);
                        nqPos.Remove(row);                    
                    }
                }
                return false;
            }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.