# 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>>();
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();
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)
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.         }
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";