What is the N Queen problem?
An N queen problem is a backtracking problem to placing Queen in a n x n shape chessboard so that each Queen in the chessboard is not in the same column and row. The Queen can't be face to face with each other in the chessboard with respect to row and column (Vertically, Horizontally, and Diagonally). For this post, we consider the N queen as 8 queens to understand the problem better. As there are many numbers of solutions and discussions about the N queen problem on the web, this website brings a different dynamic solution and discussion about the N queen problem.
A 8 queen chessboard
Why is the N queen problem called a backtracking problem?
First of all, the backtracking process is an algorithmic approach that is used to find many solutions recursively with the incrementation of these process steps. The N queen problem is just like the backtracking technique. N queen algorithm finds the solution in an incremental recursive process by using many directional (row-column-diagonal) steps. That is why the N queen problem is called or known as a backtracking problem.
N queen backtracking process
How can we generate or solve an N queen chessboard?
An N queen problem can be solved following its algorithm. The generated board of the N queen problem is made with the binary number, that is "1" and "0". The binary number "1" said that the queen can be placed in the specific row-column position that is generated by the algorithm. The "0" said the opposite. For the proper understanding, we replace the "1" with "Q" (Queen) and "0" with "-" (empty).
1 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0
0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 1
0 1 0 0 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 0 1 0 0
0 0 1 0 0 0 0 0
After replacing the "1" with "Q" (Queen) and "0" with "-" (empty).
Q - - - - - - -
- - - - - - Q -
- - - - Q - - -
- - - - - - - Q
- Q - - - - - -
- - - Q - - - -
- - - - - Q - -
- - Q - - - - -
Is N queen and 8 queen are the same problem?
80% Yes, but 20% no. N represents the number 8 for the 8 Queen problem. That is why it is "Yes". As N represents many natural numbers up to 2 (4, 5, 6, 7, ..., and so on) that N queen and 8 queens are not the same problems but 8 queen is the N queen. And the real-life chess board is 8 * 8 size.
n queen problem algorithm
1. Define the board size.
2. Initialize each board cell with zero.
3. Check the board cell position is safe (ith for the row, jth for the column, and kth for the diagonal(row, column).
The ith row and jth column then return True.
Now check diagonally for k=1 to i-1.
4. If it is safe, then place a queen in the cell.
Otherwise, it returns False.
5. Or increment one step (the backtracking process) to find a safe place for the queen.
Checking A queen Horizontally, Vertically, and Diagonally
n queen problem in C++ (n queens problem using backtracking in C++)
This solution generates only two possible solutions using backtracking.
#include<iostream>
using namespace std;
#define sz 1100
int board[sz][sz];
bool isSafe(int r, int c, int n)
{
int i, j;
for(i=c-1; i>=0; i--)
{
if(board[r][i]==1)
return false;
}
i=r-1;
j=c-1;
while(i>=0 && j>=0)
{
if(board[i][j]==1)
return false;
i--;
j--;
}
i=r+1;
j=c-1;
while(i<n && j>=0)
{
if(board[i][j]==1)
return false;
i++;
j--;
}
return true;
}
bool solveNQueen(int n, int col)
{
int r;
if(col==n)
return true;
for(r=0; r<n; r++)
{
if(isSafe(r, col, n))
{
board[r][col]=1;
if(solveNQueen(n, col+1))
return true;
board[r][col]=0;
}
}
return false;
}
int main()
{
int n, i, j;
cin>>n;
for(i=0; i<n; i++)
{
for(j=0; j<n; j++)
{
board[i][j]=0;
}
}
if(solveNQueen(n, 0))
{
cout<<"Queen Position Board 1\n";
for(i=0; i<n; i++)
{
for(j=0; j<n; j++)
{
if(board[i][j]==1)
cout<<"Q"<<" ";
else
cout<<"-"<<" ";
}
cout<<endl;
}
cout<<"\nQueen Position Board 2\n";
for(i=n-1; i>=0; i--)
{
for(j=0; j<n; j++)
{
if(board[i][j]==1)
cout<<"Q"<<" ";
else
cout<<"-"<<" ";
}
cout<<endl;
}
}
else
{
cout<<"No Solution "<<endl;
}
return 0;
}
Sample Input:
8
Sample Output:
Queen Position Board 1
Q - - - - - - -
- - - - - - Q -
- - - - Q - - -
- - - - - - - Q
- Q - - - - - -
- - - Q - - - -
- - - - - Q - -
- - Q - - - - -
Queen Position Board 2
- - Q - - - - -
- - - - - Q - -
- - - Q - - - -
- Q - - - - - -
- - - - - - - Q
- - - - Q - - -
- - - - - - Q -
Q - - - - - - -
n queen problem in Python (n queens problem using backtracking in Python)
This solution generates all possible solutions using backtracking.
class GenerateBoardSolutions:
def __init__(self):
self.board = [0] * 1000000
def IsQueenSafe(self, i, j):
for k in range(1, i):
if (self.board[k] == j) or abs(self.board[k] - j) == abs(k - i):
return False
return True
def GeneratedQueenBoard(self, n, m):
print(m)
for i in range(1, n + 1):
for j in range(1, n + 1):
if self.board[i] != j:
print('\t-', end=' ')
else:
print('\tQ', end=' ')
print()
print()
def SolveNQueen(self, i, j):
for k in range(1, n + 1):
if self.IsQueenSafe(i, k):
self.board[i] = k
if i == n:
self.GeneratedQueenBoard(n, "Queens Position Boards")
else:
self.SolveNQueen(i + 1, n)
if __name__=='__main__':
n = int(input())
GenerateBoardSolutions = GenerateBoardSolutions()
GenerateBoardSolutions.SolveNQueen(1, n)
Sample Input:
8
Sample Output:
Queens Position Boards
Q - - - - - - -
- - - - Q - - -
- - - - - - - Q
- - - - - Q - -
- - Q - - - - -
- - - - - - Q -
- Q - - - - - -
- - - Q - - - -
Queens Position Boards
Q - - - - - - -
- - - - - Q - -
- - - - - - - Q
- - Q - - - - -
- - - - - - Q -
- - - Q - - - -
- Q - - - - - -
- - - - Q - - -
Queens Position Boards
Q - - - - - - -
- - - - - - Q -
- - - Q - - - -
- - - - - Q - -
- - - - - - - Q
- Q - - - - - -
- - - - Q - - -
- - Q - - - - -
and so on.
Why above N queen solution is dynamic?
Because you can generate an N queen chess board for any number of chessboard shapes.