My Solution in C#


  • 0
    P
            /// <summary>
            /// Method to get the list of all the distinct result of possible solutions
            /// </summary>
            /// <param name="n">size of the board</param>
            /// <returns>list of possible distinct result</returns>
            public IList<IList<string>> SolveNQueens(int n)
            {
                IList<IList<string>> queenList = new List<IList<string>>();
                char[,] position = new char[n, n];
                if (n <= 0)
                    return queenList;
                Solve(position, n, 0, 0, queenList);
    
                return queenList;
            }
    
            /// <summary>
            /// Recursive method to be called to solve the problem step by step
            /// </summary>
            /// <param name="position">2D array to set the position of the Queens in 2D</param>
            /// <param name="n">size of the board</param>
            /// <param name="count">count of the queens placed on the board</param>
            /// <param name="row">current row number</param>
            /// <param name="lst">list of the solution to be populated</param>
            public void Solve(char[,] position, int n, int count, int row, IList<IList<string>> lst)
            {
                // if each row/column has a Queen
                if (count == n)
                {
                    // Save the positions of Queen in list.
                    AddToList(lst, position, n);
                    position = new char[n, n];
                    return;
                }
    
                for (int j = 0; j < n; j++)
                {
                    // check if this place is suitable to place the Queen
                    if (IsValid(position, n, row, j))
                    {
                        position[row, j] = 'Q';
                        count++;
                        // find place for next Queen in next row.
                        Solve(position, n, count, row + 1, lst);
                        count--;
                        position[row, j] = '.';
                    }
                }
            }
    
            /// <summary>
            /// Method to save the positions of the Queens in the list 
            /// </summary>
            /// <param name="lst">List of all possible solutions</param>
            /// <param name="position">2D array having Queen's position. 
            /// One of the possible solution.</param>
            /// <param name="n">size of the board</param>
            public void AddToList(IList<IList<string>> lst, char[,] position, int n)
            {
                List<string> posList = new List<string>();
    
                for (int i = 0; i < n; i++)
                {
                    string s = string.Empty;
    
                    for (int j = 0; j < n; j++)
                    {
                        if (position[i, j] == 'Q')
                        {
                            s += 'Q';
                        }
                        else
                        {
                            s += '.';
                        }
                    }
                    posList.Add(s);
                }
    
                lst.Add(posList);
            }
    
            /// <summary>
            /// Method to check if the selected row and column is suitable to place next Queen.
            /// </summary>
            /// <param name="arr">2D array having all Queens placed until now.</param>
            /// <param name="length">size of the board</param>
            /// <param name="row">row number</param>
            /// <param name="col">column number</param>
            /// <returns>true if place is valid</returns>
            public bool IsValid(char[,] arr, int length, int row, int col)
            {
                int i, j;
    
                // check Queen in row
                for (i = 0; i < length; i++)
                {
                    if (arr[row, i] == 'Q')
                        return false;
                }
    
                // check Queen in column
                for (i = 0; i < length; i++)
                {
                    if (arr[i, col] == 'Q')
                        return false;
                }
    
                // check top left to bottom right diagonal
                i = row;
                j = col;
                while (i > 0 && j > 0)
                {
                    i--;
                    j--;
                }
    
                while (i < length && j < length)
                {
                    if (arr[i, j] == 'Q')
                        return false;
                    i++;
                    j++;
                }
    
                // check bottom left to top right
                i = row;
                j = col;
                while (i < length - 1 && j > 0)
                {
                    i++;
                    j--;
                }
    
                while (i >= 0 && j < length)
                {
                    if (arr[i, j] == 'Q')
                        return false;
                    i--;
                    j++;
                }
    
                return true;
            }
    

Log in to reply
 

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