Solving the N-Queens Problem

In this blog, you will learn about 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#:

using System.Linq;
using System.Collections.Generic;

namespace NQueens
{
    class Program
    {
        static void Main(string[] args)
        {
            NQueensProblem nQueen = new NQueensProblem(4);
            var result = nQueen.Solutions;
            //result has 2 solutions.
            ///solution 1: ["OQOO",
            ///             "OOOQ",
            ///             "QOOO",
            ///             "OOQO"]
            ///solution 2: ["OOQO",
            ///             "QOOO",
            ///             "OOOQ",
            ///             "OQOO"]
        }
    }
    class NQueensProblem
    {
        public List<List<string>> Solutions = new List<List<string>>();
        private List<List<int>> ChessBoard = new List<List<int>>();
        private readonly int TotalNumberOfQueens;
        public NQueensProblem(int numOfQueens)
        {
            TotalNumberOfQueens = numOfQueens;
            //create board schema
            for (int i = 0; i < TotalNumberOfQueens; i++)
            {
                List<int> row = Enumerable.Repeat(0, TotalNumberOfQueens).ToList();
                ChessBoard.Add(row);
            }
            //start placing queen
            TryPlaceQueen();
        }
        //try place 0th queen by default
        void TryPlaceQueen(int nthQueen = 0)
        {
            //check for out of range
            if (TotalNumberOfQueens <= nthQueen)
                return;

            //iterate over every cell
            for (int i = 0; i < TotalNumberOfQueens; i++)
            {
                //skip when no more queen can be added to this board
                if (ChessBoard[nthQueen][i] != 0)
                    continue;

                //place the queen and update board
                ChessBoard[nthQueen][i] = -1;
                UpdateBoard(nthQueen, i, 1);

                //this board is valid when last queen is added to last row
                if (nthQueen == TotalNumberOfQueens - 1)
                    AddBoardToSolutions();
                //try again adding more queens
                else
                    TryPlaceQueen(nthQueen + 1);

                //remove the queen we just added
                ChessBoard[nthQueen][i] = 0;
                UpdateBoard(nthQueen, i, -1);
            }
        }
        void UpdateBoard(int i,  int j,  int value)
        {
            for (int k = 0; k < i; k++)
                ChessBoard[k][j] += value;

            //for down
            for (int k = i + 1; k < TotalNumberOfQueens; k++)
                ChessBoard[k][j] += value;

            //for left
            for (int k = 0; k < j; k++)
                ChessBoard[i][k] += value;

            //for Right
            for (int k = j + 1; k < TotalNumberOfQueens; k++)
                ChessBoard[i][k] += value;

            //for up-left
            for (int m = i - 1, n = j - 1; m >= 0 && n >= 0; m--, n--)
                ChessBoard[m][n] += value;

            //for up-right
            for (int m = i - 1, n = j + 1; m >= 0 && n < TotalNumberOfQueens; m--, n++)
                ChessBoard[m][n] += value;

            //for down-left
            for (int m = i + 1, n = j - 1; m < TotalNumberOfQueens && n >= 0; m++, n--)
                ChessBoard[m][n] += value;

            //for down-right
            for (int m = i + 1, n = j + 1; m < TotalNumberOfQueens && n < TotalNumberOfQueens; m++, n++)
                ChessBoard[m][n] += value;
        }
        void AddBoardToSolutions()
        {
            List<string> newBoard = new List<string>();
            for (int k = 0; k < TotalNumberOfQueens; k++)
            {
                string row = string.Empty;
                for (int j = 0; j < TotalNumberOfQueens; j++)
                    row += ChessBoard[k][j] == -1 ? "Q" : "O";
                newBoard.Add(row);
            }
            //add current board as a solution
            Solutions.Add(newBoard);
        }
    }
}