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;
  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;
  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;
  54. //place the queen and update board
  55. ChessBoard[nthQueen][i] = -1;
  56. UpdateBoard(nthQueen, i, 1);
  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);
  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;
  75. //for down
  76. for (int k = i + 1; k < TotalNumberOfQueens; k++)
  77. ChessBoard[k][j] += value;
  79. //for left
  80. for (int k = 0; k < j; k++)
  81. ChessBoard[i][k] += value;
  83. //for Right
  84. for (int k = j + 1; k < TotalNumberOfQueens; k++)
  85. ChessBoard[i][k] += value;
  87. //for up-left
  88. for (int m = i - 1, n = j - 1; m >= 0 && n >= 0; m--, n--)
  89. ChessBoard[m][n] += value;
  91. //for up-right
  92. for (int m = i - 1, n = j + 1; m >= 0 && n < TotalNumberOfQueens; m--, n++)
  93. ChessBoard[m][n] += value;
  95. //for down-left
  96. for (int m = i + 1, n = j - 1; m < TotalNumberOfQueens && n >= 0; m++, n--)
  97. ChessBoard[m][n] += value;
  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. }