Solving the N-Queens Problem

Introduction 

 
N-Queens is a tricky problem. To solve this problem efficiently, it requires knowing the backtracking algorithm. Basically, the problem is to place N queens on an NxN chessboard. So in this article, we will discuss how to solve the N-Queens problem using a backtracking algorithm.
 

Problem Statement

 
Given the number of queens n (more than 3), we need to return all valid possible positions of N queens, so that no queens can attack/clash each other on a chessboard, N x N. For example, for 4 queens (n = 4), there exists two solutions, such that in each chessboard position, no two queens can attack/clash each other, as shown in the figure below. If you consider N = 1, 2 & 3, there is no solution to this problem, hence N has to be greater than or equal to 4.
 

Solution

 
The most naive approach to this problem is to create an N x N chessboard and recursively try to place queens on it. If all the queens fit in the board, then it's a valid board. The interesting part of this algorithm is the placement of n queens. Firstly, queens can neither share the same row nor the same column. Then, we will try to avoid placing the queens on a spot that is already being attacked/clashed by the queens placed before. Finally, if we successfully place the n-th queen on the board, then we add the board as one of the solutions. Then comes the role of backtracking. By removing the previous queen, we try a new position for that queen to find a new solution. We can achieve backtracking by a shared object/state which is the chessboard and by a recursive method/function that places or removes queens and updates the chessboard. Here is a code sample for the solution of the N-Queens problem in C#:
  1. using System.Linq;  
  2. using System.Collections.Generic;  
  3.   
  4. namespace NQueens  
  5. {  
  6.     class Program  
  7.     {  
  8.         static void Main(string[] args)  
  9.         {  
  10.             NQueensProblem nQueen = new NQueensProblem(4);  
  11.             var result = nQueen.Solutions;  
  12.             //result has 2 solutions.  
  13.             ///solution 1: ["OQOO",  
  14.             ///             "OOOQ",  
  15.             ///             "QOOO",  
  16.             ///             "OOQO"]  
  17.             ///solution 2: ["OOQO",  
  18.             ///             "QOOO",  
  19.             ///             "OOOQ",  
  20.             ///             "OQOO"]  
  21.         }  
  22.     }  
  23.     class NQueensProblem  
  24.     {  
  25.         public List<List<string>> Solutions = new List<List<string>>();  
  26.         private List<List<int>> ChessBoard = new List<List<int>>();  
  27.         private readonly int TotalNumberOfQueens;      
  28.         public NQueensProblem(int numOfQueens)  
  29.         {  
  30.             TotalNumberOfQueens = numOfQueens;  
  31.             //create board schema  
  32.             for (int i = 0; i < TotalNumberOfQueens; i++)  
  33.             {  
  34.                 List<int> row = Enumerable.Repeat(0, TotalNumberOfQueens).ToList();  
  35.                 ChessBoard.Add(row);  
  36.             }  
  37.             //start placing queen  
  38.             TryPlaceQueen();  
  39.         }  
  40.         //try place 0th queen by default  
  41.         void TryPlaceQueen(int nthQueen = 0)  
  42.         {  
  43.             //check for out of range  
  44.             if (TotalNumberOfQueens <= nthQueen)  
  45.                 return;  
  46.   
  47.             //iterate over every cell  
  48.             for (int i = 0; i < TotalNumberOfQueens; i++)  
  49.             {  
  50.                 //skip when no more queen can be added to this board  
  51.                 if (ChessBoard[nthQueen][i] != 0)  
  52.                     continue;  
  53.   
  54.                 //place the queen and update board  
  55.                 ChessBoard[nthQueen][i] = -1;  
  56.                 UpdateBoard(nthQueen, i, 1);  
  57.   
  58.                 //this board is valid when last queen is added to last row  
  59.                 if (nthQueen == TotalNumberOfQueens - 1)  
  60.                     AddBoardToSolutions();  
  61.                 //try again adding more queens  
  62.                 else  
  63.                     TryPlaceQueen(nthQueen + 1);  
  64.   
  65.                 //remove the queen we just added  
  66.                 ChessBoard[nthQueen][i] = 0;  
  67.                 UpdateBoard(nthQueen, i, -1);  
  68.             }  
  69.         }  
  70.         void UpdateBoard(int i,  int j,  int value)  
  71.         {  
  72.             for (int k = 0; k < i; k++)  
  73.                 ChessBoard[k][j] += value;   
  74.   
  75.             //for down  
  76.             for (int k = i + 1; k < TotalNumberOfQueens; k++)  
  77.                 ChessBoard[k][j] += value;   
  78.   
  79.             //for left  
  80.             for (int k = 0; k < j; k++)  
  81.                 ChessBoard[i][k] += value;   
  82.   
  83.             //for Right  
  84.             for (int k = j + 1; k < TotalNumberOfQueens; k++)  
  85.                 ChessBoard[i][k] += value;   
  86.   
  87.             //for up-left  
  88.             for (int m = i - 1, n = j - 1; m >= 0 && n >= 0; m--, n--)  
  89.                 ChessBoard[m][n] += value;   
  90.   
  91.             //for up-right  
  92.             for (int m = i - 1, n = j + 1; m >= 0 && n < TotalNumberOfQueens; m--, n++)  
  93.                 ChessBoard[m][n] += value;   
  94.   
  95.             //for down-left  
  96.             for (int m = i + 1, n = j - 1; m < TotalNumberOfQueens && n >= 0; m++, n--)  
  97.                 ChessBoard[m][n] += value;  
  98.   
  99.             //for down-right  
  100.             for (int m = i + 1, n = j + 1; m < TotalNumberOfQueens && n < TotalNumberOfQueens; m++, n++)  
  101.                 ChessBoard[m][n] += value;   
  102.         }  
  103.         void AddBoardToSolutions()  
  104.         {  
  105.             List<string> newBoard = new List<string>();  
  106.             for (int k = 0; k < TotalNumberOfQueens; k++)  
  107.             {  
  108.                 string row = string.Empty;  
  109.                 for (int j = 0; j < TotalNumberOfQueens; j++)  
  110.                     row += ChessBoard[k][j] == -1 ? "Q" : "O";  
  111.                 newBoard.Add(row);  
  112.             }  
  113.             //add current board as a solution  
  114.             Solutions.Add(newBoard);  
  115.         }  
  116.     }  
  117. }