N Queen Problem
What is N Queen Problem?
In N-Queen problem, we are given an NxN chessboard and we have to place N number of queens on the board in such a way that no two queens attack each other. A queen will attack another queen if it is placed in horizontal, vertical or diagonal points in its way. The most popular approach for solving the N Queen puzzle is Backtracking.
Input Output Scenario
Suppose the given chessboard is of size 4x4 and we have to arrange exactly 4 queens in it. The solution arrangement is shown in the figure below −
The final solution matrix will be −
0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0
Backtracking Approach to solve N Queens Problem
In the naive method to solve n queen problem, the algorithm generates all possible solutions. Then, it explores all of the solutions one by one. If a generated solution satisfies the constraint of the problem, it prints that solution.
Follow the below steps to solve n queen problem using the backtracking approach −
Place the first queen in the top-left cell of the chessboard.
After placing a queen in the first cell, mark the position as a part of the solution and then recursively check if this will lead to a solution.
Now, if placing the queen doesn’t lead to a solution. Then go to the first step and place queens in other cells. Repeat until all cells are tried.
If placing queen returns a lead to solution return TRUE.
If all queens are placed return TRUE.
If all rows are tried and no solution is found, return FALSE.
Example
The following example illustrates how to solve the n-queen problem with 5 queens in various programming languages.
#include<stdio.h>
#define BOARD_SIZE 5
void displayChess(int chBoard[BOARD_SIZE][BOARD_SIZE]) {
for (int row = 0; row < BOARD_SIZE; row++) {
for (int col = 0; col < BOARD_SIZE; col++)
printf("%d ", chBoard[row][col]);
printf("
");
}
}
int isQueenPlaceValid(int chBoard[BOARD_SIZE][BOARD_SIZE], int crntRow, int crntCol) {
// checking if queen is in the left or not
for (int i = 0; i < crntCol; i++)
if (chBoard[crntRow][i])
return 0;
for (int i = crntRow, j = crntCol; i >= 0 && j >= 0; i--, j--)
//checking if queen is in the left upper diagonal or not
if (chBoard[i][j])
return 0;
for (int i = crntRow, j = crntCol; j >= 0 && i < BOARD_SIZE; i++, j--)
//checking if queen is in the left lower diagonal or not
if (chBoard[i][j])
return 0;
return 1;
}
int solveProblem(int chBoard[BOARD_SIZE][BOARD_SIZE], int crntCol) {
//when N queens are placed successfully
if (crntCol >= BOARD_SIZE)
return 1;
// checking placement of queen is possible or not
for (int i = 0; i < BOARD_SIZE; i++) {
if (isQueenPlaceValid(chBoard, i, crntCol)) {
//if validate, place the queen at place (i, col)
chBoard[i][crntCol] = 1;
//Go for the other columns recursively
if (solveProblem(chBoard, crntCol + 1))
return 1;
//When no place is vacant remove that queen
chBoard[i][crntCol] = 0;
}
}
return 0;
}
int displaySolution() {
int chBoard[BOARD_SIZE][BOARD_SIZE];
for(int i = 0; i < BOARD_SIZE; i++)
for(int j = 0; j < BOARD_SIZE; j++)
//set all elements to 0
chBoard[i][j] = 0;
//starting from 0th column
if (solveProblem(chBoard, 0) == 0) {
printf("Solution does not exist");
return 0;
}
displayChess(chBoard);
return 1;
}
int main() {
displaySolution();
return 0;
}
#include<iostream>
using namespace std;
#define BOARD_SIZE 5
void displayChess(int chBoard[BOARD_SIZE][BOARD_SIZE]) {
for (int row = 0; row < BOARD_SIZE; row++) {
for (int col = 0; col < BOARD_SIZE; col++)
cout << chBoard[row][col] << " ";
cout << endl;
}
}
bool isQueenPlaceValid(int chBoard[BOARD_SIZE][BOARD_SIZE], int crntRow, int crntCol) {
// checking if queen is in the left or not
for (int i = 0; i < crntCol; i++)
if (chBoard[crntRow][i])
return false;
for (int i = crntRow, j = crntCol; i >= 0 && j >= 0; i--, j--)
//checking if queen is in the left upper diagonal or not
if (chBoard[i][j])
return false;
for (int i = crntRow, j = crntCol; j >= 0 && i < BOARD_SIZE; i++, j--)
//checking if queen is in the left lower diagonal or not
if (chBoard[i][j])
return false;
return true;
}
bool solveProblem(int chBoard[BOARD_SIZE][BOARD_SIZE], int crntCol) {
//when N queens are placed successfully
if (crntCol >= BOARD_SIZE)
return true;
// checking placement of queen is possible or not
for (int i = 0; i < BOARD_SIZE; i++) {
if (isQueenPlaceValid(chBoard, i, crntCol)) {
//if validate, place the queen at place (i, col)
chBoard[i][crntCol] = 1;
//Go for the other columns recursively
if (solveProblem(chBoard, crntCol + 1))
return true;
//When no place is vacant remove that queen
chBoard[i][crntCol] = 0;
}
}
return false;
}
bool displaySolution() {
int chBoard[BOARD_SIZE][BOARD_SIZE];
for(int i = 0; i < BOARD_SIZE; i++)
for(int j = 0; j < BOARD_SIZE; j++)
//set all elements to 0
chBoard[i][j] = 0;
//starting from 0th column
if (solveProblem(chBoard, 0) == false) {
cout << "Solution does not exist";
return false;
}
displayChess(chBoard);
return true;
}
int main() {
displaySolution();
}
public class Main {
static final int BOARD_SIZE = 5;
static void displayChess(int chBoard[][]) {
for (int row = 0; row < BOARD_SIZE; row++) {
for (int col = 0; col < BOARD_SIZE; col++)
System.out.print(chBoard[row][col] + " ");
System.out.println();
}
}
static boolean isQueenPlaceValid(int chBoard[][], int crntRow, int crntCol) {
// checking if queen is in the left or not
for (int i = 0; i < crntCol; i++)
if (chBoard[crntRow][i] == 1)
return false;
for (int i = crntRow, j = crntCol; i >= 0 && j >= 0; i--, j--)
//checking if queen is in the left upper diagonal or not
if (chBoard[i][j] == 1)
return false;
for (int i = crntRow, j = crntCol; j >= 0 && i < BOARD_SIZE; i++, j--)
//checking if queen is in the left lower diagonal or not
if (chBoard[i][j] == 1)
return false;
return true;
}
static boolean solveProblem(int chBoard[][], int crntCol) {
//when N queens are placed successfully
if (crntCol >= BOARD_SIZE)
return true;
// checking placement of queen is possible or not
for (int i = 0; i < BOARD_SIZE; i++) {
if (isQueenPlaceValid(chBoard, i, crntCol)) {
//if validate, place the queen at place (i, col)
chBoard[i][crntCol] = 1;
//Go for the other columns recursively
if (solveProblem(chBoard, crntCol + 1))
return true;
//When no place is vacant remove that queen
chBoard[i][crntCol] = 0;
}
}
return false;
}
static boolean displaySolution() {
int chBoard[][] = new int[BOARD_SIZE][BOARD_SIZE];
for(int i = 0; i < BOARD_SIZE; i++)
for(int j = 0; j < BOARD_SIZE; j++)
//set all elements to 0
chBoard[i][j] = 0;
//starting from 0th column
if (!solveProblem(chBoard, 0)) {
System.out.println("Solution does not exist");
return false;
}
displayChess(chBoard);
return true;
}
public static void main(String[] args) {
displaySolution();
}
}
BOARD_SIZE = 5
def displayChess(chBoard):
for row in range(BOARD_SIZE):
for col in range(BOARD_SIZE):
print(chBoard[row][col], end=" ")
print()
def isQueenPlaceValid(chBoard, crntRow, crntCol):
# checking if queen is in the left or not
for i in range(crntCol):
if chBoard[crntRow][i]:
return False
for i, j in zip(range(crntRow, -1, -1), range(crntCol, -1, -1)):
#checking if queen is in the left upper diagonal or not
if chBoard[i][j]:
return False
for i, j in zip(range(crntRow, BOARD_SIZE), range(crntCol, -1, -1)):
#checking if queen is in the left lower diagonal or not
if chBoard[i][j]:
return False
return True
def solveProblem(chBoard, crntCol):
#when N queens are placed successfully
if crntCol >= BOARD_SIZE:
return True
# checking placement of queen is possible or not
for i in range(BOARD_SIZE):
if isQueenPlaceValid(chBoard, i, crntCol):
#if validate, place the queen at place (i, col)
chBoard[i][crntCol] = 1
#Go for the other columns recursively
if solveProblem(chBoard, crntCol + 1):
return True
#When no place is vacant remove that queen
chBoard[i][crntCol] = 0
return False
def displaySolution():
chBoard = [[0 for _ in range(BOARD_SIZE)] for _ in range(BOARD_SIZE)]
#starting from 0th column
if not solveProblem(chBoard, 0):
print("Solution does not exist")
return False
displayChess(chBoard)
return True
if __name__ == "__main__":
displaySolution()
Output
1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0
