N-Queens solution


  • 0
    L
    public class Solution
        {
            public List<List<string>> SolveNQueens(int n)
            {
                if (n <= 0)
                    return null;
                //IList<IList<string>> results;
                var results = new List<List<string>>();
                var queens = new List<int>(n);
                for (int i = 0; i < n; ++i)
                {
                    queens.Add(-1);
                }
                NQueens(n, 0, queens, results);
                return results;
            }
    
            private void NQueens(int n, int row, List<int> queens, List<List<string>> solutions)
            {
                if (row == n)
                {
                    var temp = new List<string>();
                    for (int i = 0; i < n; ++i)
                    {
                        var s = "";
                        for (int j = 0; j < n; ++j)
                        {
                            if (j == queens[i])
                                s += 'Q';
                            else
                                s += '.';
                        }
                        temp.Add(s);
                    }
                    solutions.Add(temp);
                    // InitQueens(queens, n);
                }
                else
                {
                    var mark = false;
                    int i = 0;
                    do
                    {
                        if (mark)
                        {
                            queens[row] = -1;
                        }
                        if (i < n && Check(queens, row, i))
                        {
                            queens[row] = i;
                            mark = true;
                            NQueens(n, row + 1, queens, solutions);
                        }
                        ++i;
                    } while (i <= n);
                }
            }
    
            private bool Check(List<int> queens, int row, int col)
            {
                for (int i = 0; i < queens.Count(); ++i)
                {
                    if (queens[i] == -1)
                        continue;
                    if (queens[i] == col || Math.Abs(i - row) == Math.Abs(col - queens[i]))
                        return false;
                }
                return true;
            }
    
            private void InitQueens(List<int> queens, int n)
            {
                queens.Clear();
                for (int i = 0; i < n; ++i)
                {
                    queens[i] = -1;
                }
            }
        }
    

Log in to reply
 

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