Posted on by Kalkicode
Code Backtracking

# Print all solutions in N-Queen Problem

The N-Queen Problem is a classic puzzle that involves placing N chess queens on an N×N chessboard in such a way that no two queens threaten each other. In other words, no two queens can be placed on the same row, column, or diagonal. This problem is a challenging task for computer scientists, mathematicians, and enthusiasts alike due to its complex nature.

The N-Queen Problem is a popular example of a combinatorial optimization problem, which requires finding the best arrangement of objects from a finite set of possibilities. In this case, the objects are the queens, and the possibilities are the squares on the chessboard. The goal is to find a solution that satisfies the constraints of the problem while minimizing some measure of the quality of the solution, such as the number of moves required or the time taken to find the solution.

Various algorithms have been developed to solve the N-Queen Problem, including exhaustive search, backtracking, and heuristics-based methods. The exhaustive search method involves testing all possible arrangements of queens on the board until a valid solution is found. This method is simple to understand but can become computationally infeasible for larger values of N.

Backtracking is another algorithmic technique used to solve the N-Queen Problem. It works by starting with a partial solution and then incrementally adding queens to the board until a complete solution is found. If an invalid configuration is encountered, the algorithm backtracks to the previous step and tries a different arrangement. Backtracking is more efficient than exhaustive search, but it can still be slow for large values of N.

Given a chess board of [8 X 8] size. Our goal is to setup 8 queen into this chess board where there are every queen free and not intersect to other queen.

In above is one solution of n queue. Similar way print all possible solution.

The N-Queen problem is a classic computer science problem that involves placing N queens on an N×N chessboard, such that no two queens threaten each other. In other words, no two queens should be in the same row, column, or diagonal. The goal is to find all possible configurations of the queens on the chessboard that satisfy these conditions.

## Problem Statement

Given an N×N chessboard, we need to find all possible arrangements of N queens such that no two queens threaten each other. For example, let's consider the 8-queens problem, where we need to place 8 queens on an 8×8 chessboard. The objective is to find all possible ways to place the queens so that no two queens can attack each other.

## Example

To understand the problem better, let's take an example with a smaller chessboard of size 4×4.

```- Q - -
- - - Q
Q - - -
- - Q -
```

In this example, we have successfully placed 4 queens on the chessboard in such a way that no two queens threaten each other. There are two possible solutions to the 4-queens problem.

## Pseudocode Algorithm

To solve the N-Queen problem, we can use a backtracking algorithm. The algorithm works as follows:

2. For each row, try to place a queen in each column.
3. If placing a queen in the current position is valid, move to the next row and repeat step 2.
4. If all rows are filled, we have found a valid solution. Print the chessboard.
5. If placing a queen is not valid, backtrack to the previous row and try the next column.
6. Continue this process until all possible solutions are found.

The algorithm recursively explores all possible configurations of the queens until a valid solution is found or all possibilities are exhausted.

## Code Solution

``````/*
C Program
+ print all solutions in N-Queen Problem
*/
#include <stdio.h>
//Queen size
#define SIZE 8
//Use to count number of result
int counter=0;

//Check valid element to insert a new n-queen element
int location(char result[SIZE][SIZE],int row,int col)
{

int status=1;
//Check element in row and column
for (int i = 0; i < SIZE && status==1; ++i)
{

if(result[row][i]=='Q' || result[i][col]=='Q')
{
//When element are exist
status=0;
}
}

//Compare by diagonal element
for (int i = 0,j=row,k=col; i <SIZE && status==1 ; ++i)
{
//Check condition of diagonal element
//top left
//bottom right
//bottom left
//top right
if(
(j-i>=0 && k-i>=0 && result[j-i][k-i]=='Q')
||
(j+i)<SIZE && (k+i) < SIZE && result[j+i][k+i]=='Q'
||
(j-i>=0 && k+i<SIZE && result[j-i][k+i]=='Q')
||
(j+i<SIZE && k-i>=0 && result[j+i][k-i]=='Q')
)
{
status=0;
}

}

return status;
}
void show_data(char result[SIZE][SIZE])
{
for (int i = 0; i < SIZE; ++i)
{
for (int j = 0; j < SIZE; ++j)
{
printf("%3c",result[i][j] );
}
printf("\n");
}
printf("\n\n");
}
void n_queen(char result[SIZE][SIZE], int row)
{

if(row>SIZE || row<0)
{
return;
}
if(row==SIZE)
{
counter++;
//Display queen result
show_data(result);

}
else
{
for (int i = 0; i < SIZE; ++i)
{

if(location(result,row,i)==1)
{
//When valid to insert Queen element
result[row][i]='Q';

n_queen(result,row+1);

//set the initial value
result[row][i]='-';
}
}
}
}
void defualt_value(char result[SIZE][SIZE])
{
//Set initial value
for (int i = 0; i < SIZE; ++i)
{
for (int j = 0; j < SIZE; ++j)
{
result[i][j]='-';
}
}
}
int main(){

char result[SIZE][SIZE];

defualt_value(result);

n_queen(result,0);

printf("\n Total N Queue %d\n",counter );
return 0;
}```
```

#### Output

``````  Q  -  -  -  -  -  -  -
-  -  -  -  Q  -  -  -
-  -  -  -  -  -  -  Q
-  -  -  -  -  Q  -  -
-  -  Q  -  -  -  -  -
-  -  -  -  -  -  Q  -
-  Q  -  -  -  -  -  -
-  -  -  Q  -  -  -  -

Q  -  -  -  -  -  -  -
-  -  -  -  -  Q  -  -
-  -  -  -  -  -  -  Q
-  -  Q  -  -  -  -  -
-  -  -  -  -  -  Q  -
-  -  -  Q  -  -  -  -
-  Q  -  -  -  -  -  -
-  -  -  -  Q  -  -  -

Q  -  -  -  -  -  -  -
-  -  -  -  -  -  Q  -
-  -  -  Q  -  -  -  -
-  -  -  -  -  Q  -  -
-  -  -  -  -  -  -  Q
-  Q  -  -  -  -  -  -
-  -  -  -  Q  -  -  -
-  -  Q  -  -  -  -  -

Q  -  -  -  -  -  -  -
-  -  -  -  -  -  Q  -
-  -  -  -  Q  -  -  -
-  -  -  -  -  -  -  Q
-  Q  -  -  -  -  -  -
-  -  -  Q  -  -  -  -
-  -  -  -  -  Q  -  -
-  -  Q  -  -  -  -  -

-  Q  -  -  -  -  -  -
-  -  -  Q  -  -  -  -
-  -  -  -  -  Q  -  -
-  -  -  -  -  -  -  Q
-  -  Q  -  -  -  -  -
Q  -  -  -  -  -  -  -
-  -  -  -  -  -  Q  -
-  -  -  -  Q  -  -  -

-  Q  -  -  -  -  -  -
-  -  -  -  Q  -  -  -
-  -  -  -  -  -  Q  -
Q  -  -  -  -  -  -  -
-  -  Q  -  -  -  -  -
-  -  -  -  -  -  -  Q
-  -  -  -  -  Q  -  -
-  -  -  Q  -  -  -  -

-  Q  -  -  -  -  -  -
-  -  -  -  Q  -  -  -
-  -  -  -  -  -  Q  -
-  -  -  Q  -  -  -  -
Q  -  -  -  -  -  -  -
-  -  -  -  -  -  -  Q
-  -  -  -  -  Q  -  -
-  -  Q  -  -  -  -  -

-  Q  -  -  -  -  -  -
-  -  -  -  -  Q  -  -
Q  -  -  -  -  -  -  -
-  -  -  -  -  -  Q  -
-  -  -  Q  -  -  -  -
-  -  -  -  -  -  -  Q
-  -  Q  -  -  -  -  -
-  -  -  -  Q  -  -  -

-  Q  -  -  -  -  -  -
-  -  -  -  -  Q  -  -
-  -  -  -  -  -  -  Q
-  -  Q  -  -  -  -  -
Q  -  -  -  -  -  -  -
-  -  -  Q  -  -  -  -
-  -  -  -  -  -  Q  -
-  -  -  -  Q  -  -  -

-  Q  -  -  -  -  -  -
-  -  -  -  -  -  Q  -
-  -  Q  -  -  -  -  -
-  -  -  -  -  Q  -  -
-  -  -  -  -  -  -  Q
-  -  -  -  Q  -  -  -
Q  -  -  -  -  -  -  -
-  -  -  Q  -  -  -  -

-  Q  -  -  -  -  -  -
-  -  -  -  -  -  Q  -
-  -  -  -  Q  -  -  -
-  -  -  -  -  -  -  Q
Q  -  -  -  -  -  -  -
-  -  -  Q  -  -  -  -
-  -  -  -  -  Q  -  -
-  -  Q  -  -  -  -  -

-  Q  -  -  -  -  -  -
-  -  -  -  -  -  -  Q
-  -  -  -  -  Q  -  -
Q  -  -  -  -  -  -  -
-  -  Q  -  -  -  -  -
-  -  -  -  Q  -  -  -
-  -  -  -  -  -  Q  -
-  -  -  Q  -  -  -  -

-  -  Q  -  -  -  -  -
Q  -  -  -  -  -  -  -
-  -  -  -  -  -  Q  -
-  -  -  -  Q  -  -  -
-  -  -  -  -  -  -  Q
-  Q  -  -  -  -  -  -
-  -  -  Q  -  -  -  -
-  -  -  -  -  Q  -  -

-  -  Q  -  -  -  -  -
-  -  -  -  Q  -  -  -
-  Q  -  -  -  -  -  -
-  -  -  -  -  -  -  Q
Q  -  -  -  -  -  -  -
-  -  -  -  -  -  Q  -
-  -  -  Q  -  -  -  -
-  -  -  -  -  Q  -  -

-  -  Q  -  -  -  -  -
-  -  -  -  Q  -  -  -
-  Q  -  -  -  -  -  -
-  -  -  -  -  -  -  Q
-  -  -  -  -  Q  -  -
-  -  -  Q  -  -  -  -
-  -  -  -  -  -  Q  -
Q  -  -  -  -  -  -  -

-  -  Q  -  -  -  -  -
-  -  -  -  Q  -  -  -
-  -  -  -  -  -  Q  -
Q  -  -  -  -  -  -  -
-  -  -  Q  -  -  -  -
-  Q  -  -  -  -  -  -
-  -  -  -  -  -  -  Q
-  -  -  -  -  Q  -  -

-  -  Q  -  -  -  -  -
-  -  -  -  Q  -  -  -
-  -  -  -  -  -  -  Q
-  -  -  Q  -  -  -  -
Q  -  -  -  -  -  -  -
-  -  -  -  -  -  Q  -
-  Q  -  -  -  -  -  -
-  -  -  -  -  Q  -  -

-  -  Q  -  -  -  -  -
-  -  -  -  -  Q  -  -
-  Q  -  -  -  -  -  -
-  -  -  -  Q  -  -  -
-  -  -  -  -  -  -  Q
Q  -  -  -  -  -  -  -
-  -  -  -  -  -  Q  -
-  -  -  Q  -  -  -  -

-  -  Q  -  -  -  -  -
-  -  -  -  -  Q  -  -
-  Q  -  -  -  -  -  -
-  -  -  -  -  -  Q  -
Q  -  -  -  -  -  -  -
-  -  -  Q  -  -  -  -
-  -  -  -  -  -  -  Q
-  -  -  -  Q  -  -  -

-  -  Q  -  -  -  -  -
-  -  -  -  -  Q  -  -
-  Q  -  -  -  -  -  -
-  -  -  -  -  -  Q  -
-  -  -  -  Q  -  -  -
Q  -  -  -  -  -  -  -
-  -  -  -  -  -  -  Q
-  -  -  Q  -  -  -  -

-  -  Q  -  -  -  -  -
-  -  -  -  -  Q  -  -
-  -  -  Q  -  -  -  -
Q  -  -  -  -  -  -  -
-  -  -  -  -  -  -  Q
-  -  -  -  Q  -  -  -
-  -  -  -  -  -  Q  -
-  Q  -  -  -  -  -  -

-  -  Q  -  -  -  -  -
-  -  -  -  -  Q  -  -
-  -  -  Q  -  -  -  -
-  Q  -  -  -  -  -  -
-  -  -  -  -  -  -  Q
-  -  -  -  Q  -  -  -
-  -  -  -  -  -  Q  -
Q  -  -  -  -  -  -  -

-  -  Q  -  -  -  -  -
-  -  -  -  -  Q  -  -
-  -  -  -  -  -  -  Q
Q  -  -  -  -  -  -  -
-  -  -  Q  -  -  -  -
-  -  -  -  -  -  Q  -
-  -  -  -  Q  -  -  -
-  Q  -  -  -  -  -  -

-  -  Q  -  -  -  -  -
-  -  -  -  -  Q  -  -
-  -  -  -  -  -  -  Q
Q  -  -  -  -  -  -  -
-  -  -  -  Q  -  -  -
-  -  -  -  -  -  Q  -
-  Q  -  -  -  -  -  -
-  -  -  Q  -  -  -  -

-  -  Q  -  -  -  -  -
-  -  -  -  -  Q  -  -
-  -  -  -  -  -  -  Q
-  Q  -  -  -  -  -  -
-  -  -  Q  -  -  -  -
Q  -  -  -  -  -  -  -
-  -  -  -  -  -  Q  -
-  -  -  -  Q  -  -  -

-  -  Q  -  -  -  -  -
-  -  -  -  -  -  Q  -
-  Q  -  -  -  -  -  -
-  -  -  -  -  -  -  Q
-  -  -  -  Q  -  -  -
Q  -  -  -  -  -  -  -
-  -  -  Q  -  -  -  -
-  -  -  -  -  Q  -  -

-  -  Q  -  -  -  -  -
-  -  -  -  -  -  Q  -
-  Q  -  -  -  -  -  -
-  -  -  -  -  -  -  Q
-  -  -  -  -  Q  -  -
-  -  -  Q  -  -  -  -
Q  -  -  -  -  -  -  -
-  -  -  -  Q  -  -  -

-  -  Q  -  -  -  -  -
-  -  -  -  -  -  -  Q
-  -  -  Q  -  -  -  -
-  -  -  -  -  -  Q  -
Q  -  -  -  -  -  -  -
-  -  -  -  -  Q  -  -
-  Q  -  -  -  -  -  -
-  -  -  -  Q  -  -  -

-  -  -  Q  -  -  -  -
Q  -  -  -  -  -  -  -
-  -  -  -  Q  -  -  -
-  -  -  -  -  -  -  Q
-  Q  -  -  -  -  -  -
-  -  -  -  -  -  Q  -
-  -  Q  -  -  -  -  -
-  -  -  -  -  Q  -  -

-  -  -  Q  -  -  -  -
Q  -  -  -  -  -  -  -
-  -  -  -  Q  -  -  -
-  -  -  -  -  -  -  Q
-  -  -  -  -  Q  -  -
-  -  Q  -  -  -  -  -
-  -  -  -  -  -  Q  -
-  Q  -  -  -  -  -  -

-  -  -  Q  -  -  -  -
-  Q  -  -  -  -  -  -
-  -  -  -  Q  -  -  -
-  -  -  -  -  -  -  Q
-  -  -  -  -  Q  -  -
Q  -  -  -  -  -  -  -
-  -  Q  -  -  -  -  -
-  -  -  -  -  -  Q  -

-  -  -  Q  -  -  -  -
-  Q  -  -  -  -  -  -
-  -  -  -  -  -  Q  -
-  -  Q  -  -  -  -  -
-  -  -  -  -  Q  -  -
-  -  -  -  -  -  -  Q
Q  -  -  -  -  -  -  -
-  -  -  -  Q  -  -  -

-  -  -  Q  -  -  -  -
-  Q  -  -  -  -  -  -
-  -  -  -  -  -  Q  -
-  -  Q  -  -  -  -  -
-  -  -  -  -  Q  -  -
-  -  -  -  -  -  -  Q
-  -  -  -  Q  -  -  -
Q  -  -  -  -  -  -  -

-  -  -  Q  -  -  -  -
-  Q  -  -  -  -  -  -
-  -  -  -  -  -  Q  -
-  -  -  -  Q  -  -  -
Q  -  -  -  -  -  -  -
-  -  -  -  -  -  -  Q
-  -  -  -  -  Q  -  -
-  -  Q  -  -  -  -  -

-  -  -  Q  -  -  -  -
-  Q  -  -  -  -  -  -
-  -  -  -  -  -  -  Q
-  -  -  -  Q  -  -  -
-  -  -  -  -  -  Q  -
Q  -  -  -  -  -  -  -
-  -  Q  -  -  -  -  -
-  -  -  -  -  Q  -  -

-  -  -  Q  -  -  -  -
-  Q  -  -  -  -  -  -
-  -  -  -  -  -  -  Q
-  -  -  -  -  Q  -  -
Q  -  -  -  -  -  -  -
-  -  Q  -  -  -  -  -
-  -  -  -  Q  -  -  -
-  -  -  -  -  -  Q  -

-  -  -  Q  -  -  -  -
-  -  -  -  -  Q  -  -
Q  -  -  -  -  -  -  -
-  -  -  -  Q  -  -  -
-  Q  -  -  -  -  -  -
-  -  -  -  -  -  -  Q
-  -  Q  -  -  -  -  -
-  -  -  -  -  -  Q  -

-  -  -  Q  -  -  -  -
-  -  -  -  -  Q  -  -
-  -  -  -  -  -  -  Q
-  Q  -  -  -  -  -  -
-  -  -  -  -  -  Q  -
Q  -  -  -  -  -  -  -
-  -  Q  -  -  -  -  -
-  -  -  -  Q  -  -  -

-  -  -  Q  -  -  -  -
-  -  -  -  -  Q  -  -
-  -  -  -  -  -  -  Q
-  -  Q  -  -  -  -  -
Q  -  -  -  -  -  -  -
-  -  -  -  -  -  Q  -
-  -  -  -  Q  -  -  -
-  Q  -  -  -  -  -  -

-  -  -  Q  -  -  -  -
-  -  -  -  -  -  Q  -
Q  -  -  -  -  -  -  -
-  -  -  -  -  -  -  Q
-  -  -  -  Q  -  -  -
-  Q  -  -  -  -  -  -
-  -  -  -  -  Q  -  -
-  -  Q  -  -  -  -  -

-  -  -  Q  -  -  -  -
-  -  -  -  -  -  Q  -
-  -  Q  -  -  -  -  -
-  -  -  -  -  -  -  Q
-  Q  -  -  -  -  -  -
-  -  -  -  Q  -  -  -
Q  -  -  -  -  -  -  -
-  -  -  -  -  Q  -  -

-  -  -  Q  -  -  -  -
-  -  -  -  -  -  Q  -
-  -  -  -  Q  -  -  -
-  Q  -  -  -  -  -  -
-  -  -  -  -  Q  -  -
Q  -  -  -  -  -  -  -
-  -  Q  -  -  -  -  -
-  -  -  -  -  -  -  Q

-  -  -  Q  -  -  -  -
-  -  -  -  -  -  Q  -
-  -  -  -  Q  -  -  -
-  -  Q  -  -  -  -  -
Q  -  -  -  -  -  -  -
-  -  -  -  -  Q  -  -
-  -  -  -  -  -  -  Q
-  Q  -  -  -  -  -  -

-  -  -  Q  -  -  -  -
-  -  -  -  -  -  -  Q
Q  -  -  -  -  -  -  -
-  -  Q  -  -  -  -  -
-  -  -  -  -  Q  -  -
-  Q  -  -  -  -  -  -
-  -  -  -  -  -  Q  -
-  -  -  -  Q  -  -  -

-  -  -  Q  -  -  -  -
-  -  -  -  -  -  -  Q
Q  -  -  -  -  -  -  -
-  -  -  -  Q  -  -  -
-  -  -  -  -  -  Q  -
-  Q  -  -  -  -  -  -
-  -  -  -  -  Q  -  -
-  -  Q  -  -  -  -  -

-  -  -  Q  -  -  -  -
-  -  -  -  -  -  -  Q
-  -  -  -  Q  -  -  -
-  -  Q  -  -  -  -  -
Q  -  -  -  -  -  -  -
-  -  -  -  -  -  Q  -
-  Q  -  -  -  -  -  -
-  -  -  -  -  Q  -  -

-  -  -  -  Q  -  -  -
Q  -  -  -  -  -  -  -
-  -  -  Q  -  -  -  -
-  -  -  -  -  Q  -  -
-  -  -  -  -  -  -  Q
-  Q  -  -  -  -  -  -
-  -  -  -  -  -  Q  -
-  -  Q  -  -  -  -  -

-  -  -  -  Q  -  -  -
Q  -  -  -  -  -  -  -
-  -  -  -  -  -  -  Q
-  -  -  Q  -  -  -  -
-  Q  -  -  -  -  -  -
-  -  -  -  -  -  Q  -
-  -  Q  -  -  -  -  -
-  -  -  -  -  Q  -  -

-  -  -  -  Q  -  -  -
Q  -  -  -  -  -  -  -
-  -  -  -  -  -  -  Q
-  -  -  -  -  Q  -  -
-  -  Q  -  -  -  -  -
-  -  -  -  -  -  Q  -
-  Q  -  -  -  -  -  -
-  -  -  Q  -  -  -  -

-  -  -  -  Q  -  -  -
-  Q  -  -  -  -  -  -
-  -  -  Q  -  -  -  -
-  -  -  -  -  Q  -  -
-  -  -  -  -  -  -  Q
-  -  Q  -  -  -  -  -
Q  -  -  -  -  -  -  -
-  -  -  -  -  -  Q  -

-  -  -  -  Q  -  -  -
-  Q  -  -  -  -  -  -
-  -  -  Q  -  -  -  -
-  -  -  -  -  -  Q  -
-  -  Q  -  -  -  -  -
-  -  -  -  -  -  -  Q
-  -  -  -  -  Q  -  -
Q  -  -  -  -  -  -  -

-  -  -  -  Q  -  -  -
-  Q  -  -  -  -  -  -
-  -  -  -  -  Q  -  -
Q  -  -  -  -  -  -  -
-  -  -  -  -  -  Q  -
-  -  -  Q  -  -  -  -
-  -  -  -  -  -  -  Q
-  -  Q  -  -  -  -  -

-  -  -  -  Q  -  -  -
-  Q  -  -  -  -  -  -
-  -  -  -  -  -  -  Q
Q  -  -  -  -  -  -  -
-  -  -  Q  -  -  -  -
-  -  -  -  -  -  Q  -
-  -  Q  -  -  -  -  -
-  -  -  -  -  Q  -  -

-  -  -  -  Q  -  -  -
-  -  Q  -  -  -  -  -
Q  -  -  -  -  -  -  -
-  -  -  -  -  Q  -  -
-  -  -  -  -  -  -  Q
-  Q  -  -  -  -  -  -
-  -  -  Q  -  -  -  -
-  -  -  -  -  -  Q  -

-  -  -  -  Q  -  -  -
-  -  Q  -  -  -  -  -
Q  -  -  -  -  -  -  -
-  -  -  -  -  -  Q  -
-  Q  -  -  -  -  -  -
-  -  -  -  -  -  -  Q
-  -  -  -  -  Q  -  -
-  -  -  Q  -  -  -  -

-  -  -  -  Q  -  -  -
-  -  Q  -  -  -  -  -
-  -  -  -  -  -  -  Q
-  -  -  Q  -  -  -  -
-  -  -  -  -  -  Q  -
Q  -  -  -  -  -  -  -
-  -  -  -  -  Q  -  -
-  Q  -  -  -  -  -  -

-  -  -  -  Q  -  -  -
-  -  -  -  -  -  Q  -
Q  -  -  -  -  -  -  -
-  -  Q  -  -  -  -  -
-  -  -  -  -  -  -  Q
-  -  -  -  -  Q  -  -
-  -  -  Q  -  -  -  -
-  Q  -  -  -  -  -  -

-  -  -  -  Q  -  -  -
-  -  -  -  -  -  Q  -
Q  -  -  -  -  -  -  -
-  -  -  Q  -  -  -  -
-  Q  -  -  -  -  -  -
-  -  -  -  -  -  -  Q
-  -  -  -  -  Q  -  -
-  -  Q  -  -  -  -  -

-  -  -  -  Q  -  -  -
-  -  -  -  -  -  Q  -
-  Q  -  -  -  -  -  -
-  -  -  Q  -  -  -  -
-  -  -  -  -  -  -  Q
Q  -  -  -  -  -  -  -
-  -  Q  -  -  -  -  -
-  -  -  -  -  Q  -  -

-  -  -  -  Q  -  -  -
-  -  -  -  -  -  Q  -
-  Q  -  -  -  -  -  -
-  -  -  -  -  Q  -  -
-  -  Q  -  -  -  -  -
Q  -  -  -  -  -  -  -
-  -  -  Q  -  -  -  -
-  -  -  -  -  -  -  Q

-  -  -  -  Q  -  -  -
-  -  -  -  -  -  Q  -
-  Q  -  -  -  -  -  -
-  -  -  -  -  Q  -  -
-  -  Q  -  -  -  -  -
Q  -  -  -  -  -  -  -
-  -  -  -  -  -  -  Q
-  -  -  Q  -  -  -  -

-  -  -  -  Q  -  -  -
-  -  -  -  -  -  Q  -
-  -  -  Q  -  -  -  -
Q  -  -  -  -  -  -  -
-  -  Q  -  -  -  -  -
-  -  -  -  -  -  -  Q
-  -  -  -  -  Q  -  -
-  Q  -  -  -  -  -  -

-  -  -  -  Q  -  -  -
-  -  -  -  -  -  -  Q
-  -  -  Q  -  -  -  -
Q  -  -  -  -  -  -  -
-  -  Q  -  -  -  -  -
-  -  -  -  -  Q  -  -
-  Q  -  -  -  -  -  -
-  -  -  -  -  -  Q  -

-  -  -  -  Q  -  -  -
-  -  -  -  -  -  -  Q
-  -  -  Q  -  -  -  -
Q  -  -  -  -  -  -  -
-  -  -  -  -  -  Q  -
-  Q  -  -  -  -  -  -
-  -  -  -  -  Q  -  -
-  -  Q  -  -  -  -  -

-  -  -  -  -  Q  -  -
Q  -  -  -  -  -  -  -
-  -  -  -  Q  -  -  -
-  Q  -  -  -  -  -  -
-  -  -  -  -  -  -  Q
-  -  Q  -  -  -  -  -
-  -  -  -  -  -  Q  -
-  -  -  Q  -  -  -  -

-  -  -  -  -  Q  -  -
-  Q  -  -  -  -  -  -
-  -  -  -  -  -  Q  -
Q  -  -  -  -  -  -  -
-  -  Q  -  -  -  -  -
-  -  -  -  Q  -  -  -
-  -  -  -  -  -  -  Q
-  -  -  Q  -  -  -  -

-  -  -  -  -  Q  -  -
-  Q  -  -  -  -  -  -
-  -  -  -  -  -  Q  -
Q  -  -  -  -  -  -  -
-  -  -  Q  -  -  -  -
-  -  -  -  -  -  -  Q
-  -  -  -  Q  -  -  -
-  -  Q  -  -  -  -  -

-  -  -  -  -  Q  -  -
-  -  Q  -  -  -  -  -
Q  -  -  -  -  -  -  -
-  -  -  -  -  -  Q  -
-  -  -  -  Q  -  -  -
-  -  -  -  -  -  -  Q
-  Q  -  -  -  -  -  -
-  -  -  Q  -  -  -  -

-  -  -  -  -  Q  -  -
-  -  Q  -  -  -  -  -
Q  -  -  -  -  -  -  -
-  -  -  -  -  -  -  Q
-  -  -  Q  -  -  -  -
-  Q  -  -  -  -  -  -
-  -  -  -  -  -  Q  -
-  -  -  -  Q  -  -  -

-  -  -  -  -  Q  -  -
-  -  Q  -  -  -  -  -
Q  -  -  -  -  -  -  -
-  -  -  -  -  -  -  Q
-  -  -  -  Q  -  -  -
-  Q  -  -  -  -  -  -
-  -  -  Q  -  -  -  -
-  -  -  -  -  -  Q  -

-  -  -  -  -  Q  -  -
-  -  Q  -  -  -  -  -
-  -  -  -  Q  -  -  -
-  -  -  -  -  -  Q  -
Q  -  -  -  -  -  -  -
-  -  -  Q  -  -  -  -
-  Q  -  -  -  -  -  -
-  -  -  -  -  -  -  Q

-  -  -  -  -  Q  -  -
-  -  Q  -  -  -  -  -
-  -  -  -  Q  -  -  -
-  -  -  -  -  -  -  Q
Q  -  -  -  -  -  -  -
-  -  -  Q  -  -  -  -
-  Q  -  -  -  -  -  -
-  -  -  -  -  -  Q  -

-  -  -  -  -  Q  -  -
-  -  Q  -  -  -  -  -
-  -  -  -  -  -  Q  -
-  Q  -  -  -  -  -  -
-  -  -  Q  -  -  -  -
-  -  -  -  -  -  -  Q
Q  -  -  -  -  -  -  -
-  -  -  -  Q  -  -  -

-  -  -  -  -  Q  -  -
-  -  Q  -  -  -  -  -
-  -  -  -  -  -  Q  -
-  Q  -  -  -  -  -  -
-  -  -  -  -  -  -  Q
-  -  -  -  Q  -  -  -
Q  -  -  -  -  -  -  -
-  -  -  Q  -  -  -  -

-  -  -  -  -  Q  -  -
-  -  Q  -  -  -  -  -
-  -  -  -  -  -  Q  -
-  -  -  Q  -  -  -  -
Q  -  -  -  -  -  -  -
-  -  -  -  -  -  -  Q
-  Q  -  -  -  -  -  -
-  -  -  -  Q  -  -  -

-  -  -  -  -  Q  -  -
-  -  -  Q  -  -  -  -
Q  -  -  -  -  -  -  -
-  -  -  -  Q  -  -  -
-  -  -  -  -  -  -  Q
-  Q  -  -  -  -  -  -
-  -  -  -  -  -  Q  -
-  -  Q  -  -  -  -  -

-  -  -  -  -  Q  -  -
-  -  -  Q  -  -  -  -
-  Q  -  -  -  -  -  -
-  -  -  -  -  -  -  Q
-  -  -  -  Q  -  -  -
-  -  -  -  -  -  Q  -
Q  -  -  -  -  -  -  -
-  -  Q  -  -  -  -  -

-  -  -  -  -  Q  -  -
-  -  -  Q  -  -  -  -
-  -  -  -  -  -  Q  -
Q  -  -  -  -  -  -  -
-  -  Q  -  -  -  -  -
-  -  -  -  Q  -  -  -
-  Q  -  -  -  -  -  -
-  -  -  -  -  -  -  Q

-  -  -  -  -  Q  -  -
-  -  -  Q  -  -  -  -
-  -  -  -  -  -  Q  -
Q  -  -  -  -  -  -  -
-  -  -  -  -  -  -  Q
-  Q  -  -  -  -  -  -
-  -  -  -  Q  -  -  -
-  -  Q  -  -  -  -  -

-  -  -  -  -  Q  -  -
-  -  -  -  -  -  -  Q
-  Q  -  -  -  -  -  -
-  -  -  Q  -  -  -  -
Q  -  -  -  -  -  -  -
-  -  -  -  -  -  Q  -
-  -  -  -  Q  -  -  -
-  -  Q  -  -  -  -  -

-  -  -  -  -  -  Q  -
Q  -  -  -  -  -  -  -
-  -  Q  -  -  -  -  -
-  -  -  -  -  -  -  Q
-  -  -  -  -  Q  -  -
-  -  -  Q  -  -  -  -
-  Q  -  -  -  -  -  -
-  -  -  -  Q  -  -  -

-  -  -  -  -  -  Q  -
-  Q  -  -  -  -  -  -
-  -  -  Q  -  -  -  -
Q  -  -  -  -  -  -  -
-  -  -  -  -  -  -  Q
-  -  -  -  Q  -  -  -
-  -  Q  -  -  -  -  -
-  -  -  -  -  Q  -  -

-  -  -  -  -  -  Q  -
-  Q  -  -  -  -  -  -
-  -  -  -  -  Q  -  -
-  -  Q  -  -  -  -  -
Q  -  -  -  -  -  -  -
-  -  -  Q  -  -  -  -
-  -  -  -  -  -  -  Q
-  -  -  -  Q  -  -  -

-  -  -  -  -  -  Q  -
-  -  Q  -  -  -  -  -
Q  -  -  -  -  -  -  -
-  -  -  -  -  Q  -  -
-  -  -  -  -  -  -  Q
-  -  -  -  Q  -  -  -
-  Q  -  -  -  -  -  -
-  -  -  Q  -  -  -  -

-  -  -  -  -  -  Q  -
-  -  Q  -  -  -  -  -
-  -  -  -  -  -  -  Q
-  Q  -  -  -  -  -  -
-  -  -  -  Q  -  -  -
Q  -  -  -  -  -  -  -
-  -  -  -  -  Q  -  -
-  -  -  Q  -  -  -  -

-  -  -  -  -  -  Q  -
-  -  -  Q  -  -  -  -
-  Q  -  -  -  -  -  -
-  -  -  -  Q  -  -  -
-  -  -  -  -  -  -  Q
Q  -  -  -  -  -  -  -
-  -  Q  -  -  -  -  -
-  -  -  -  -  Q  -  -

-  -  -  -  -  -  Q  -
-  -  -  Q  -  -  -  -
-  Q  -  -  -  -  -  -
-  -  -  -  -  -  -  Q
-  -  -  -  -  Q  -  -
Q  -  -  -  -  -  -  -
-  -  Q  -  -  -  -  -
-  -  -  -  Q  -  -  -

-  -  -  -  -  -  Q  -
-  -  -  -  Q  -  -  -
-  -  Q  -  -  -  -  -
Q  -  -  -  -  -  -  -
-  -  -  -  -  Q  -  -
-  -  -  -  -  -  -  Q
-  Q  -  -  -  -  -  -
-  -  -  Q  -  -  -  -

-  -  -  -  -  -  -  Q
-  Q  -  -  -  -  -  -
-  -  -  Q  -  -  -  -
Q  -  -  -  -  -  -  -
-  -  -  -  -  -  Q  -
-  -  -  -  Q  -  -  -
-  -  Q  -  -  -  -  -
-  -  -  -  -  Q  -  -

-  -  -  -  -  -  -  Q
-  Q  -  -  -  -  -  -
-  -  -  -  Q  -  -  -
-  -  Q  -  -  -  -  -
Q  -  -  -  -  -  -  -
-  -  -  -  -  -  Q  -
-  -  -  Q  -  -  -  -
-  -  -  -  -  Q  -  -

-  -  -  -  -  -  -  Q
-  -  Q  -  -  -  -  -
Q  -  -  -  -  -  -  -
-  -  -  -  -  Q  -  -
-  Q  -  -  -  -  -  -
-  -  -  -  Q  -  -  -
-  -  -  -  -  -  Q  -
-  -  -  Q  -  -  -  -

-  -  -  -  -  -  -  Q
-  -  -  Q  -  -  -  -
Q  -  -  -  -  -  -  -
-  -  Q  -  -  -  -  -
-  -  -  -  -  Q  -  -
-  Q  -  -  -  -  -  -
-  -  -  -  -  -  Q  -
-  -  -  -  Q  -  -  -

Total N Queue 92``````
``````#include<iostream>
#define N 8
using namespace std;

/*
C++ Program
Print all solutions in N-Queen Problem
*/
class MyBacktracking {
public:
int counter;
int size;
MyBacktracking(int size) {
this->size = N;
this->counter = 0;
}
//Check valid element to insert a new n-queen element
int location(char result[][N], int row, int col) {
int status = 1;
//Check element in row and column

for (int i = 0; i < this->size && status == 1; ++i) {
if (result[row][i] == 'Q' || result[i][col] == 'Q') {
//When element are exist
status = 0;
}
}
//Compare by diagonal element

for (int i = 0, j = row, k = col; i < this->size && status == 1; ++i) {
//Check condition of diagonal element
//top left
//bottom right
//bottom left
//top right

if ((j - i >= 0
&&
k - i >= 0
&&
result[j - i][k - i] == 'Q')
||
(j + i) < this->size
&&
(k + i) < this->size
&&
result[j + i][k + i] == 'Q'
||
(j - i >= 0
&& k + i < this->size
&& result[j - i][k + i] == 'Q')
||
(j + i < this->size
&& k - i >= 0
&& result[j + i][k - i] == 'Q'))
{
status = 0;
}
}
return status;
}
//Display the value of result
void show_data(char result[][N]) {
for (int i = 0; i < this->size; ++i) {
for (int j = 0; j < this->size; ++j) {
cout << " " << result[i][j];
}
cout << "\n";
}
cout << "\n\n";
}
void n_queen(char result[][N], int row) {
if (row > this->size || row < 0) {
return;
}
if (row == this->size) {
this->counter++;
//Display queen result
this->show_data(result);
} else {
for (int i = 0; i < this->size; ++i) {
if (this->location(result, row, i) == 1) {
//When valid to insert Queen element
result[row][i] = 'Q';
this->n_queen(result, row + 1);
//set the initial value
result[row][i] = '-';
}
}
}
}
void defualt_value(char result[N][N]) {
//When implement more than 2 n-queen
//reset the counter value
this->counter = 0;
//Set initial value

for (int i = 0; i < this->size; ++i) {
for (int j = 0; j < this->size; ++j) {
result[i][j] = '-';
}
}
}
};
int main() {
MyBacktracking obj(8);
char result[N][N] ;
obj.defualt_value(result);
obj.n_queen(result, 0);
cout << " Total N Queue " << obj.counter << "\n";
return 0;
}```
```

#### Output

`````` Q - - - - - - -
- - - - Q - - -
- - - - - - - Q
- - - - - Q - -
- - Q - - - - -
- - - - - - Q -
- Q - - - - - -
- - - Q - - - -

Q - - - - - - -
- - - - - Q - -
- - - - - - - Q
- - Q - - - - -
- - - - - - Q -
- - - Q - - - -
- Q - - - - - -
- - - - Q - - -

Q - - - - - - -
- - - - - - Q -
- - - Q - - - -
- - - - - Q - -
- - - - - - - Q
- Q - - - - - -
- - - - Q - - -
- - Q - - - - -

Q - - - - - - -
- - - - - - Q -
- - - - Q - - -
- - - - - - - Q
- Q - - - - - -
- - - Q - - - -
- - - - - Q - -
- - Q - - - - -

- Q - - - - - -
- - - Q - - - -
- - - - - Q - -
- - - - - - - Q
- - Q - - - - -
Q - - - - - - -
- - - - - - Q -
- - - - Q - - -

more....

Total N Queue 92``````
``````/*
Java Program
Print all solutions in N-Queen Problem
*/
public class MyBacktracking {

public int counter;
public int size;

public MyBacktracking(int size)
{
this.size = size;
counter = 0;
}

//Check valid element to insert a new n-queen element
public int location(char [][]result,int row,int col)
{

int status=1;
//Check element in row and column
for (int i = 0; i < this.size && status==1; ++i)
{

if(result[row][i]=='Q' || result[i][col]=='Q')
{
//When element are exist
status=0;
}
}

//Compare by diagonal element
for (int i = 0,j=row,k=col; i <this.size && status==1 ; ++i)
{
//Check condition of diagonal element
//top left
//bottom right
//bottom left
//top right
if(
(j-i>=0 && k-i>=0 && result[j-i][k-i]=='Q')
||
(j+i)<this.size && (k+i) < this.size && result[j+i][k+i]=='Q'
||
(j-i>=0 && k+i<this.size && result[j-i][k+i]=='Q')
||
(j+i<this.size && k-i>=0 && result[j+i][k-i]=='Q')
)
{
status=0;
}

}

return status;
}
//Display the value of result
public void show_data(char [][]result)
{
for (int i = 0; i < this.size; ++i)
{
for (int j = 0; j < this.size; ++j)
{
System.out.print("  "+result[i][j] );
}
System.out.print("\n");
}
System.out.print("\n\n");
}
public void n_queen(char [][]result, int row)
{

if(row>this.size || row<0)
{
return;
}
if(row==this.size)
{
counter++;
//Display queen result
show_data(result);

}
else
{
for (int i = 0; i < this.size; ++i)
{

if(location(result,row,i)==1)
{
//When valid to insert Queen element
result[row][i]='Q';

n_queen(result,row+1);

//set the initial value
result[row][i]='-';
}
}
}
}
public void defualt_value(char [][]result)
{
//When implement more than 2 n-queen
//reset the counter value
this.counter=0;

//Set initial value
for (int i = 0; i < this.size; ++i)
{
for (int j = 0; j < this.size; ++j)
{
result[i][j]='-';
}
}
}

public static void main(String[] args) {

MyBacktracking obj = new MyBacktracking(8);

//Auxiliary space which is store the result
char [][]result=new char[obj.size][obj.size];

obj.defualt_value(result);

obj.n_queen(result,0);

System.out.print(" Total N Queue "+obj.counter +"\n");
}
}```
```

#### Output

`````` Q - - - - - - -
- - - - Q - - -
- - - - - - - Q
- - - - - Q - -
- - Q - - - - -
- - - - - - Q -
- Q - - - - - -
- - - Q - - - -

Q - - - - - - -
- - - - - Q - -
- - - - - - - Q
- - Q - - - - -
- - - - - - Q -
- - - Q - - - -
- Q - - - - - -
- - - - Q - - -

Q - - - - - - -
- - - - - - Q -
- - - Q - - - -
- - - - - Q - -
- - - - - - - Q
- Q - - - - - -
- - - - Q - - -
- - Q - - - - -

Q - - - - - - -
- - - - - - Q -
- - - - Q - - -
- - - - - - - Q
- Q - - - - - -
- - - Q - - - -
- - - - - Q - -
- - Q - - - - -

- Q - - - - - -
- - - Q - - - -
- - - - - Q - -
- - - - - - - Q
- - Q - - - - -
Q - - - - - - -
- - - - - - Q -
- - - - Q - - -

more....

Total N Queue 92``````
``````/*
C# Program
Print all solutions in N-Queen Problem
*/
using System;
public class MyBacktracking {
int counter;
int size;
MyBacktracking(int size) {
this.size = size;
counter = 0;
}
//Check valid element to insert a new n-queen element
public int location(char[,] result, int row, int col) {
int status = 1;
//Check element in row and column

for (int i = 0; i < this.size && status == 1; ++i) {
if (result[row,i] == 'Q' || result[i,col] == 'Q') {
//When element are exist
status = 0;
}
}
//Compare by diagonal element

for (int i = 0, j = row, k = col; i < this.size && status == 1; ++i) {
//Check condition of diagonal element
//top left
//bottom right
//bottom left
//top right

if ((j - i >= 0 && k - i >= 0 && result[j - i,k - i] == 'Q') || (j + i) < this.size && (k + i) < this.size && result[j + i,k + i] == 'Q' || (j - i >= 0 && k + i < this.size && result[j - i,k + i] == 'Q') || (j + i < this.size && k - i >= 0 && result[j + i,k - i] == 'Q')) {
status = 0;
}
}
return status;
}
//Display the value of result
public void show_data(char[,] result) {
for (int i = 0; i < this.size; ++i) {
for (int j = 0; j < this.size; ++j) {
Console.Write(" " + result[i,j]);
}
Console.Write("\n");
}
Console.Write("\n\n");
}
public void n_queen(char[,] result, int row) {
if (row > this.size || row < 0) {
return;
}
if (row == this.size) {
counter++;
show_data(result);
} else {
for (int i = 0; i < this.size; ++i) {
if (location(result, row, i) == 1) {
//When valid to insert Queen element
result[row,i] = 'Q';
n_queen(result, row + 1);
//set the initial value
result[row,i] = '-';
}
}
}
}
public void defualt_value(char[,] result) {
//When implement more than 2 n-queen
//reset the counter value
this.counter = 0;
//Set initial value
for (int i = 0; i < this.size; ++i) {
for (int j = 0; j < this.size; ++j) {
result[i,j] = '-';
}
}
}
public static void Main(String[] args) {
MyBacktracking obj = new MyBacktracking(8);
//Auxiliary space which is store the result
char[,]result = new char[obj.size,obj.size];
obj.defualt_value(result);
obj.n_queen(result, 0);
Console.Write(" Total N Queue " + obj.counter + "\n");
}
}```
```

#### Output

`````` Q - - - - - - -
- - - - Q - - -
- - - - - - - Q
- - - - - Q - -
- - Q - - - - -
- - - - - - Q -
- Q - - - - - -
- - - Q - - - -

Q - - - - - - -
- - - - - Q - -
- - - - - - - Q
- - Q - - - - -
- - - - - - Q -
- - - Q - - - -
- Q - - - - - -
- - - - Q - - -

Q - - - - - - -
- - - - - - Q -
- - - Q - - - -
- - - - - Q - -
- - - - - - - Q
- Q - - - - - -
- - - - Q - - -
- - Q - - - - -

Q - - - - - - -
- - - - - - Q -
- - - - Q - - -
- - - - - - - Q
- Q - - - - - -
- - - Q - - - -
- - - - - Q - -
- - Q - - - - -

- Q - - - - - -
- - - Q - - - -
- - - - - Q - -
- - - - - - - Q
- - Q - - - - -
Q - - - - - - -
- - - - - - Q -
- - - - Q - - -

more....

Total N Queue 92``````
``````<?php
/*
Php Program
Print all solutions in N-Queen Problem
*/
class MyBacktracking {
public \$counter;
public \$size;

function __construct(\$size) {
\$this->size = \$size;
\$this->counter = 0;
}
//Check valid element to insert a new n-queen element

public  function location(\$result, \$row, \$col) {
\$status = 1;
//Check element in row and column

for (\$i = 0; \$i < \$this->size && \$status == 1; ++\$i) {
if (\$result[\$row][\$i] == 'Q' || \$result[\$i][\$col] == 'Q') {
//When element are exist
\$status = 0;
}
}
//Compare by diagonal element

for (\$i = 0, \$j = \$row, \$k = \$col; \$i < \$this->size && \$status == 1; ++\$i) {
//Check condition of diagonal element
//top left
//bottom right
//bottom left
//top right

if ((\$j - \$i >= 0 && \$k - \$i >= 0 && \$result[\$j - \$i][\$k - \$i] == 'Q') || (\$j + \$i) < \$this->size && (\$k + \$i) < \$this->size && \$result[\$j + \$i][\$k + \$i] == 'Q' || (\$j - \$i >= 0 && \$k + \$i < \$this->size && \$result[\$j - \$i][\$k + \$i] == 'Q') || (\$j + \$i < \$this->size && \$k - \$i >= 0 && \$result[\$j + \$i][\$k - \$i] == 'Q')) {
\$status = 0;
}
}
return \$status;
}
//Display the value of result

public  function show_data(\$result) {
for (\$i = 0; \$i < \$this->size; ++\$i) {
for (\$j = 0; \$j < \$this->size; ++\$j) {
echo(" ". \$result[\$i][\$j]);
}
echo("\n");
}
echo("\n\n");
}
public  function n_queen(&\$result, \$row) {
if (\$row > \$this->size || \$row < 0) {
return;
}
if (\$row == \$this->size) {
\$this->counter++;
//Display queen result
\$this->show_data(\$result);
} else {
for (\$i = 0; \$i < \$this->size; ++\$i) {
if (\$this->location(\$result, \$row, \$i) == 1) {
//When valid to insert Queen element
\$result[\$row][\$i] = 'Q';
\$this->n_queen(\$result, \$row + 1);
//set the initial value
\$result[\$row][\$i] = '-';
}
}
}
}
public  function defualt_value() {
//When implement more than 2 n-queen
//reset the counter value
\$this->counter = 0;

}
}

function main() {
\$obj = new MyBacktracking(8);
//Auxiliary space which is store the result
\$result = array_fill(0, \$obj->size, array_fill(0, \$obj->size, '-'));
\$obj->defualt_value();
\$obj->n_queen(\$result, 0);
echo(" Total N Queue ". \$obj->counter ."\n");

}
main();```
```

#### Output

`````` Q - - - - - - -
- - - - Q - - -
- - - - - - - Q
- - - - - Q - -
- - Q - - - - -
- - - - - - Q -
- Q - - - - - -
- - - Q - - - -

Q - - - - - - -
- - - - - Q - -
- - - - - - - Q
- - Q - - - - -
- - - - - - Q -
- - - Q - - - -
- Q - - - - - -
- - - - Q - - -

Q - - - - - - -
- - - - - - Q -
- - - Q - - - -
- - - - - Q - -
- - - - - - - Q
- Q - - - - - -
- - - - Q - - -
- - Q - - - - -

Q - - - - - - -
- - - - - - Q -
- - - - Q - - -
- - - - - - - Q
- Q - - - - - -
- - - Q - - - -
- - - - - Q - -
- - Q - - - - -

- Q - - - - - -
- - - Q - - - -
- - - - - Q - -
- - - - - - - Q
- - Q - - - - -
Q - - - - - - -
- - - - - - Q -
- - - - Q - - -

more....

Total N Queue 92``````
``````/*
Node Js Program
Print all solutions in N-Queen Problem
*/
class MyBacktracking {

constructor(size) {
this.size = size;
this.counter = 0;
}

//Check valid element to insert a new n-queen element
location(result, row, col) {
var status = 1;
//Check element in row and column

for (var i = 0; i < this.size && status == 1; ++i) {
if (result[row][i] == 'Q' || result[i][col] == 'Q') {
//When element are exist
status = 0;
}
}

//Compare by diagonal element

for (var i = 0,j = row,k = col; i < this.size && status == 1; ++i) {
//Check condition of diagonal element
//top left
//bottom right
//bottom left
//top right

if ((j - i >= 0 && k - i >= 0 && result[j - i][k - i] == 'Q') || (j + i) < this.size && (k + i) < this.size && result[j + i][k + i] == 'Q' || (j - i >= 0 && k + i < this.size && result[j - i][k + i] == 'Q') || (j + i < this.size && k - i >= 0 && result[j + i][k - i] == 'Q')) {
status = 0;
}
}

return status;
}

//Display the value of result
show_data(result) {
for (var i = 0; i < this.size; ++i) {
for (var j = 0; j < this.size; ++j) {
process.stdout.write(" " + result[i][j]);
}

process.stdout.write("\n");
}

process.stdout.write("\n\n");
}
n_queen(result, row) {
if (row > this.size || row < 0) {
return;
}

if (row == this.size) {
this.counter++;
//Display queen result
this.show_data(result);
} else {
for (var i = 0; i < this.size; ++i) {
if (this.location(result, row, i) == 1) {
//When valid to insert Queen element
result[row][i] = 'Q';
this.n_queen(result, row + 1);
//set the initial value
result[row][i] = '-';
}
}
}
}
defualt_value(result) {
//When implement more than 2 n-queen
//reset the counter value
this.counter = 0;
//Set initial value

for (var i = 0; i < this.size; ++i) {
for (var j = 0; j < this.size; ++j) {
result[i][j] = '-';
}
}
}
}

function main(args) {
var obj = new MyBacktracking(8);
//Auxiliary space which is store the result
var result = Array(obj.size).fill().map(() => new Array(obj.size).fill('-'));
obj.defualt_value(result);
obj.n_queen(result, 0);
process.stdout.write(" Total N Queue " + obj.counter + "\n");
}

main();```
```

#### Output

`````` Q - - - - - - -
- - - - Q - - -
- - - - - - - Q
- - - - - Q - -
- - Q - - - - -
- - - - - - Q -
- Q - - - - - -
- - - Q - - - -

Q - - - - - - -
- - - - - Q - -
- - - - - - - Q
- - Q - - - - -
- - - - - - Q -
- - - Q - - - -
- Q - - - - - -
- - - - Q - - -

Q - - - - - - -
- - - - - - Q -
- - - Q - - - -
- - - - - Q - -
- - - - - - - Q
- Q - - - - - -
- - - - Q - - -
- - Q - - - - -

Q - - - - - - -
- - - - - - Q -
- - - - Q - - -
- - - - - - - Q
- Q - - - - - -
- - - Q - - - -
- - - - - Q - -
- - Q - - - - -

- Q - - - - - -
- - - Q - - - -
- - - - - Q - -
- - - - - - - Q
- - Q - - - - -
Q - - - - - - -
- - - - - - Q -
- - - - Q - - -

more....

Total N Queue 92``````
``````#   Python 3 Program
#   Print all solutions in N-Queen Problem
class MyBacktracking :

def __init__(self, size) :
self.size = size
self.counter = 0

# Check valid element to insert a new n-queen element
def location(self, result, row, col) :
status = 1
# Check element in row and column
i = 0
while (i < self.size and status == 1) :
if (result[row][i] == 'Q'
or result[i][col] == 'Q') :
# When element are exist
status = 0

i += 1

# Compare by diagonal element
i = 0
j = row
k = col
while (i < self.size and status == 1) :
# Check condition of diagonal element
# top left
# bottom right
# bottom left
# top right

if ((j - i >= 0 and k - i >= 0 and result[j - i][k - i] == 'Q') or(j + i) < self.size and(k + i) < self.size and result[j + i][k + i] == 'Q'
or(j - i >= 0 and k + i < self.size and result[j - i][k + i] == 'Q') or(j + i < self.size and k - i >= 0 and result[j + i][k - i] == 'Q')) :
status = 0

i += 1

return status

# Display the value of result
def show_data(self, result) :
i = 0
while (i < self.size) :
j = 0
while (j < self.size) :
print(" ", result[i][j], end = "")
j += 1

print("\n", end = "")
i += 1

print("\n\n", end = "")

def n_queen(self, result, row) :
if (row > self.size or row < 0) :
return

if (row == self.size) :
self.counter += 1
self.show_data(result)
else :
i = 0
while (i < self.size) :
if (self.location(result, row, i) == 1) :
# When valid to insert Queen element
result[row][i] = 'Q'
self.n_queen(result, row + 1)
# set the initial value
result[row][i] = '-'

i += 1

def defualt_value(self) :
# When implement more than 2 n-queen
# reset the counter value
self.counter = 0

def main() :
obj = MyBacktracking(8)
result = [['-'] * obj.size
for _ in range(obj.size)
]
obj.defualt_value()
obj.n_queen(result, 0)
print(" Total N Queue ", obj.counter ,"\n", end = "")

if __name__ == "__main__":
main()```
```

#### Output

`````` Q - - - - - - -
- - - - Q - - -
- - - - - - - Q
- - - - - Q - -
- - Q - - - - -
- - - - - - Q -
- Q - - - - - -
- - - Q - - - -

Q - - - - - - -
- - - - - Q - -
- - - - - - - Q
- - Q - - - - -
- - - - - - Q -
- - - Q - - - -
- Q - - - - - -
- - - - Q - - -

Q - - - - - - -
- - - - - - Q -
- - - Q - - - -
- - - - - Q - -
- - - - - - - Q
- Q - - - - - -
- - - - Q - - -
- - Q - - - - -

Q - - - - - - -
- - - - - - Q -
- - - - Q - - -
- - - - - - - Q
- Q - - - - - -
- - - Q - - - -
- - - - - Q - -
- - Q - - - - -

- Q - - - - - -
- - - Q - - - -
- - - - - Q - -
- - - - - - - Q
- - Q - - - - -
Q - - - - - - -
- - - - - - Q -
- - - - Q - - -

more....

Total N Queue 92``````
``````#   Ruby Program
#   Print all solutions in N-Queen Problem
class MyBacktracking
# Define the accessor and reader of class MyBacktracking
attr_accessor :counter, :size
def initialize(size)
self.size = size
@counter = 0
end
# Check valid element to insert a new n-queen element
def location(result, row, col)
status = 1
# Check element in row and column
i = 0
while (i < self.size && status == 1)
if (result[row][i] == 'Q' || result[i][col] == 'Q')
# When element are exist
status = 0
end
i += 1
end
# Compare by diagonal element
i = 0
j = row
k = col
while (i < self.size && status == 1)
# Check condition of diagonal element
# top left
# bottom right
# bottom left
# top right

if ((j - i >= 0 && k - i >= 0 && result[j - i][k - i] == 'Q') || (j + i) < self.size && (k + i) < self.size && result[j + i][k + i] == 'Q' || (j - i >= 0 && k + i < self.size && result[j - i][k + i] == 'Q') || (j + i < self.size && k - i >= 0 && result[j + i][k - i] == 'Q'))
status = 0
end
i += 1
end
return status
end
# Display the value of result
def show_data(result)
i = 0
while (i < self.size)
j = 0
while (j < self.size)
print(" ", result[i][j])
j += 1
end
print("\n")
i += 1
end
print("\n\n")
end
def n_queen(result, row)
if (row > self.size || row < 0)
return
end
if (row == self.size)
@counter += 1
self.show_data(result)
else
i = 0
while (i < self.size)
if (self.location(result, row, i) == 1)
# When valid to insert Queen element
result[row][i] = 'Q'
self.n_queen(result, row + 1)
# set the initial value
result[row][i] = '-'
end
i += 1
end
end
end
def defualt_value()
# When implement more than 2 n-queen
# reset the counter value
self.counter = 0

end
end
def main()
obj = MyBacktracking.new(8)
result = Array.new(obj.size) { Array.new(obj.size,'-' ) }
obj.defualt_value()
obj.n_queen(result, 0)
print(" Total N Queue ", obj.counter ,"\n")
end

main()```
```

#### Output

`````` Q - - - - - - -
- - - - Q - - -
- - - - - - - Q
- - - - - Q - -
- - Q - - - - -
- - - - - - Q -
- Q - - - - - -
- - - Q - - - -

- - - - Q - - -
- Q - - - - - -
- - - - - - - Q
Q - - - - - - -
- - - Q - - - -
- - - - - - Q -
- - Q - - - - -
- - - - - Q - -
more ...
Total N Queue 92
``````
``````/*
Scala Program
Print all solutions in N-Queen Problem
*/
class MyBacktracking(var size: Int,var counter: Int) {

def this(size: Int) {
this(size, 0);
}
//Check valid element to insert a new n-queen element
def location(result: Array[Array[Char]], row: Int, col: Int): Int = {
var status: Int = 1;

//Check element in row and column
var i: Int = 0;
while (i < this.size && status == 1) {
if (result(row)(i) == 'Q' || result(i)(col) == 'Q') {
//When element are exist
status = 0;
}
i += 1;
}
//Compare by diagonal element
i = 0;
val j: Int = row;
val k: Int = col;
while (i < this.size && status == 1) {
//Check condition of diagonal element
//top left
//bottom right
//bottom left
//top right

if ((j - i >= 0 && k - i >= 0 && result(j - i)(k - i) == 'Q') || (j + i) < this.size && (k + i) < this.size && result(j + i)(k + i) == 'Q' || (j - i >= 0 && k + i < this.size && result(j - i)(k + i) == 'Q') || (j + i < this.size && k - i >= 0 && result(j + i)(k - i) == 'Q')) {
status = 0;
}
i += 1;
}
return status;
}
//Display the value of result
def show_data(result: Array[Array[Char]]): Unit = {
var i: Int = 0;
while (i < this.size) {
var j: Int = 0;
while (j < this.size) {
print(" " + result(i)(j));
j += 1;
}
print("\n");
i += 1;
}
print("\n\n");
}
def n_queen(result: Array[Array[Char]], row: Int): Unit = {
if (row > this.size || row < 0) {
return;
}
if (row == this.size) {
this.counter += 1;
this.show_data(result);
} else {
var i: Int = 0;
while (i < this.size) {
if (this.location(result, row, i) == 1) {
//When valid to insert Queen element
result(row)(i) = 'Q';
this.n_queen(result, row + 1);

//set the initial value
result(row)(i) = '-';
}
i += 1;
}
}
}
def defualt_value(): Unit = {
//When implement more than 2 n-queen
//reset the counter value
this.counter = 0;
}
}
object Main {
def main(args: Array[String]): Unit = {
val obj: MyBacktracking = new MyBacktracking(8);
val result: Array[Array[Char]] = Array.fill[Char](obj.size, obj.size)('-');
obj.defualt_value();
obj.n_queen(result, 0);
print(" Total N Queue " + obj.counter + "\n");
}
}```
```

#### Output

`````` Q - - - - - - -
- - - - Q - - -
- - - - - - - Q
- - - - - Q - -
- - Q - - - - -
- - - - - - Q -
- Q - - - - - -
- - - Q - - - -

Q - - - - - - -
- - - - - Q - -
- - - - - - - Q
- - Q - - - - -
- - - - - - Q -
- - - Q - - - -
- Q - - - - - -
- - - - Q - - -

more--
Total N Queue 92``````
``````/*
Swift Program
Print all solutions in N-Queen Problem
*/
class MyBacktracking {
var counter : Int;
var size : Int;
init(_ size: Int) {
self.size = size;
self.counter = 0;
}
//Check valid element to insert a new n-queen element
func location(_ result: [
[Character]
], _ row: Int, _ col: Int) -> Int {
var status: Int = 1;
//Check element in row and column
var i: Int = 0;
while (i < self.size && status == 1) {
if (result[row][i] == "Q" || result[i][col] == "Q") {
//When element are exist
status = 0;
}
i += 1;
}
//Compare by diagonal element
i = 0;
let j: Int = row;
let k: Int = col;
while (i < self.size && status == 1) {
//Check condition of diagonal element
//top left
//bottom right
//bottom left
//top right

if ((j - i >= 0 && k - i >= 0 && result[j - i][k - i] == "Q") || (j + i) < self.size && (k + i) < self.size && result[j + i][k + i] == "Q" || (j - i >= 0 && k + i < self.size && result[j - i][k + i] == "Q") || (j + i < self.size && k - i >= 0 && result[j + i][k - i] == "Q")) {
status = 0;
}
i += 1;
}
return status;
}
//Display the value of result
func show_data(_ result: [
[Character]
]) {
var i: Int = 0;
while (i < self.size) {
var j: Int = 0;
while (j < self.size) {
print(" ", result[i][j], terminator: "");
j += 1;
}
print("\n", terminator: "");
i += 1;
}
print("\n\n", terminator: "");
}
func n_queen(_ result: inout [
[Character]
], _ row: Int) {
if (row > self.size || row < 0) {
return;
}
if (row == self.size) {
self.counter += 1;
self.show_data(result);
} else {
var i: Int = 0;
while (i < self.size) {
if (self.location(result, row, i) == 1) {
//When valid to insert Queen element
result[row][i] = "Q";
self.n_queen(&result, row + 1);
//set the initial value
result[row][i] = "-";
}
i += 1;
}
}
}
func defualt_value() {
//When implement more than 2 n-queen
//reset the counter value
self.counter = 0;

}
}
func main() {
let obj: MyBacktracking = MyBacktracking(8);
var result: [[Character]] = Array(repeating: Array(repeating:"-" , count: obj.size), count: obj.size);
obj.defualt_value();
obj.n_queen(&result, 0);
print(" Total N Queue ", obj.counter ,"\n", terminator: "");
}
main();```
```

#### Output

``````  Q  -  -  -  -  -  -  -
-  -  -  -  Q  -  -  -
-  -  -  -  -  -  -  Q
-  -  -  -  -  Q  -  -
-  -  Q  -  -  -  -  -
-  -  -  -  -  -  Q  -
-  Q  -  -  -  -  -  -
-  -  -  Q  -  -  -  -

Q  -  -  -  -  -  -  -
-  -  -  -  -  Q  -  -
-  -  -  -  -  -  -  Q
-  -  Q  -  -  -  -  -
-  -  -  -  -  -  Q  -
-  -  -  Q  -  -  -  -
-  Q  -  -  -  -  -  -
-  -  -  -  Q  -  -  -

Q  -  -  -  -  -  -  -
-  -  -  -  -  -  Q  -
-  -  -  Q  -  -  -  -
-  -  -  -  -  Q  -  -
-  -  -  -  -  -  -  Q
-  Q  -  -  -  -  -  -
-  -  -  -  Q  -  -  -
-  -  Q  -  -  -  -  -

Q  -  -  -  -  -  -  -
-  -  -  -  -  -  Q  -
-  -  -  -  Q  -  -  -
-  -  -  -  -  -  -  Q
-  Q  -  -  -  -  -  -
-  -  -  Q  -  -  -  -
-  -  -  -  -  Q  -  -
-  -  Q  -  -  -  -  -

-  Q  -  -  -  -  -  -
-  -  -  Q  -  -  -  -
-  -  -  -  -  Q  -  -
-  -  -  -  -  -  -  Q
-  -  Q  -  -  -  -  -
Q  -  -  -  -  -  -  -
-  -  -  -  -  -  Q  -
-  -  -  -  Q  -  -  -

-  Q  -  -  -  -  -  -
-  -  -  -  Q  -  -  -
-  -  -  -  -  -  Q  -
Q  -  -  -  -  -  -  -
-  -  Q  -  -  -  -  -
-  -  -  -  -  -  -  Q
-  -  -  -  -  Q  -  -
-  -  -  Q  -  -  -  -

-  Q  -  -  -  -  -  -
-  -  -  -  Q  -  -  -
-  -  -  -  -  -  Q  -
-  -  -  Q  -  -  -  -
Q  -  -  -  -  -  -  -
-  -  -  -  -  -  -  Q
-  -  -  -  -  Q  -  -
-  -  Q  -  -  -  -  -

-  Q  -  -  -  -  -  -
-  -  -  -  -  Q  -  -
Q  -  -  -  -  -  -  -
-  -  -  -  -  -  Q  -
-  -  -  Q  -  -  -  -
-  -  -  -  -  -  -  Q
-  -  Q  -  -  -  -  -
-  -  -  -  Q  -  -  -

-  Q  -  -  -  -  -  -
-  -  -  -  -  Q  -  -
-  -  -  -  -  -  -  Q
-  -  Q  -  -  -  -  -
Q  -  -  -  -  -  -  -
-  -  -  Q  -  -  -  -
-  -  -  -  -  -  Q  -
-  -  -  -  Q  -  -  -

-  Q  -  -  -  -  -  -
-  -  -  -  -  -  Q  -
-  -  Q  -  -  -  -  -
-  -  -  -  -  Q  -  -
-  -  -  -  -  -  -  Q
-  -  -  -  Q  -  -  -
Q  -  -  -  -  -  -  -
-  -  -  Q  -  -  -  -

-  Q  -  -  -  -  -  -
-  -  -  -  -  -  Q  -
-  -  -  -  Q  -  -  -
-  -  -  -  -  -  -  Q
Q  -  -  -  -  -  -  -
-  -  -  Q  -  -  -  -
-  -  -  -  -  Q  -  -
-  -  Q  -  -  -  -  -

-  Q  -  -  -  -  -  -
-  -  -  -  -  -  -  Q
-  -  -  -  -  Q  -  -
Q  -  -  -  -  -  -  -
-  -  Q  -  -  -  -  -
-  -  -  -  Q  -  -  -
-  -  -  -  -  -  Q  -
-  -  -  Q  -  -  -  -

-  -  Q  -  -  -  -  -
Q  -  -  -  -  -  -  -
-  -  -  -  -  -  Q  -
-  -  -  -  Q  -  -  -
-  -  -  -  -  -  -  Q
-  Q  -  -  -  -  -  -
-  -  -  Q  -  -  -  -
-  -  -  -  -  Q  -  -

-  -  Q  -  -  -  -  -
-  -  -  -  Q  -  -  -
-  Q  -  -  -  -  -  -
-  -  -  -  -  -  -  Q
Q  -  -  -  -  -  -  -
-  -  -  -  -  -  Q  -
-  -  -  Q  -  -  -  -
-  -  -  -  -  Q  -  -

-  -  Q  -  -  -  -  -
-  -  -  -  Q  -  -  -
-  Q  -  -  -  -  -  -
-  -  -  -  -  -  -  Q
-  -  -  -  -  Q  -  -
-  -  -  Q  -  -  -  -
-  -  -  -  -  -  Q  -
Q  -  -  -  -  -  -  -

-  -  Q  -  -  -  -  -
-  -  -  -  Q  -  -  -
-  -  -  -  -  -  Q  -
Q  -  -  -  -  -  -  -
-  -  -  Q  -  -  -  -
-  Q  -  -  -  -  -  -
-  -  -  -  -  -  -  Q
-  -  -  -  -  Q  -  -

-  -  Q  -  -  -  -  -
-  -  -  -  Q  -  -  -
-  -  -  -  -  -  -  Q
-  -  -  Q  -  -  -  -
Q  -  -  -  -  -  -  -
-  -  -  -  -  -  Q  -
-  Q  -  -  -  -  -  -
-  -  -  -  -  Q  -  -

-  -  Q  -  -  -  -  -
-  -  -  -  -  Q  -  -
-  Q  -  -  -  -  -  -
-  -  -  -  Q  -  -  -
-  -  -  -  -  -  -  Q
Q  -  -  -  -  -  -  -
-  -  -  -  -  -  Q  -
-  -  -  Q  -  -  -  -

more...
Total N Queue  92``````

## Resultant Output Explanation

The output of the program represents all the valid solutions to the N-Queen problem. Each solution is displayed as a chessboard with 'Q' representing a queen and '-' representing an empty cell. The program finds all possible solutions and prints them one by one.

For example, in the output shown, the first solution is:

```Q - - - - - - -
- - - - Q - - -
- - - - - - - Q
- - - - - Q - -
- - Q - - - - -
- - - - - - Q -
- Q - - - - - -
- - - Q - - - -
```

This solution represents a valid placement of 8 queens on an 8×8 chessboard. The program continues to find and display all other valid solutions.

## Time Complexity

The time complexity of the N-Queen problem is exponential, as the number of solutions grows exponentially with the size of the chessboard. In the worst case, the algorithm needs to explore all possible configurations, which results in a time complexity of O(N!). However, with pruning techniques and optimization, the actual runtime can be reduced significantly.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post