Algotree > Algorithms > Backtracking > Solving N Queens Problem Using Backtracking

Solving N Queens Problem Using Backtracking

NQueens

N Queens problem : Place N queens on a chessboard of dimension N x N, such that no two queens attack each other.
Consider the chessboards of size 4, the board on the left side is valid in which no two queens can attack each other; whereas the board on the right is invalid.

N Queens placement idea :
a) Start by placing the queen starting from the 0’th column of the chessboard.
b) For every column, try placing the queen from the 0’th row of the chessboard such that it does not attack any of the already placed queens.

For every possible valid placement of the queen on the chessboard the next empty column is selected. Thus, while checking if a queen on a ( row, column ) is correctly placed we check only the left side of the current column. i.e

We check if there is a queen on the left in the row.
We check if there is a queen on the upper diagonal.
We check if there is a queen on the lower diagonal.

Backtracking
If for a selected column, a queen cannot be placed in the current row, we try to place it in the next row. If the queen cannot be placed in any of the rows of the selected column, we backtrack, and try to place the earlier queen in the next row before trying to place the current queen again.

Algorithm : N Queens

bool IsBoardOk ( chessboard, row R, column C ) {

If there is a queen Q positioned to the left of column C in row R, then
return False;

If there is queen Q positioned on the upper left diagonal, then
return false;

If there is queen Q positioned on the lower left diagonal, then
return false;

return true;
}

PlaceNQueens ( chessboard, column )

a) If the chessboard size equals column number ( chessboard.size() == column )
    All the queens are correctly placed on the chessboard. Display the chessboard.

b) Else try placing the queen on each row of the column and check if the chessboard remains valid.
    for ( row = 0; row < chessboard.size(); row++ )
        Place the queen Q at position [ row ] [ column ] and check if the chessboard remains valid
        chessboard [ row ] [ column ] = ’ Q ‘
        Check if ( IsBoardOk ( chessboard, row, column ) == true ) {
            Try placing another queen Q in the next column.
            PlaceNQueens ( chessboard, column + 1 ) ;
        }
        Chessboard was not valid. Revert
        chessboard [ row ] [ column ] = ’ . ‘

Time complexity of N queens algorithm : For finding a single solution where the first queen Q has been assigned the first column and can be put on N positions, the second queen has been assigned the second column and would choose from N-1 possible positions and so on; the time complexity is O ( N ) * ( N - 1 ) * ( N - 2 ) * … 1 ). i.e The worst-case time complexity is O ( N! ).
Thus, for finding all the solutions to the N Queens problem the time complexity runs in polynomial time.

Implementation of N Queens problem using backtracking

from typing import List # For annotations

boardcnt = 0

def IsBoardOk (chessboard : List, row : int, col : int) :

   # Check if there is a queen 'Q' positioned to the left of column col on the same row.
   for c in range(col) :
       if (chessboard[row][c] == 'Q') :
           return False

   # Check if there is queen 'Q' positioned on the upper left diagonal
   for r, c in zip(range(row-1, -1, -1), range(col-1, -1, -1)) :
       if (chessboard[r][c] == 'Q') :
           return False

   # Check if there is queen 'Q' positioned on the lower left diagonal
   for r, c in zip(range(row+1, len(chessboard), 1), range(col-1, -1, -1)) :
      if (chessboard[r][c] == 'Q') :
          return False

   return True

def DisplayBoard (chessboard : List) :

    for row in chessboard :
        print(row)

def PlaceNQueens (chessboard : List, col : int) :

    # If all the columns have a queen 'Q', a solution has been found.
    global boardcnt

    if (col >= len(chessboard)) :

        boardcnt += 1
        print("Board " + str(boardcnt))
        print("==========================")
        DisplayBoard(chessboard)
        print("==========================\n")

    else :

        # Else try placing the queen on each row of the column and check if the chessboard remains OK.
        for row in range(len(chessboard)) :

            chessboard[row][col] = 'Q'

            if (IsBoardOk(chessboard, row, col) == True) :
                # Chess board was OK, hence try placing the queen 'Q' in the next column.
                PlaceNQueens(chessboard, col + 1)

            chessboard[row][col] = '.'; # As previously placed queen was not valid, restore '.'

def main() :

   chessboard = []
   N = int(input("Enter chessboard size : "))

   for i in range(N) :
       row = ["."] * N
       chessboard.append(row)

   # Start placing the queen 'Q' from the 0'th column.
   PlaceNQueens(chessboard, 0)

if __name__ == "__main__" :
    main()

Output

Enter chessboard size : 4
Board 1
==========================
['.', '.', 'Q', '.']
['Q', '.', '.', '.']
['.', '.', '.', 'Q']
['.', 'Q', '.', '.']
==========================

Board 2
==========================
['.', 'Q', '.', '.']
['.', '.', '.', 'Q']
['Q', '.', '.', '.']
['.', '.', 'Q', '.']
==========================

Enter chessboard size : 5
Board 1
==========================
['Q', '.', '.', '.', '.']
['.', '.', '.', 'Q', '.']
['.', 'Q', '.', '.', '.']
['.', '.', '.', '.', 'Q']
['.', '.', 'Q', '.', '.']
==========================

Board 2
==========================
['Q', '.', '.', '.', '.']
['.', '.', 'Q', '.', '.']
['.', '.', '.', '.', 'Q']
['.', 'Q', '.', '.', '.']
['.', '.', '.', 'Q', '.']
==========================

Board 3
==========================
['.', '.', 'Q', '.', '.']
['Q', '.', '.', '.', '.']
['.', '.', '.', 'Q', '.']
['.', 'Q', '.', '.', '.']
['.', '.', '.', '.', 'Q']
==========================

Board 4
==========================
['.', '.', '.', 'Q', '.']
['Q', '.', '.', '.', '.']
['.', '.', 'Q', '.', '.']
['.', '.', '.', '.', 'Q']
['.', 'Q', '.', '.', '.']
==========================

Board 5
==========================
['.', 'Q', '.', '.', '.']
['.', '.', '.', 'Q', '.']
['Q', '.', '.', '.', '.']
['.', '.', 'Q', '.', '.']
['.', '.', '.', '.', 'Q']
==========================

Board 6
==========================
['.', '.', '.', '.', 'Q']
['.', '.', 'Q', '.', '.']
['Q', '.', '.', '.', '.']
['.', '.', '.', 'Q', '.']
['.', 'Q', '.', '.', '.']
==========================

Board 7
==========================
['.', 'Q', '.', '.', '.']
['.', '.', '.', '.', 'Q']
['.', '.', 'Q', '.', '.']
['Q', '.', '.', '.', '.']
['.', '.', '.', 'Q', '.']
==========================

Board 8
==========================
['.', '.', '.', '.', 'Q']
['.', 'Q', '.', '.', '.']
['.', '.', '.', 'Q', '.']
['Q', '.', '.', '.', '.']
['.', '.', 'Q', '.', '.']
==========================

Board 9
==========================
['.', '.', '.', 'Q', '.']
['.', 'Q', '.', '.', '.']
['.', '.', '.', '.', 'Q']
['.', '.', 'Q', '.', '.']
['Q', '.', '.', '.', '.']
==========================

Board 10
==========================
['.', '.', 'Q', '.', '.']
['.', '.', '.', '.', 'Q']
['.', 'Q', '.', '.', '.']
['.', '.', '.', 'Q', '.']
['Q', '.', '.', '.', '.']
==========================

#include<iostream>
#include<string>
#include<vector>

using namespace std;
int boardcnt = 0;

bool IsBoardOk (vector<string>& chessboard, int row, int col) {

   // Check if there is a queen 'Q' positioned to the left of column col 
   // on the same row.
   for (int c=0; c<col; c++) {
      if (chessboard[row][c] == 'Q') {
         return false;
      }
   }

   // Check if there is queen 'Q' positioned on the upper left diagonal
   for (int r=row-1, c=col-1; r >= 0 && c >= 0; r--, c--) {
      if (chessboard[r][c] == 'Q') {
         return false;
      }
   }

   // Check if there is queen 'Q' positioned on the lower left diagonal
   for (int r=row+1, c=col-1; c >= 0 && r<chessboard.size(); r++, c--) {
      if (chessboard[r][c] == 'Q') {
         return false;
      }
   }

   return true;
}

void DisplayBoard (vector<string>& chessboard) {
   for (auto& row : chessboard) {
       for(auto& ch : row) {
           cout << ch << " ";
       } cout << endl;
   }
}


void PlaceNQueens (vector<string>& chessboard, int col) {

    // If all the columns have a queen 'Q', a solution has been found.
    if (col >= chessboard.size()) {
        cout << endl << "Board " << ++boardcnt << endl;
        cout << "========================" << endl;
        DisplayBoard(chessboard);
        cout << "========================" << endl;

    }  else {

        // Else try placing the queen on each row of the column and check if the chessboard remains OK.
        for (int row=0; row<chessboard.size(); row++) {

            chessboard[row][col] = 'Q';

            if (IsBoardOk(chessboard, row, col) == true) {
                //Chess board was OK, hence try placing the queen 'Q' in the next column.
                PlaceNQueens(chessboard, col + 1);
            }

            chessboard[row][col] = '.'; // As previously placed queen was not valid, restore '.'
        }
    }
}

int main() {

   vector<string> chessboard;
   int N;

   cout << "Enter chessboard size : ";
   cin >> N;

   for(int i=0; i<N; i++) {
       string row(".", N);
       chessboard.push_back(row);
   }

   // Start placing the queen 'Q' from the 0'th column.
   PlaceNQueens(chessboard, 0);

   return 0;
}

Output

Enter chessboard size : 1

Board 1
========================
Q 
========================

Enter chessboard size : 4

Board 1
========================
. . Q . 
Q . . . 
. . . Q 
. Q . . 
========================

Board 2
========================
. Q . . 
. . . Q 
Q . . . 
. . Q . 
========================

import java.util.Scanner;

class NQueens {

    private int boardcnt = 0;

    boolean IsBoardOk (char chessboard[][], int row, int col) {

       // Check if there is a queen 'Q' positioned to the left of column col 
       // on the same row.
       for (int c=0; c<col; c++) {
          if (chessboard[row][c] == 'Q') {
             return false;
          }
       }

       // Check if there is queen 'Q' positioned on the upper left diagonal
       for (int r=row-1, c=col-1; r >= 0 && c >= 0; r--, c--) {
          if (chessboard[r][c] == 'Q') {
             return false;
          }
       }

       // Check if there is queen 'Q' positioned on the lower left diagonal
       for (int r=row+1, c=col-1; c >= 0 && r<chessboard.length; r++, c--) {
          if (chessboard[r][c] == 'Q') {
             return false;
          }
       }

       return true;
    }

    void DisplayBoard (char chessboard[][]) {

        for (int r=0; r<chessboard.length; r++) {
            for (int c=0; c<chessboard.length; c++) {
                System.out.print(chessboard[r][c]+" ");
            } System.out.println();
        }
    }

    void PlaceNQueens (char chessboard[][], int col) {

        // If all the columns have a queen 'Q', a solution has been found.
        if (col >= chessboard.length) {
            ++boardcnt;
            System.out.println("Board "+boardcnt);
            System.out.println("========================");
            DisplayBoard(chessboard);
            System.out.println("========================");

        } else {
            // Else try placing the queen on each row of the column and check if the chessboard remains OK.
            for (int row=0; row<chessboard.length; row++) {

                chessboard[row][col] = 'Q';

                if (IsBoardOk(chessboard, row, col) == true) {
                    //Chess board was OK, hence try placing the queen 'Q' in the next column.
                    PlaceNQueens(chessboard, col + 1);
                }
                chessboard[row][col] = '.'; // As previously placed queen was not valid, restore '.'
            }
        }
    }

    public static void main(String args[]) {

       int N;

       Scanner obj_scanner = new Scanner(System.in);  // Create a Scanner object
       System.out.print("Enter chessboard size : ");

       N = obj_scanner.nextInt();  // Get user input

       char chessboard[][] = new char[N][N];

       for (int r=0; r<N; r++) {
           for (int c=0; c<N; c++) {
               chessboard[r][c] = '.';
           }
       }

       NQueens obj = new NQueens();

       // Start placing the queen 'Q' from the 0'th column.
       obj.PlaceNQueens(chessboard, 0);
    }
}

Output

Enter chessboard size : 4
Board 1
========================
. . Q . 
Q . . . 
. . . Q 
. Q . . 
========================
Board 2
========================
. Q . . 
. . . Q 
Q . . . 
. . Q . 
========================

Enter chessboard size : 5
Board 1
========================
Q . . . . 
. . . Q . 
. Q . . . 
. . . . Q 
. . Q . . 
========================
Board 2
========================
Q . . . . 
. . Q . . 
. . . . Q 
. Q . . . 
. . . Q . 
========================
Board 3
========================
. . Q . . 
Q . . . . 
. . . Q . 
. Q . . . 
. . . . Q 
========================
Board 4
========================
. . . Q . 
Q . . . . 
. . Q . . 
. . . . Q 
. Q . . . 
========================
Board 5
========================
. Q . . . 
. . . Q . 
Q . . . . 
. . Q . . 
. . . . Q 
========================
Board 6
========================
. . . . Q 
. . Q . . 
Q . . . . 
. . . Q . 
. Q . . . 
========================
Board 7
========================
. Q . . . 
. . . . Q 
. . Q . . 
Q . . . . 
. . . Q . 
========================
Board 8
========================
. . . . Q 
. Q . . . 
. . . Q . 
Q . . . . 
. . Q . . 
========================
Board 9
========================
. . . Q . 
. Q . . . 
. . . . Q 
. . Q . . 
Q . . . . 
========================
Board 10
========================
. . Q . . 
. . . . Q 
. Q . . . 
. . . Q . 
Q . . . . 
========================