Last Updated : 03 Oct, 2023
Improve
We have discussed Knight’s tour and Rat in a Maze problem earlier as examples of Backtracking problems. Let us discuss N Queen as another example problem that can be solved using backtracking.
What is N-Queen problem?
The N Queen is the problem of placing N chess queens on an N×N chessboard so that no two queens attack each other.
For example, the following is a solution for the 4 Queen problem.
The expected output is in the form of a matrix that has ‘Q‘s for the blocks where queens are placed and the empty spaces are represented by ‘.’ . For example, the following is the output matrix for the above 4-Queen solution.
. Q ..
. . . Q
Q . . .
. . Q .
Recommended: Please solve it on “PRACTICE ” first, before moving on to the solution.
N Queen Problem using Backtracking:
The idea is to place queens one by one in different columns, starting from the leftmost column. When we place a queen in a column, we check for clashes with already placed queens. In the current column, if we find a row for which there is no clash, we mark this row and column as part of the solution. If we do not find such a row due to clashes, then we backtrack and return false.
Below is the recursive tree of the above approach:
Recursive tree for N Queen problem
Follow the steps mentioned below to implement the idea:
- Start in the leftmost column
- If all queens are placed return true
- Try all rows in the current column. Do the following for every row.
- If the queen can be placed safely in this row
- Then mark this [row, column] as part of the solution and recursively check if placing queen here leads to a solution.
- If placing the queen in [row, column] leads to a solution then return true.
- If placing queen doesn’t lead to a solution then unmark this [row, column] then backtrack and try other rows.
- If all rows have been tried and valid solution is not found return false to trigger backtracking.
- If the queen can be placed safely in this row
For better visualisation of this backtracking approach, please refer 4 Queen problem.
Note: We can also solve this problem by placing queens in rows as well.
Below is the implementation of the above approach:
C++
// C++ program to solve N Queen Problem using backtracking
#include <bits/stdc++.h>
#define N 4
using
namespace
std;
// A utility function to print solution
void
printSolution(
int
board[N][N])
{
for
(
int
i = 0; i < N; i++) {
for
(
int
j = 0; j < N; j++)
if
(board[i][j])
cout <<
"Q "
;
else
cout<<
". "
;
printf
(
"\n"
);
}
}
// A utility function to check if a queen can
// be placed on board[row][col]. Note that this
// function is called when "col" queens are
// already placed in columns from 0 to col -1.
// So we need to check only left side for
// attacking queens
bool
isSafe(
int
board[N][N],
int
row,
int
col)
{
int
i, j;
// Check this row on left side
for
(i = 0; i < col; i++)
if
(board[row][i])
return
false
;
// Check upper diagonal on left side
for
(i = row, j = col; i >= 0 && j >= 0; i--, j--)
if
(board[i][j])
return
false
;
// Check lower diagonal on left side
for
(i = row, j = col; j >= 0 && i < N; i++, j--)
if
(board[i][j])
return
false
;
return
true
;
}
// A recursive utility function to solve N
// Queen problem
bool
solveNQUtil(
int
board[N][N],
int
col)
{
// base case: If all queens are placed
// then return true
if
(col >= N)
return
true
;
// Consider this column and try placing
// this queen in all rows one by one
for
(
int
i = 0; i < N; i++) {
// Check if the queen can be placed on
// board[i][col]
if
(isSafe(board, i, col)) {
// Place this queen in board[i][col]
board[i][col] = 1;
// recur to place rest of the queens
if
(solveNQUtil(board, col + 1))
return
true
;
// If placing queen in board[i][col]
// doesn't lead to a solution, then
// remove queen from board[i][col]
board[i][col] = 0;
// BACKTRACK
}
}
// If the queen cannot be placed in any row in
// this column col then return false
return
false
;
}
// This function solves the N Queen problem using
// Backtracking. It mainly uses solveNQUtil() to
// solve the problem. It returns false if queens
// cannot be placed, otherwise, return true and
// prints placement of queens in the form of 1s.
// Please note that there may be more than one
// solutions, this function prints one of the
// feasible solutions.
bool
solveNQ()
{
int
board[N][N] = { { 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 } };
if
(solveNQUtil(board, 0) ==
false
) {
cout <<
"Solution does not exist"
;
return
false
;
}
printSolution(board);
return
true
;
}
// Driver program to test above function
int
main()
{
solveNQ();
return
0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
C
// C program to solve N Queen Problem using backtracking
#define N 4
#include <stdbool.h>
#include <stdio.h>
// A utility function to print solution
void
printSolution(
int
board[N][N])
{
for
(
int
i = 0; i < N; i++) {
for
(
int
j = 0; j < N; j++) {
if
(board[i][j])
printf
(
"Q "
);
else
printf
(
". "
);
}
printf
(
"\n"
);
}
}
// A utility function to check if a queen can
// be placed on board[row][col]. Note that this
// function is called when "col" queens are
// already placed in columns from 0 to col -1.
// So we need to check only left side for
// attacking queens
bool
isSafe(
int
board[N][N],
int
row,
int
col)
{
int
i, j;
// Check this row on left side
for
(i = 0; i < col; i++)
if
(board[row][i])
return
false
;
// Check upper diagonal on left side
for
(i = row, j = col; i >= 0 && j >= 0; i--, j--)
if
(board[i][j])
return
false
;
// Check lower diagonal on left side
for
(i = row, j = col; j >= 0 && i < N; i++, j--)
if
(board[i][j])
return
false
;
return
true
;
}
// A recursive utility function to solve N
// Queen problem
bool
solveNQUtil(
int
board[N][N],
int
col)
{
// Base case: If all queens are placed
// then return true
if
(col >= N)
return
true
;
// Consider this column and try placing
// this queen in all rows one by one
for
(
int
i = 0; i < N; i++) {
// Check if the queen can be placed on
// board[i][col]
if
(isSafe(board, i, col)) {
// Place this queen in board[i][col]
board[i][col] = 1;
// Recur to place rest of the queens
if
(solveNQUtil(board, col + 1))
return
true
;
// If placing queen in board[i][col]
// doesn't lead to a solution, then
// remove queen from board[i][col]
board[i][col] = 0;
// BACKTRACK
}
}
// If the queen cannot be placed in any row in
// this column col then return false
return
false
;
}
// This function solves the N Queen problem using
// Backtracking. It mainly uses solveNQUtil() to
// solve the problem. It returns false if queens
// cannot be placed, otherwise, return true and
// prints placement of queens in the form of 1s.
// Please note that there may be more than one
// solutions, this function prints one of the
// feasible solutions.
bool
solveNQ()
{
int
board[N][N] = { { 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 } };
if
(solveNQUtil(board, 0) ==
false
) {
printf
(
"Solution does not exist"
);
return
false
;
}
printSolution(board);
return
true
;
}
// Driver program to test above function
int
main()
{
solveNQ();
return
0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
Java
// Java program to solve N Queen Problem using backtracking
public
class
NQueenProblem {
final
int
N =
4
;
// A utility function to print solution
void
printSolution(
int
board[][])
{
for
(
int
i =
0
; i < N; i++) {
for
(
int
j =
0
; j < N; j++) {
if
(board[i][j] ==
1
)
System.out.print(
"Q "
);
else
System.out.print(
". "
);
}
System.out.println();
}
}
// A utility function to check if a queen can
// be placed on board[row][col]. Note that this
// function is called when "col" queens are already
// placeed in columns from 0 to col -1. So we need
// to check only left side for attacking queens
boolean
isSafe(
int
board[][],
int
row,
int
col)
{
int
i, j;
// Check this row on left side
for
(i =
0
; i < col; i++)
if
(board[row][i] ==
1
)
return
false
;
// Check upper diagonal on left side
for
(i = row, j = col; i >=
0
&& j >=
0
; i--, j--)
if
(board[i][j] ==
1
)
return
false
;
// Check lower diagonal on left side
for
(i = row, j = col; j >=
0
&& i < N; i++, j--)
if
(board[i][j] ==
1
)
return
false
;
return
true
;
}
// A recursive utility function to solve N
// Queen problem
boolean
solveNQUtil(
int
board[][],
int
col)
{
// Base case: If all queens are placed
// then return true
if
(col >= N)
return
true
;
// Consider this column and try placing
// this queen in all rows one by one
for
(
int
i =
0
; i < N; i++) {
// Check if the queen can be placed on
// board[i][col]
if
(isSafe(board, i, col)) {
// Place this queen in board[i][col]
board[i][col] =
1
;
// Recur to place rest of the queens
if
(solveNQUtil(board, col +
1
) ==
true
)
return
true
;
// If placing queen in board[i][col]
// doesn't lead to a solution then
// remove queen from board[i][col]
board[i][col] =
0
;
// BACKTRACK
}
}
// If the queen can not be placed in any row in
// this column col, then return false
return
false
;
}
// This function solves the N Queen problem using
// Backtracking. It mainly uses solveNQUtil () to
// solve the problem. It returns false if queens
// cannot be placed, otherwise, return true and
// prints placement of queens in the form of 1s.
// Please note that there may be more than one
// solutions, this function prints one of the
// feasible solutions.
boolean
solveNQ()
{
int
board[][] = { {
0
,
0
,
0
,
0
},
{
0
,
0
,
0
,
0
},
{
0
,
0
,
0
,
0
},
{
0
,
0
,
0
,
0
} };
if
(solveNQUtil(board,
0
) ==
false
) {
System.out.print(
"Solution does not exist"
);
return
false
;
}
printSolution(board);
return
true
;
}
// Driver program to test above function
public
static
void
main(String args[])
{
NQueenProblem Queen =
new
NQueenProblem();
Queen.solveNQ();
}
}
// This code is contributed by Abhishek Shankhadhar
Python3
# Python3 program to solve N Queen
# Problem using backtracking
global
N
N
=
4
def
printSolution(board):
for
i
in
range
(N):
for
j
in
range
(N):
if
board[i][j]
=
=
1
:
print
(
"Q"
,end
=
" "
)
else
:
print
(
"."
,end
=
" "
)
print
()
# A utility function to check if a queen can
# be placed on board[row][col]. Note that this
# function is called when "col" queens are
# already placed in columns from 0 to col -1.
# So we need to check only left side for
# attacking queens
def
isSafe(board, row, col):
# Check this row on left side
for
i
in
range
(col):
if
board[row][i]
=
=
1
:
return
False
# Check upper diagonal on left side
for
i, j
in
zip
(
range
(row,
-
1
,
-
1
),
range
(col,
-
1
,
-
1
)):
if
board[i][j]
=
=
1
:
return
False
# Check lower diagonal on left side
for
i, j
in
zip
(
range
(row, N,
1
),
range
(col,
-
1
,
-
1
)):
if
board[i][j]
=
=
1
:
return
False
return
True
def
solveNQUtil(board, col):
# Base case: If all queens are placed
# then return true
if
col >
=
N:
return
True
# Consider this column and try placing
# this queen in all rows one by one
for
i
in
range
(N):
if
isSafe(board, i, col):
# Place this queen in board[i][col]
board[i][col]
=
1
# Recur to place rest of the queens
if
solveNQUtil(board, col
+
1
)
=
=
True
:
return
True
# If placing queen in board[i][col
# doesn't lead to a solution, then
# queen from board[i][col]
board[i][col]
=
0
# If the queen can not be placed in any row in
# this column col then return false
return
False
# This function solves the N Queen problem using
# Backtracking. It mainly uses solveNQUtil() to
# solve the problem. It returns false if queens
# cannot be placed, otherwise return true and
# placement of queens in the form of 1s.
# note that there may be more than one
# solutions, this function prints one of the
# feasible solutions.
def
solveNQ():
board
=
[[
0
,
0
,
0
,
0
],
[
0
,
0
,
0
,
0
],
[
0
,
0
,
0
,
0
],
[
0
,
0
,
0
,
0
]]
if
solveNQUtil(board,
0
)
=
=
False
:
print
(
"Solution does not exist"
)
return
False
printSolution(board)
return
True
# Driver Code
if
__name__
=
=
'__main__'
:
solveNQ()
# This code is contributed by Divyanshu Mehta
C#
// C# program to solve N Queen Problem
// using backtracking
using
System;
class
GFG
{
readonly
int
N = 4;
// A utility function to print solution
void
printSolution(
int
[,]board)
{
for
(
int
i = 0; i < N; i++)
{
for
(
int
j = 0; j < N; j++)
{
if
(board[i, j] == 1)
Console.Write(
"Q "
);
else
Console.Write(
". "
);
}
Console.WriteLine();
}
}
// A utility function to check if a queen can
// be placed on board[row,col]. Note that this
// function is called when "col" queens are already
// placeed in columns from 0 to col -1. So we need
// to check only left side for attacking queens
bool
isSafe(
int
[,]board,
int
row,
int
col)
{
int
i, j;
// Check this row on left side
for
(i = 0; i < col; i++)
if
(board[row,i] == 1)
return
false
;
// Check upper diagonal on left side
for
(i = row, j = col; i >= 0 &&
j >= 0; i--, j--)
if
(board[i,j] == 1)
return
false
;
// Check lower diagonal on left side
for
(i = row, j = col; j >= 0 &&
i < N; i++, j--)
if
(board[i, j] == 1)
return
false
;
return
true
;
}
// A recursive utility function to solve N
// Queen problem
bool
solveNQUtil(
int
[,]board,
int
col)
{
// Base case: If all queens are placed
// then return true
if
(col >= N)
return
true
;
// Consider this column and try placing
// this queen in all rows one by one
for
(
int
i = 0; i < N; i++)
{
// Check if the queen can be placed on
// board[i,col]
if
(isSafe(board, i, col))
{
// Place this queen in board[i,col]
board[i, col] = 1;
// Recur to place rest of the queens
if
(solveNQUtil(board, col + 1) ==
true
)
return
true
;
// If placing queen in board[i,col]
// doesn't lead to a solution then
// remove queen from board[i,col]
board[i, col] = 0;
// BACKTRACK
}
}
// If the queen can not be placed in any row in
// this column col, then return false
return
false
;
}
// This function solves the N Queen problem using
// Backtracking. It mainly uses solveNQUtil () to
// solve the problem. It returns false if queens
// cannot be placed, otherwise, return true and
// prints placement of queens in the form of 1s.
// Please note that there may be more than one
// solutions, this function prints one of the
// feasible solutions.
bool
solveNQ()
{
int
[,]board = {{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 }};
if
(solveNQUtil(board, 0) ==
false
)
{
Console.Write(
"Solution does not exist"
);
return
false
;
}
printSolution(board);
return
true
;
}
// Driver Code
public
static
void
Main(String []args)
{
GFG Queen =
new
GFG();
Queen.solveNQ();
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// JavaScript program to solve N Queen
// Problem using backtracking
const N = 4
function
printSolution(board)
{
for
(let i = 0; i < N; i++)
{
for
(let j = 0; j < N; j++)
{
if
(board[i][j] == 1)
document.write(
"Q "
)
else
document.write(
". "
)
}
document.write(
"</br>"
)
}
}
// A utility function to check if a queen can
// be placed on board[row][col]. Note that this
// function is called when "col" queens are
// already placed in columns from 0 to col -1.
// So we need to check only left side for
// attacking queens
function
isSafe(board, row, col)
{
// Check this row on left side
for
(let i = 0; i < col; i++){
if
(board[row][i] == 1)
return
false
}
// Check upper diagonal on left side
for
(i = row, j = col; i >= 0 && j >= 0; i--, j--)
if
(board[i][j])
return
false
// Check lower diagonal on left side
for
(i = row, j = col; j >= 0 && i < N; i++, j--)
if
(board[i][j])
return
false
return
true
}
function
solveNQUtil(board, col){
// base case: If all queens are placed
// then return true
if
(col >= N)
return
true
// Consider this column and try placing
// this queen in all rows one by one
for
(let i=0;i<N;i++){
if
(isSafe(board, i, col)==
true
){
// Place this queen in board[i][col]
board[i][col] = 1
// recur to place rest of the queens
if
(solveNQUtil(board, col + 1) ==
true
)
return
true
// If placing queen in board[i][col
// doesn't lead to a solution, then
// queen from board[i][col]
board[i][col] = 0
}
}
// if the queen can not be placed in any row in
// this column col then return false
return
false
}
// This function solves the N Queen problem using
// Backtracking. It mainly uses solveNQUtil() to
// solve the problem. It returns false if queens
// cannot be placed, otherwise return true and
// placement of queens in the form of 1s.
// note that there may be more than one
// solutions, this function prints one of the
// feasible solutions.
function
solveNQ(){
let board = [ [0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0] ]
if
(solveNQUtil(board, 0) ==
false
){
document.write(
"Solution does not exist"
)
return
false
}
printSolution(board)
return
true
}
// Driver Code
solveNQ()
// This code is contributed by shinjanpatra
</script>
Output
. . Q . Q . . . . . . Q . Q . .
Time Complexity: O(N!)
Auxiliary Space: O(N2)
Further Optimization in is_safe() function:
The idea is not to check every element in the right and left diagonal, instead use the property of diagonals:
- The sum of i and j is constant and unique for each right diagonal, where i is the row of elements and j is the
column of elements.- The difference between i and j is constant and unique for each left diagonal, where i and j are row and column of element respectively.
Below is the implementation:
C++
// C++ program to solve N Queen Problem using backtracking
#include <bits/stdc++.h>
using
namespace
std;
#define N 4
// ld is an array where its indices indicate row-col+N-1
// (N-1) is for shifting the difference to store negative
// indices
int
ld[30] = { 0 };
// rd is an array where its indices indicate row+col
// and used to check whether a queen can be placed on
// right diagonal or not
int
rd[30] = { 0 };
// Column array where its indices indicates column and
// used to check whether a queen can be placed in that
// row or not*/
int
cl[30] = { 0 };
// A utility function to print solution
void
printSolution(
int
board[N][N])
{
for
(
int
i = 0; i < N; i++) {
for
(
int
j = 0; j < N; j++)
cout <<
" "
<< (board[i][j]==1?
"Q"
:
"."
) <<
" "
;
cout << endl;
}
}
// A recursive utility function to solve N
// Queen problem
bool
solveNQUtil(
int
board[N][N],
int
col)
{
// Base case: If all queens are placed
// then return true
if
(col >= N)
return
true
;
// Consider this column and try placing
// this queen in all rows one by one
for
(
int
i = 0; i < N; i++) {
// Check if the queen can be placed on
// board[i][col]
// To check if a queen can be placed on
// board[row][col].We just need to check
// ld[row-col+n-1] and rd[row+coln] where
// ld and rd are for left and right
// diagonal respectively
if
((ld[i - col + N - 1] != 1 && rd[i + col] != 1)
&& cl[i] != 1) {
// Place this queen in board[i][col]
board[i][col] = 1;
ld[i - col + N - 1] = rd[i + col] = cl[i] = 1;
// Recur to place rest of the queens
if
(solveNQUtil(board, col + 1))
return
true
;
// If placing queen in board[i][col]
// doesn't lead to a solution, then
// remove queen from board[i][col]
board[i][col] = 0;
// BACKTRACK
ld[i - col + N - 1] = rd[i + col] = cl[i] = 0;
}
}
// If the queen cannot be placed in any row in
// this column col then return false
return
false
;
}
// This function solves the N Queen problem using
// Backtracking. It mainly uses solveNQUtil() to
// solve the problem. It returns false if queens
// cannot be placed, otherwise, return true and
// prints placement of queens in the form of 1s.
// Please note that there may be more than one
// solutions, this function prints one of the
// feasible solutions.
bool
solveNQ()
{
int
board[N][N] = { { 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 } };
if
(solveNQUtil(board, 0) ==
false
) {
cout <<
"Solution does not exist"
;
return
false
;
}
printSolution(board);
return
true
;
}
// Driver program to test above function
int
main()
{
solveNQ();
return
0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
Java
// Java program to solve N Queen Problem using backtracking
import
java.util.*;
class
GFG {
static
int
N =
4
;
// ld is an array where its indices indicate row-col+N-1
// (N-1) is for shifting the difference to store
// negative indices
static
int
[] ld =
new
int
[
30
];
// rd is an array where its indices indicate row+col
// and used to check whether a queen can be placed on
// right diagonal or not
static
int
[] rd =
new
int
[
30
];
// Column array where its indices indicates column and
// used to check whether a queen can be placed in that
// row or not
static
int
[] cl =
new
int
[
30
];
// A utility function to print solution
static
void
printSolution(
int
board[][])
{
for
(
int
i =
0
; i < N; i++) {
for
(
int
j =
0
; j < N; j++)
System.out.printf(
" %d "
, board[i][j]);
System.out.printf(
"\n"
);
}
}
// A recursive utility function to solve N
// Queen problem
static
boolean
solveNQUtil(
int
board[][],
int
col)
{
// Base case: If all queens are placed
// then return true
if
(col >= N)
return
true
;
// Consider this column and try placing
// this queen in all rows one by one
for
(
int
i =
0
; i < N; i++) {
// Check if the queen can be placed on
// board[i][col]
// To check if a queen can be placed on
// board[row][col].We just need to check
// ld[row-col+n-1] and rd[row+coln] where
// ld and rd are for left and right
// diagonal respectively
if
((ld[i - col + N -
1
] !=
1
&& rd[i + col] !=
1
)
&& cl[i] !=
1
) {
// Place this queen in board[i][col]
board[i][col] =
1
;
ld[i - col + N -
1
] = rd[i + col] = cl[i]
=
1
;
// Recur to place rest of the queens
if
(solveNQUtil(board, col +
1
))
return
true
;
// If placing queen in board[i][col]
// doesn't lead to a solution, then
// remove queen from board[i][col]
board[i][col] =
0
;
// BACKTRACK
ld[i - col + N -
1
] = rd[i + col] = cl[i]
=
0
;
}
}
// If the queen cannot be placed in any row in
// this column col then return false
return
false
;
}
// This function solves the N Queen problem using
// Backtracking. It mainly uses solveNQUtil() to
// solve the problem. It returns false if queens
// cannot be placed, otherwise, return true and
// prints placement of queens in the form of 1s.
// Please note that there may be more than one
// solutions, this function prints one of the
// feasible solutions.
static
boolean
solveNQ()
{
int
board[][] = { {
0
,
0
,
0
,
0
},
{
0
,
0
,
0
,
0
},
{
0
,
0
,
0
,
0
},
{
0
,
0
,
0
,
0
} };
if
(solveNQUtil(board,
0
) ==
false
) {
System.out.printf(
"Solution does not exist"
);
return
false
;
}
printSolution(board);
return
true
;
}
// Driver Code
public
static
void
main(String[] args)
{
solveNQ();
}
}
// This code is contributed by Princi Singh
Python3
# Python3 program to solve N Queen Problem using
# backtracking
N
=
4
# ld is an array where its indices indicate row-col+N-1
# (N-1) is for shifting the difference to store negative
# indices
ld
=
[
0
]
*
30
# rd is an array where its indices indicate row+col
# and used to check whether a queen can be placed on
# right diagonal or not
rd
=
[
0
]
*
30
# Column array where its indices indicates column and
# used to check whether a queen can be placed in that
# row or not
cl
=
[
0
]
*
30
# A utility function to print solution
def
printSolution(board):
for
i
in
range
(N):
for
j
in
range
(N):
print
(board[i][j], end
=
" "
)
print
()
# A recursive utility function to solve N
# Queen problem
def
solveNQUtil(board, col):
# Base case: If all queens are placed
# then return True
if
(col >
=
N):
return
True
# Consider this column and try placing
# this queen in all rows one by one
for
i
in
range
(N):
# Check if the queen can be placed on board[i][col]
# To check if a queen can be placed on
# board[row][col] We just need to check
# ld[row-col+n-1] and rd[row+coln]
# where ld and rd are for left and
# right diagonal respectively
if
((ld[i
-
col
+
N
-
1
] !
=
1
and
rd[i
+
col] !
=
1
)
and
cl[i] !
=
1
):
# Place this queen in board[i][col]
board[i][col]
=
1
ld[i
-
col
+
N
-
1
]
=
rd[i
+
col]
=
cl[i]
=
1
# Recur to place rest of the queens
if
(solveNQUtil(board, col
+
1
)):
return
True
# If placing queen in board[i][col]
# doesn't lead to a solution,
# then remove queen from board[i][col]
board[i][col]
=
0
# BACKTRACK
ld[i
-
col
+
N
-
1
]
=
rd[i
+
col]
=
cl[i]
=
0
# If the queen cannot be placed in
# any row in this column col then return False
return
False
# This function solves the N Queen problem using
# Backtracking. It mainly uses solveNQUtil() to
# solve the problem. It returns False if queens
# cannot be placed, otherwise, return True and
# prints placement of queens in the form of 1s.
# Please note that there may be more than one
# solutions, this function prints one of the
# feasible solutions.
def
solveNQ():
board
=
[[
0
,
0
,
0
,
0
],
[
0
,
0
,
0
,
0
],
[
0
,
0
,
0
,
0
],
[
0
,
0
,
0
,
0
]]
if
(solveNQUtil(board,
0
)
=
=
False
):
printf(
"Solution does not exist"
)
return
False
printSolution(board)
return
True
# Driver Code
if
__name__
=
=
'__main__'
:
solveNQ()
# This code is contributed by SHUBHAMSINGH10
C#
// C# program to solve N Queen Problem using backtracking
using
System;
class
GFG {
static
int
N = 4;
// ld is an array where its indices indicate row-col+N-1
// (N-1) is for shifting the difference to store
// negative indices
static
int
[] ld =
new
int
[30];
// rd is an array where its indices indicate row+col
// and used to check whether a queen can be placed on
// right diagonal or not
static
int
[] rd =
new
int
[30];
// Column array where its indices indicates column and
// used to check whether a queen can be placed in that
// row or not
static
int
[] cl =
new
int
[30];
// A utility function to print solution
static
void
printSolution(
int
[, ] board)
{
for
(
int
i = 0; i < N; i++) {
for
(
int
j = 0; j < N; j++)
Console.Write(
" {0} "
, board[i, j]);
Console.Write(
"\n"
);
}
}
// A recursive utility function to solve N
// Queen problem
static
bool
solveNQUtil(
int
[, ] board,
int
col)
{
// Base case: If all queens are placed
// then return true
if
(col >= N)
return
true
;
// Consider this column and try placing
// this queen in all rows one by one
for
(
int
i = 0; i < N; i++) {
// Check if the queen can be placed on
// board[i,col]
// To check if a queen can be placed on
// board[row,col].We just need to check
// ld[row-col+n-1] and rd[row+coln] where
// ld and rd are for left and right
// diagonal respectively
if
((ld[i - col + N - 1] != 1
&& rd[i + col] != 1)
&& cl[i] != 1) {
// Place this queen in board[i,col]
board[i, col] = 1;
ld[i - col + N - 1] = rd[i + col] = cl[i]
= 1;
// Recur to place rest of the queens
if
(solveNQUtil(board, col + 1))
return
true
;
// If placing queen in board[i,col]
// doesn't lead to a solution, then
// remove queen from board[i,col]
board[i, col] = 0;
// BACKTRACK
ld[i - col + N - 1] = rd[i + col] = cl[i]
= 0;
}
}
// If the queen cannot be placed in any row in
// this column col then return false
return
false
;
}
// This function solves the N Queen problem using
// Backtracking. It mainly uses solveNQUtil() to
// solve the problem. It returns false if queens
// cannot be placed, otherwise, return true and
// prints placement of queens in the form of 1s.
// Please note that there may be more than one
// solutions, this function prints one of the
// feasible solutions.
static
bool
solveNQ()
{
int
[, ] board = { { 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 } };
if
(solveNQUtil(board, 0) ==
false
) {
Console.Write(
"Solution does not exist"
);
return
false
;
}
printSolution(board);
return
true
;
}
// Driver Code
public
static
void
Main(String[] args)
{
solveNQ();
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript code to implement the approach
let N = 4;
// ld is an array where its indices indicate row-col+N-1
// (N-1) is for shifting the difference to store negative
// indices
let ld =
new
Array(30);
// rd is an array where its indices indicate row+col
// and used to check whether a queen can be placed on
// right diagonal or not
let rd =
new
Array(30);
// Column array where its indices indicates column and
// used to check whether a queen can be placed in that
// row or not
let cl =
new
Array(30);
// A utility function to print solution
function
printSolution( board)
{
for
(let i = 0; i < N; i++)
{
for
(let j = 0; j < N; j++)
document.write(board[i][j] +
" "
);
document.write(
"<br/>"
);
}
}
// A recursive utility function to solve N
// Queen problem
function
solveNQUtil(board, col)
{
// Base case: If all queens are placed
// then return true
if
(col >= N)
return
true
;
// Consider this column and try placing
// this queen in all rows one by one
for
(let i = 0; i < N; i++)
{
// Check if the queen can be placed on
// board[i][col]
// To check if a queen can be placed on
// board[row][col].We just need to check
// ld[row-col+n-1] and rd[row+coln] where
// ld and rd are for left and right
// diagonal respectively
if
((ld[i - col + N - 1] != 1 &&
rd[i + col] != 1) && cl[i] != 1)
{
// Place this queen in board[i][col]
board[i][col] = 1;
ld[i - col + N - 1] =
rd[i + col] = cl[i] = 1;
// Recur to place rest of the queens
if
(solveNQUtil(board, col + 1))
return
true
;
// If placing queen in board[i][col]
// doesn't lead to a solution, then
// remove queen from board[i][col]
board[i][col] = 0;
// BACKTRACK
ld[i - col + N - 1] =
rd[i + col] = cl[i] = 0;
}
}
// If the queen cannot be placed in any row in
// this column col then return false
return
false
;
}
// This function solves the N Queen problem using
// Backtracking. It mainly uses solveNQUtil() to
// solve the problem. It returns false if queens
// cannot be placed, otherwise, return true and
// prints placement of queens in the form of 1s.
// Please note that there may be more than one
// solutions, this function prints one of the
// feasible solutions.
function
solveNQ()
{
let board = [[ 0, 0, 0, 0 ],
[ 0, 0, 0, 0 ],
[ 0, 0, 0, 0 ],
[ 0, 0, 0, 0 ]];
if
(solveNQUtil(board, 0) ==
false
)
{
document.write(
"Solution does not exist"
);
return
false
;
}
printSolution(board);
return
true
;
}
// Driver code
solveNQ();
// This code is contributed by sanjoy_62.
</script>
Output
. . Q . Q . . . . . . Q . Q . .
Time Complexity: O(N!)
Auxiliary Space: O(N)
Related Articles:
- Printing all solutions in N-Queen Problem