Merge pull request abhpd#216 from amitgeed/patch-1

added new cpp file for n_queens_problem
snigdhaop · Oct 25, 2020 · f8714ba · f8714ba
2 parents 7e97e5c + 49ce3fa
commit f8714ba
Showing 1 changed file with 65 additions and 0 deletions.
diff --git a/C++/Data Structure/n_queens_problem.cpp b/C++/Data Structure/n_queens_problem.cpp
@@ -0,0 +1,65 @@
+#include<iostream>
+using namespace std;
+bool isSafe(int board[][10], int row, int col, int n)	//This function is to check whether queen can be placed safely or not
+{
+	for(int i=0;i<col;i++)
+	{
+		if(board[row][i] == 1)
+		{
+			return false;
+		}
+	}
+	for(int i=row,j=col;i>=0 && j>=0;i--,j--)
+	{
+		if(board[i][j] ==1)
+		{
+			return false;
+		}
+	}
+	for(int i=row,j=col;i<n && j>=0;i++,j--)
+	{
+		if(board[i][j] ==1)
+		{
+			return false;
+		}
+	}
+	return true;
+}
+bool nQueen(int board[][10], int col, int n)
+{
+	if(col>=n)
+	{
+		for(int i=0;i<n;i++)	//Simple printing of the board 
+		{
+			for(int j=0;j<n;j++)
+			{
+				cout<<board[i][j]<<" ";
+			}
+			cout<<endl;
+		}
+		return true;
+	}
+	for(int i=0;i<n;i++)
+	{
+		if(isSafe(board,i,col,n))
+		{
+			board[i][col]=1;
+			if(nQueen(board,col+1,n))	//Recursively calling the function to keep another queen
+			{
+				return true;
+			}
+			board[i][col]=0; 	//Backtracking
+		}
+	}
+	return false;	//if control reaches over here that means there is no way to place queen on such a board
+}
+int main()
+{
+	int n;
+	int board[10][10]={0};	//Initially no queen on board
+	cin>>n;
+	bool check = nQueen(board,0,n);	//function calling
+	if(check == false)
+	cout<<-1;
+	return 0;
+}