N Queen Problem – Pencil Programmer

What is N Queen Problem?

We are given N chess’s queens and is asked to place them in the chessboard of size NxN so that no two queens attack/eliminate each other.

A queen can only attack if another queen is either on:

Same Row
Same Column
Same Diagonal (left or right)

Example: For 4 Queens problem, we will have a 4×4 board. If a queen is placed at (2,2), then the places at which no queen can be placed is crossed by red line as shown in the figure:

N Queen Algorithm

Now the question is how to solve N Queen Problem?

There are two approaches to solve this problem:

Naive Algorithm

In this approach, we try the brute force method to find all possible solutions to the problem by randomly choosing the position.

while some configurations are unchecked
{
    Generate configuration of queen position
    if in current configuration queens don't attack
    {
        print the configuration
    }
}

while some configurations are unchecked

{

Generate configuration of queen position

if in current configuration queens don't attack

{

print the configuration

}

Backtracking Algorithm

In this approach, we place a queen in one column and then we proceed to the next column (since a single column cannot contain more than one queen). Then, we check the possible safe row to place next queen, so that we can proceed to the next column.

If there is no safe row in the current column, we go back to the previous column and change the queen’s position to the next possible safe row. If found any then we proceed to the next column again, else we go back further and repeat the same task.

If we reached the last column and found the possible safe position (i.e row), then we print the configuration of queens (i.e solution), else if we came back to the first column and none of the position (i.e row) is safe then we assume that there is no possible solution.

So, In backtracking, if no further solution is possible, we go one step back and proceed with next available option.

Check N-Queens Visualizer to get visual working of backtrack algorithm.

find_solution(row, column)
{
    if (column == lastColumn + 1)
    {
        passed all columns, therefore successfully found a solution;
        print board;
        return true;
    }
    else
    {
        for(all rows of column)
        {
            if([row, column] is safe for placing queen)
            {
                //place queen, i.e   
                board[row][column] = 1;
                
                //check for next column
                if(find_solution(0,column + 1))
                {
                    return true;
                }
                
                //No safe place in column+1, remove queen, i.e
                board[row][column] = 0;
            }
        
            move to next row
            
        }
        
        checked all rows of the column, no safe place;
        return false;
        
    }
}

find_solution(row, column)

{

if (column == lastColumn + 1)

{

passed all columns, therefore successfully found a solution;

print board;

return true;

}

else

{

for(all rows of column)

{

if([row, column] is safe for placing queen)

{

//place queen, i.e

board[row][column] = 1;

//check for next column

if(find_solution(0,column + 1))

{

return true;

}

//No safe place in column+1, remove queen, i.e

board[row][column] = 0;

}

move to next row

}

checked all rows of the column, no safe place;

return false;

}

N Queen in C|Java

This C program gives all possible safe configuration for N Queen Problem as output by giving the value of N during program execution.

C

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

int queens, count =0;
int chessBoard[20][20];

bool hasSolution(int,int);
bool isValidPlace(int , int);
void displayBoard();
void solveNqueen();
bool flag = false;


int main()
{
    //Enter value of N
    printf("Enter number of Queens \n");
    scanf("%d", &queens);
    solveNqueen();

    return 0;
}

void solveNqueen(){

    int i;
    //starting from (0,0) of the board
    hasSolution(0,0);

    //After running hasSolution() still flag == false
    //It means no Solution
    if(!flag)
        printf("No Solution \n");

}

//to reset value to 0
void reset(){
    int i, j;
    for(i=0; i<queens; i++){
        for(j=0; j<queens; j++){
            chessBoard[i][j] = 0;
            }
        }
}

//finding all solution by backtracking
//row == ctr
//column == colQueen
bool hasSolution(int ctr,int colQueen){

    //Reached beyond last column
    //Means solution (configuration) found
    if(colQueen == queens){
        flag = true;
        displayBoard();
        //intentionally returning false to find more possible solution
        return false;
    }

    int i,j;
    for(i=ctr; i<queens; i++){

        //checking if position is safe
        if(isValidPlace(i,colQueen)){
            //setting current value to 1 means placing a queen
            chessBoard[i][colQueen] = 1;
            //moving to next column's 1st row
            if(hasSolution(0,colQueen+1))
                return true;

            //backtrack
            //reset to 0 means removing queen
            chessBoard[i][colQueen] = 0;
        }

    }

    //When no row is safe in the current column
    return false;
}

//To check whether the particular position is safe or not
bool isValidPlace(int row, int col){
    int i,j;

    //Checking horizontally
    for(i=col; i>=0; i--){
        if(chessBoard[row][i] == 1)
            return false;
    }

    //checking left diagonal
    for(i=row, j=col; i>=0 && j>=0; i--,j--){
        if(chessBoard[i][j] == 1)
            return false;
    }

    //checking right diagonal
    for(i=row, j=col; i<queens && j>=0; i++,j--){
        if(chessBoard[i][j] == 1)
            return false;
    }

    return true;
}

//To display chess board with queen configuration
// In place of 1 we print *
// In place of 0 we print -
void displayBoard(){
    int i, j;
    for(i=0; i<queens; i++){
        for(j=0; j<queens; j++){
            if(chessBoard[i][j] == 1)
                printf(" * ");
            else
                printf(" - ");
        }
        printf("\n");
    }
     printf("\n");
     printf("\n");
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

#include <stdio.h>

#include <stdlib.h>

#include <stdbool.h>

int queens, count =0;

int chessBoard[20][20];

bool hasSolution(int,int);

bool isValidPlace(int , int);

void displayBoard();

void solveNqueen();

bool flag = false;

int main()

{

//Enter value of N

printf("Enter number of Queens \n");

scanf("%d", &queens);

solveNqueen();

return 0;

}

void solveNqueen(){

int i;

//starting from (0,0) of the board

hasSolution(0,0);

//After running hasSolution() still flag == false

//It means no Solution

if(!flag)

printf("No Solution \n");

}

//to reset value to 0

void reset(){

int i, j;

for(i=0; i<queens; i++){

for(j=0; j<queens; j++){

chessBoard[i][j] = 0;

}

//finding all solution by backtracking

//row == ctr

//column == colQueen

bool hasSolution(int ctr,int colQueen){

//Reached beyond last column

//Means solution (configuration) found

if(colQueen == queens){

flag = true;

displayBoard();

//intentionally returning false to find more possible solution

return false;

}

int i,j;

for(i=ctr; i<queens; i++){

//checking if position is safe

if(isValidPlace(i,colQueen)){

//setting current value to 1 means placing a queen

chessBoard[i][colQueen] = 1;

//moving to next column's 1st row

if(hasSolution(0,colQueen+1))

return true;

//backtrack

//reset to 0 means removing queen

chessBoard[i][colQueen] = 0;

}

//When no row is safe in the current column

return false;

}

//To check whether the particular position is safe or not

bool isValidPlace(int row, int col){

int i,j;

//Checking horizontally

for(i=col; i>=0; i--){

if(chessBoard[row][i] == 1)

return false;

}

//checking left diagonal

for(i=row, j=col; i>=0 && j>=0; i--,j--){

if(chessBoard[i][j] == 1)

return false;

}

//checking right diagonal

for(i=row, j=col; i<queens && j>=0; i++,j--){

if(chessBoard[i][j] == 1)

return false;

}

return true;

}

//To display chess board with queen configuration

// In place of 1 we print *

// In place of 0 we print -

void displayBoard(){

int i, j;

for(i=0; i<queens; i++){

for(j=0; j<queens; j++){

if(chessBoard[i][j] == 1)

printf(" * ");

else

printf(" - ");

}

printf("\n");

}

printf("\n");

}

Java

import java.util.Scanner;

public class Board {

    int chessBoard[][];
    int queens;

    public Board(int queens) {
        chessBoard = new int[20][20];
        this.queens = queens;
    }

    void displayBoard(){
        int i, j;
        for(i=0; i<queens; i++){
            for(j=0; j<queens; j++){
                if(chessBoard[i][j] == 1)
                    System.out.print(" * ");
                else
                    System.out.print(" - ");
            }
            System.out.print("\n");
        }
        System.out.print("\n");
        System.out.print("\n");
    }

    void reset(){
        for(int i=0; i<queens; i++){
            for(int j=0; j<queens; j++){
                chessBoard[i][j] = 0;
            }
        }
    }

    boolean isValidPlace(int row, int col){
        int i,j;

        //Checking horizontally
        for(i=col; i>=0; i--){
            if(chessBoard[row][i] == 1)
                return false;
        }

        //checking left diagonal
        for(i=row, j=col; i>=0 && j>=0; i--,j--){
            if(chessBoard[i][j] == 1)
                return false;
        }

        //checking right diagonal
        for(i=row, j=col; i<queens && j>=0; i++,j--){
            if(chessBoard[i][j] == 1)
                return false;
        }

        return true;
    }
}

public class NQueen {

    int queens;
    boolean flag;
    Board board;

    public NQueen(int queens) {
        this.flag = false;
        this.board = new Board(queens);;
        this.queens = queens;
    }

    void solveNqueen(){

        int i;
        //starting from (0,0) of the board
        hasSolution(0,0);

        //After running hasSolution() still flag == false
        //It means no Solution
        if(!flag)
            System.out.println("No Solution");

    }

    boolean hasSolution(int ctr, int colQueen){

        //Reached beyond last column
        //Means solution (configuration) found

        if(colQueen == queens){
            flag = true;
            board.displayBoard();
            //intentionally returning false to find more possible solution
            return false;
        }

        int i,j;
        for(i=ctr; i<queens; i++){

            //checking if position is safe
            if(board.isValidPlace(i,colQueen)){
                //setting current value to 1 means placing a queen
                board.chessBoard[i][colQueen] = 1;
                //moving to next column's 1st row
                if(hasSolution(0,colQueen+1))
                    return true;

                //backtrack
                //reset to 0 means removing queen
                board.chessBoard[i][colQueen] = 0;
            }

        }

        //When no row is safe in current column
        return false;
    }
}

public class App {

    static Scanner in = new Scanner(System.in);

    public static void main(String args[]){
        System.out.println("Enter number of Queens");
        int queens = in.nextInt();

        NQueen nQueen = new NQueen(queens);
        nQueen.solveNqueen();

    }
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

import java.util.Scanner;

public class Board {

int chessBoard[][];

int queens;

public Board(int queens) {

chessBoard = new int[20][20];

this.queens = queens;

}

void displayBoard(){

int i, j;

for(i=0; i<queens; i++){

for(j=0; j<queens; j++){

if(chessBoard[i][j] == 1)

System.out.print(" * ");

else

System.out.print(" - ");

}

System.out.print("\n");

}

System.out.print("\n");

}

void reset(){

for(int i=0; i<queens; i++){

for(int j=0; j<queens; j++){

chessBoard[i][j] = 0;

}

boolean isValidPlace(int row, int col){

int i,j;

//Checking horizontally

for(i=col; i>=0; i--){

if(chessBoard[row][i] == 1)

return false;

}

//checking left diagonal

for(i=row, j=col; i>=0 && j>=0; i--,j--){

if(chessBoard[i][j] == 1)

return false;

}

//checking right diagonal

for(i=row, j=col; i<queens && j>=0; i++,j--){

if(chessBoard[i][j] == 1)

return false;

}

return true;

}

public class NQueen {

int queens;

boolean flag;

Board board;

public NQueen(int queens) {

this.flag = false;

this.board = new Board(queens);;

this.queens = queens;

}

void solveNqueen(){

int i;

//starting from (0,0) of the board

hasSolution(0,0);

//After running hasSolution() still flag == false

//It means no Solution

if(!flag)

System.out.println("No Solution");

}

boolean hasSolution(int ctr, int colQueen){

//Reached beyond last column

//Means solution (configuration) found

if(colQueen == queens){

flag = true;

board.displayBoard();

//intentionally returning false to find more possible solution

return false;

}

int i,j;

for(i=ctr; i<queens; i++){

//checking if position is safe

if(board.isValidPlace(i,colQueen)){

//setting current value to 1 means placing a queen

board.chessBoard[i][colQueen] = 1;

//moving to next column's 1st row

if(hasSolution(0,colQueen+1))

return true;

//backtrack

//reset to 0 means removing queen

board.chessBoard[i][colQueen] = 0;

}

//When no row is safe in current column

return false;

}

public class App {

static Scanner in = new Scanner(System.in);

public static void main(String args[]){

System.out.println("Enter number of Queens");

int queens = in.nextInt();

NQueen nQueen = new NQueen(queens);

nQueen.solveNqueen();

}

Output

When N is 4:

There are total 92 safe configurations possible to place 8 queens in the 8×8 board, so it is not possible to show output here. Check the output yourself by giving the value of N during program execution. If you have any doubts then do comment below.

This Post Has 3 Comments

saurav rajput
23 Nov 2019 Reply
wow,so helpful
thank you so much for saving me.
saurav rajput
23 Nov 2019 Reply
one request sir
how to solve sum of subsets problem using backtracking.
please help 👨‍🦱
1. Adarsh Kumar
  23 Nov 2019 Reply
  Check out I have posted the solution of Subset problem.

What is N Queen Problem?

N Queen Algorithm

Naive Algorithm

Backtracking Algorithm

N Queen in C|Java

C

Java

This Post Has 3 Comments

saurav rajput

saurav rajput

Adarsh Kumar

Leave a Reply Cancel reply