BacktrackingNQueensSolver.cs

using System;
using System.Collections.Generic;

namespace Algorithms.Problems.NQueens
{
    public class BacktrackingNQueensSolver
    {
        /// <summary>
        ///     Solves N-Queen Problem given a n dimension chessboard and using backtracking with recursion algorithm.
        ///     If we find a dead-end within or current solution we go back and try another position for queen.
        /// </summary>
        /// <param name="n">Number of rows.</param>
        /// <returns>All solutions.</returns>
        public IEnumerable<bool[,]> BacktrackSolve(int n)
        {
            if (n < 0)
            {
                throw new ArgumentException(nameof(n));
            }

            return BacktrackSolve(new bool[n, n], 0);
        }

        private static IEnumerable<bool[,]> BacktrackSolve(bool[,] board, int col)
        {
            var solutions = col < board.GetLength(0) - 1
                ? HandleIntermediateColumn(board, col)
                : HandleLastColumn(board);
            return solutions;
        }

        private static IEnumerable<bool[,]> HandleIntermediateColumn(bool[,] board, int col)
        {
            // To start placing queens on possible spaces within the board.
            for (var i = 0; i < board.GetLength(0); i++)
            {
                if (CanPlace(board, i, col))
                {
                    board[i, col] = true;

                    foreach (var solution in BacktrackSolve(board, col + 1))
                    {
                        yield return solution;
                    }

                    board[i, col] = false;
                }
            }
        }

        private static IEnumerable<bool[,]> HandleLastColumn(bool[,] board)
        {
            var n = board.GetLength(0);
            for (var i = 0; i < n; i++)
            {
                if (CanPlace(board, i, n - 1))
                {
                    board[i, n - 1] = true;

                    yield return (bool[,])board.Clone();

                    board[i, n - 1] = false;
                }
            }
        }

        /// <summary>
        ///     Checks whether current queen can be placed in current position,
        ///     outside attacking range of another queen.
        /// </summary>
        /// <param name="board">Source board.</param>
        /// <param name="row">Row coordinate.</param>
        /// <param name="col">Col coordinate.</param>
        /// <returns>true if queen can be placed in given chessboard coordinates; false otherwise.</returns>
        private static bool CanPlace(bool[,] board, int row, int col)
        {
            // To check whether there are any queens on current row.
            for (var i = 0; i < col; i++)
            {
                if (board[row, i])
                {
                    return false;
                }
            }

            // To check diagonal attack top-left range.
            for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--)
            {
                if (board[i, j])
                {
                    return false;
                }
            }

            // To check diagonal attack bottom-left range.
            for (int i = row + 1, j = col - 1; j >= 0 && i < board.GetLength(0); i++, j--)
            {
                if (board[i, j])
                {
                    return false;
                }
            }

            // Return true if it can use position.
            return true;
        }
    }
}