Solving N-Queens Problem the C# Way

Problem Statement

• The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.
• Given an integer n, return all distinct solutions to the n-queens puzzle. You may return the answer in any order.
• Each solution contains a distinct board configuration of the n-queens' placement, where ‘Q’ and ‘.’ both indicate a queen and an empty space, respectively.

Intuition

The intuition for any recursive solution is

• There should be a parameter change in your recursive method so that the every call will get you closer to the base case. When you reach the leaf node, the specific path that you traversed to get to the base case will collectively construe a single solution.
• There should be a loop that will run through all possible combinations/solutions. When you try different combinations at any level, it allows you to explore multiple solutions for the problem.
• In addition to this, we need to keep track of the nodes visited so that when we are done exploring the solution, we don’t visit the same solution again.

There are certain cases where this happens naturally. e.g. a purely recursive call like a fibonacci snippet does not need to keep track of visited nodes.

Solution

The below code starts off with initializing the 2d-board. The recursive call parameters has the board, the size of the board and the hashsets to keep track of the visited nodes.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

    public IList<IList<string>> SolveNQueens(int n) {
        IList<IList<string>> result = new List<IList<string>>();
        string[,] board = new string[n,n];
        for(int r=0; r < n; r++)
        {
            for(int c=0; c < n; c++)
            {
                board[r, c] = ".";
            }
        }
        RecurSolveNQueens(board, n, 0, new HashSet<int>(), new HashSet<int>(), new HashSet<int>(), result);
        return result;
    }

Next step, is to write the recursion method.

• The base case is satisfied when the last column has the queen placed. At this point, we add the solution traversed to the list of all the solutions.
• The loop goes through all the cells and figures out if its safe to place the queen. In this process, we also mark the nodes as visited.
• We have hashsets that helps to determine whether the queen is placed diagonally or straight.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

   private void RecurSolveNQueens(string[,] board, int n, int col, HashSet<int> rowSet, HashSet<int> upperDiagSet, HashSet<int> lowerDiagSet, IList<IList<string>> result)
    {
        if(col >= n)
        {
            IList<string> combination = new List<string>();
            StringBuilder temp = new StringBuilder();
            for(int r = 0; r < n; r++)
            {
                for(int c = 0; c < n; c++)
                {
                    temp.Append(board[r, c]);
                }
                combination.Add(temp.ToString());
                temp.Clear();
            }
            result.Add(combination);
            return;
        }
        for(int row = 0; row < n; row++)
        {
            int upperDiagVal = row - col;
            int lowerDiagVal = row + col;

            if(rowSet.Contains(row) || upperDiagSet.Contains(upperDiagVal) || lowerDiagSet.Contains(lowerDiagVal))
            {
                continue;
            }
            rowSet.Add(row);
            upperDiagSet.Add(upperDiagVal);
            lowerDiagSet.Add(lowerDiagVal);
            board[row, col] = "Q";
            RecurSolveNQueens(board, n, col + 1, rowSet, upperDiagSet, lowerDiagSet, result);
            rowSet.Remove(row);
            upperDiagSet.Remove(upperDiagVal);
            lowerDiagSet.Remove(lowerDiagVal);
            board[row, col] = ".";
        }
    }

Refactoring all the for loops to LINQ

LINQ (Language-Integrated Query) provides query syntax similar to SQL that allows you to modify objects. LINQ provides both method syntax and query syntax which differs syntactically, but the functionality is the same.

 Enumerable.Repeat(".", 5).ToArray(); //creates a string array with 5 "."
 Enumerable.Range(0, 5).Select(_ => ".").ToArray(); //Also creates a string array with 5 "."

Now, we can use the combination of Enumerable.Repeat and Enumerable.Range to create a LINQ expression. In the below code, for each element of the range, an array of “.” is created. The sequence of arrays is now converted into array of arrays, creating a 2D array.

1
2
3

 var board =   Enumerable.Range(0, n)
    .Select(_ => Enumerable.Repeat(".", n).ToArray())
    .ToArray();

We also have another for loop that we can convert into LINQ expression. The below code creates a range and iterates through the range to create another range. For each cell in the board gets concatenated into a string.

1
2
3
4
5
6
7

combination = Enumerable.Range(0, n)
    .Select(r => Enumerable.Range(0, n)
        .Select(c => board[r][c])
        .Aggregate((a, b) => a + b))
    .ToList();
    
result.Add(combination);

Refactoring HashSets into alias

In C# 12, there is a new feature that allows you to declare complex data types into an alias.

using VisitedSets = (System.Collections.Generic.HashSet<int> row, 
                    System.Collections.Generic.HashSet<int> upperDiag, 
                    System.Collections.Generic.HashSet<int> lowerDiag);

using Values = (int row, int upperDiag, int lowerDiag);                   

Now rather than declaring three separated HashSets, we could declare it all as one single variable and use this to pass it in the methods.

   var visitedSets = new VisitedSets(
            new(),
            new(),
            new()
        );
    Values values = (row, row - col, row + col);

Now, we can move the logic to mark the nodes as visited and unvisited into its own methods. Rather than passing in so many parameters in the method, we succesfully refactored so that we can pass a collection of objects, in this case tuples.

  private static void MarkUnVisited(VisitedSets visitedSets, Values values)
  {
      visitedSets.row.Remove(values.row);
      visitedSets.upperDiag.Remove(values.lowerDiag);
      visitedSets.lowerDiag.Remove(values.upperDiag);
  }

  private static void MarkVisited(VisitedSets visitedSets, Values values)
  {
      visitedSets.row.Add(values.row);
      visitedSets.upperDiag.Add(values.upperDiag);
      visitedSets.lowerDiag.Add(values.lowerDiag);
  }

For full code before and after refactoring, please refer here: