{"id":3427,"date":"2023-07-24T19:09:01","date_gmt":"2023-07-24T13:39:01","guid":{"rendered":"https:\/\/www.interviewbit.com\/blog\/?p=3427"},"modified":"2023-07-24T19:16:10","modified_gmt":"2023-07-24T13:46:10","slug":"n-queen-problem","status":"publish","type":"post","link":"https:\/\/www.interviewbit.com\/blog\/n-queen-problem\/","title":{"rendered":"N Queen Problem"},"content":{"rendered":"\n<div class=\"gutentoc tocactive ullist\"><div class=\"gutentoc-toc-wrap\"><div class=\"gutentoc-toc-title-wrap\"><div class=\"gutentoc-toc-title\">Table Of Contents<\/div><div id=\"open\" class=\"text_open\">show<\/div><\/div><div id=\"toclist\"><div class=\"gutentoc-toc__list-wrap\"><ul class=\"gutentoc-toc__list\"><li><a href=\"#problem-statement\">Problem Statement<\/a><\/li><li><a href=\"#method-1-using-backtracking\">Method 1 (Using Backtracking)<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-code-implementation\">C++ Code Implementation<\/a><\/li><li><a href=\"#java-code-implementation\">Java Code Implementation<\/a><\/li><li><a href=\"#python-code-implementation\">Python Code Implementation<\/a><\/li><\/ul><li><a href=\"#method-2-a-little-optimisation\">Method 2 (A little optimisation)<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-code-implementation\">C++ Code Implementation<\/a><\/li><li><a href=\"#java-code-implementation-\">Java Code Implementation <\/a><\/li><li><a href=\"#python-code-implementation\">Python Code Implementation<\/a><\/li><li><a href=\"#practice-question\">Practice Question<\/a><\/li><\/ul><li><a href=\"#faqs\">FAQs<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#q1-what-is-the-algorithm-used-by-the-n--queen-problem\">Q.1: What is the algorithm used by the N- Queen problem?<\/a><\/li><li><a href=\"#q2-what-is-the-time-complexity-of-the-n-queen-problem\">Q.2: What is the Time Complexity of the N-Queen Problem?<\/a><\/li><\/ul><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n<h2 id=\"problem-statement\">Problem Statement<\/h2>\n\n\n\n<p>Given an NxN Chessboard, we have to place N Queens such that they do not attack each other. (A queen can attack any square vertically, Horizontally, or diagonally).<\/p>\n\n\n\n<p><strong>Example of N Queen Problem :<\/strong><\/p>\n\n\n\n<p>Given, N = 8,<\/p>\n\n\n\n<p>One of the possible solution such that no queen attack any of the other queens,<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img  loading=\"lazy\"  width=\"665\"  height=\"675\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"Example of N Queen Problem\"  class=\"wp-image-3430 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 665px) 100vw, 665px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Example-of-N-Queen-Problem.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Example-of-N-Queen-Problem.png 665w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Example-of-N-Queen-Problem-296x300.png 296w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Example-of-N-Queen-Problem-80x80.png 80w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Example-of-N-Queen-Problem-380x386.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Example-of-N-Queen-Problem-550x558.png 550w\" ><\/figure>\n\n\n\n<h2 id=\"method-1-using-backtracking\">Method 1 (Using Backtracking)<\/h2>\n\n\n\n<p>As we know we cannot place any two queens in the same row thus every queen will be placed in different rows. Now, we can place i<sup>th<\/sup> queen to i<sup>th<\/sup> row if the square we are placing in is safe to place due to the previously placed queens; if there are no such squares left we can backtrack and return false.&nbsp;<\/p>\n\n\n\n<p>For every queen we are placing we have to check,&nbsp;<\/p>\n\n\n\n<ul><li>There should be no queen in the same column,<\/li><li>There should be no queen in the same row,<\/li><li>There should be no queen in the same diagonal (upper left and right diagonal).<\/li><\/ul>\n\n\n\n<p>Note that we can eliminate the row search as we are already moving row-wise to place the queens thus there will be no other queen in the same row thus we can eliminate that search.<\/p>\n\n\n\n<p><strong>Code for the above implementation :\u00a0<\/strong><\/p>\n\n\n\n<h3 id=\"c-code-implementation\"><span id=\"c-code-implementation-2\">C++ Code Implementation<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">\/* Function to print solution *\/\nvoid printBoard(vector&lt;vector&lt;int>> chess)\n{\n\tint N = chess.size();\n\tfor (int i = 0; i &lt; N; i++) {\n\t\tfor (int j = 0; j &lt; N;j++) {\n\t\t\tcout&lt;&lt;chess[i][j]&lt;&lt;\" \";\n\t\t}\n\t\tcout&lt;&lt;endl;\n\t}\n}\n\nbool isValid(vector&lt;vector&lt;int>> chess, int r, int c)\n{\n\tint N = chess.size();\n\n\t\/* Check this column only upward *\/\n\tfor (int i = 0; i &lt; r; i++)\n\t\tif (chess[i][c]==1)\n\t\t\treturn false;\n\n\t\/* Check upper diagonal on right side *\/\n\tfor (int i = r, j = c; j &lt; N &amp;&amp; i >= 0; i--, j++)\n\t\tif (chess[i][j]==1)\n\t\t\treturn false;\n\n\t\/* Check upper diagonal on left side *\/\n\tfor (int i = r, j = c; i >= 0 &amp;&amp; j >= 0; i--, j--)\n\t\tif (chess[i][j]==1)\n\t\t\treturn false;\n\n\treturn true;\n}\n\n\/* Recursive function for N-Queen Problem*\/\nbool recurNqueen(vector&lt;vector&lt;int>> chess, int r,int N)\n{\n\/* if no queens are left to place\n\twe return true. *\/\n\tif (r >= N)\n\t\treturn true;\n\n\tfor (int i = 0; i &lt; N; i++) {\n\t\t\/*Check if placing queen to chess[r][i] is valid.*\/\n\t\tif (isValid(chess, r, i)) {\n\t\t\t\/* Place this queen in chess[r][i] *\/\n\t\t\tchess[r][i] = 1;\n\n\t\t\t\/* move ahead for next row *\/\n\t\t\tif (recurNqueen(chess, r + 1,N))\n\t\t\t\treturn true;\n\n\t\t\t\/* Backtracking *\/\n\t\t\tchess[r][i] = 0; \n\t\t}\n\t}\n\n\t\/* If the queen cannot be placed in any column for\n\tthe given row we return false.*\/\n\treturn false;\n}\n\n        void NQueen(int N)\n{\n\t\/* creating chess board of NxN and initialising it with 0*\/\n\tvector&lt;vector&lt;int>> chess(N,vector&lt;int>(N,0));\n\t\n\t\/*initialising the recursive function from 0th row*\/\n\tif (recurNqueen(chess, 0, N) == 0) {\n\t\t\/* if no solution exists the recursive function will end up \n\t\treturning false.*\/\n\t\tcout&lt;&lt;\"Solution Do not exist for \"&lt;&lt;N&lt;&lt;\" Queens \";\n\t\treturn;\n\t}\n\t\/* else solution exists and printing out the solution*\/\n\tprintBoard(chess);\n\treturn;\n}\n<\/pre>\n\n\n\n<h3 id=\"java-code-implementation\">Java Code Implementation<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">static void printBoard(int chess[][],int N)\n{\n\tfor (int i = 0; i &lt; N; i++) {\n\t\tfor (int j = 0; j &lt; N; j++) {\n\t\t\tSystem.out.print(\" \" + chess[i][j] + \" \");\n        }\n        System.out.println();\n\t}\n}\n\nstatic boolean isValid(int chess[][], int r, int c,int N)\n{\n\t\/* Check this column only upward *\/\n\tfor (int i = 0; i &lt; r; i++)\n\t\tif (chess[i][c]==1)\n\t\t\treturn false;\n\n\t\/* Check upper diagonal on right side *\/\n\tfor (int i = r, j = c; j &lt; N &amp;&amp; i >= 0; i--, j++)\n\t\tif (chess[i][j]==1)\n\t\t\treturn false;\n\n\t\/* Check upper diagonal on left side *\/\n\tfor (int i = r, j = c; i >= 0 &amp;&amp; j >= 0; i--, j--)\n\t\tif (chess[i][j]==1)\n\t\t\treturn false;\n\n\treturn true;\n}\n\n\/* Recursive function for N-Queen Problem*\/\nstatic boolean recurNqueen(int chess[][], int r,int N)\n{\n\t\/* if no queens are left to place\n\twe return true. *\/\n\tif (r >= N)\n\t\treturn true;\n\n\tfor (int i = 0; i &lt; N; i++) {\n\t\t\/*Check if placing queen to chess[r][i] is valid.*\/\n\t\tif (isValid(chess, r, i, N)) {\n\t\t\t\/* Place this queen in chess[r][i] *\/\n\t\t\tchess[r][i] = 1;\n \n\t\t\t\/* move ahead for next row *\/\n\t\t\tif (recurNqueen(chess, r + 1, N))\n\t\t\t\treturn true;\n\n\t\t\t\/* Backtracking *\/\n\t\t\tchess[r][i] = 0; \n\t\t}\n\t}\n\n\t\/* If the queen cannot be placed in any column for\n\tthe given row we return false.*\/\n\treturn false;\n}\n\nstatic void NQueen(int N)\n{\n    \/* creating chess board of NxN and initialising it with 0*\/\n    int chess[][] = new int[N+1][N+1];\n    for(int i=0;i&lt;N+1;i++){\n        for(int j=0;j&lt;N+1;j++){\n            chess[i][j] = 0;\n        }\n    }\n\t\/*initialising the recursive function from 0th row*\/\n\tif (recurNqueen(chess, 0, N) == false) {\n\t\t\/* if no solution exists the recursive function will end up \n\t\treturning false.*\/\n        System.out.print(\"Solution Do not exist for \" + N + \" Queens. \");\n\t\treturn;\n\t}\n\t\/* else solution exists and printing out the solution*\/\n\tprintBoard(chess, N);\n\treturn;\n}\n<\/pre>\n\n\n\n<h3 id=\"python-code-implementation\"><span id=\"python-code-implementation-2\">Python Code Implementation<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\"># Function to print solution \ndef printBoard(chess,N) :\n    for i in range(N):\n        for j in range(N):\n            print(chess[i][j],end=' ')\n        print()\n\ndef isValid( chess, r, c, N) :\t\n\t# Check this column only upward \n\tfor i in range(r):\n\t\tif chess[i][c]==1:\n\t\t\treturn False\n\n\t# Check upper diagonal on right side\n\tfor i, j in zip(range(r, -1, -1),range(c, N, 1)):\n\t\tif chess[i][j]==1:\n\t\t\treturn False\n\n\t# Check upper diagonal on left side \n\tfor i, j in zip(range(r, -1, -1),range(c, -1, -1)):\n\t\tif chess[i][j]==1:\n\t\t\treturn False\n\n\treturn True\n\n# Recursive function for N-Queen Problem\ndef recurNqueen( chess, r, N):\n\t# if no queens are left to place\n\t# we return true. \n\tif r >= N:\n\t\treturn True\n\n\tfor i in range(N):\n\t\t# Check if placing queen to chess[r][i] is valid.\n\t\tif isValid(chess, r, i, N) == True: \n\t\t\t# Place this queen in chess[r][i] \n\t\t\tchess[r][i] = 1\n\n\t\t\t# move ahead for next row \n\t\t\tif recurNqueen(chess, r + 1, N):\n\t\t\t\treturn True\n\n\t\t\t# Backtracking \n\t\t\tchess[r][i] = 0 \n\n\t# If the queen cannot be placed in any column for\n\t# the given row we return false.\n\treturn False\n\ndef NQueen(N):\n\t# creating chess board of NxN and initialising it with 0\n    chess = [[0 for i in range(N+1)] for j in range(N+1)]\n    # initialising the recursive function from 0th row\n    if recurNqueen(chess, 0, N) == 0:\n\t\t# if no solution exists the recursive function will end up \n\t\t# returning false.\n        print(\"Solution not found !!\")\n        return\n\n    # else solution exists and printing out the solution*\/\n    printBoard(chess, N)\n\t<\/pre>\n\n\n\n<ul><li><strong>Time Complexity of the Above approach:<\/strong> O(N!).<\/li><\/ul>\n\n\n\n<h2 id=\"method-2-a-little-optimisation\">Method 2 (A little optimisation)<\/h2>\n\n\n\n<p>In the above approach, we can make some of the observations based on the image below.<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img  loading=\"lazy\"  width=\"943\"  height=\"716\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"right diagonal\"  class=\"wp-image-3431 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 943px) 100vw, 943px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/right-diagonal.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/right-diagonal.png 943w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/right-diagonal-300x228.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/right-diagonal-768x583.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/right-diagonal-380x289.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/right-diagonal-550x418.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/right-diagonal-800x607.png 800w\" ><\/figure>\n\n\n\n<p>From the above image, we can clearly observe that every right diagonal can be represented as a sum of coordinates of the cells through which the diagonal passes.<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img  loading=\"lazy\"  width=\"943\"  height=\"716\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"left diagonal\"  class=\"wp-image-3432 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 943px) 100vw, 943px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/left-diagonal.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/left-diagonal.png 943w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/left-diagonal-300x228.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/left-diagonal-768x583.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/left-diagonal-380x289.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/left-diagonal-550x418.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/left-diagonal-800x607.png 800w\" ><\/figure>\n\n\n\n<p>From the above image, we can observe that every left diagonal can be represented by the difference in the coordinates of the cells lying on the diagonal.\u00a0<\/p>\n\n\n\n<p>Thus using the same we can reduce our time by excluding the step for searching the whole diagonal using a loop instead we can create an array for the left, and right diagonals and columns to store if there exists a queen in them.\u00a0<\/p>\n\n\n\n<p><strong>Code for the above optimization :<\/strong><\/p>\n\n\n\n<h3 id=\"c-code-implementation\">C++ Code Implementation<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">\/*global vectors to store previously placed queens*\/\nvector&lt;vector&lt;int>> prevd;\nvector&lt;int> prevc;\n\n\/* Function to print solution *\/\nvoid printBoard(vector&lt;vector&lt;int>> chess)\n{\n\tint N = chess.size();\n\tfor (int i = 0; i &lt; N; i++) {\n\t\tfor (int j = 0; j &lt; N;j++) {\n\t\t\tcout&lt;&lt;chess[i][j]&lt;&lt;\" \";\n\t\t}\n\t\tcout&lt;&lt;endl;\n\t}\n}\n\nbool isValid(vector&lt;vector&lt;int>> chess, int r, int c)\n{\n\tint N = chess.size();\n\n\t\/* Check this column only upward *\/\n\tif(prevc[c] == 1) return false;\n\n\t\/* Check upper diagonal on right side *\/\n\tif(prevd[r+c][0] == 1) return false;\n\n\t\/* Check upper diagonal on left side *\/\n\tif(prevd[r-c+N-1][1] == 1) return false;\n\n\treturn true;\n}\n\n\/* Recursive function for N-Queen Problem*\/\nbool recurNqueen(vector&lt;vector&lt;int>> chess, int r,int N)\n{\n\t\/* if no queens are left to place\n\twe return true. *\/\n\tif (r >= N)\n\t\treturn true;\n\n\tfor (int i = 0; i &lt; N; i++) {\n\t\t\/*Check if placing queen to chess[r][i] is valid.*\/\n\t\tif (isValid(chess, r, i)) {\n\t\t\t\/* Place this queen in chess[r][i] and mark \n                  the respective column , right and left diagonal. *\/\n\t\t\tchess[r][i] = 1;\n\t\t\tprevc[i] = 1;\n\t\t\tprevd[r+i][0] = 1;\n\t\t\tprevd[r-i+N-1][1] = 1;\n\t\t\t\n\t\t\t\/* move ahead for next row *\/\n\t\t\tif (recurNqueen(chess, r + 1,N))\n\t\t\t\treturn true;\n\n\t\t\t\/* Backtracking *\/\n\t\tchess[r][i] = 0;\n\t\t\tprevc[i] = 0;\n\t\t\tprevd[r+i][0] = 0;\n\t\t\tprevd[r-i+N-1][1] = 0;\n\t\t}\n\t}\n\n\t\/* If the queen cannot be placed in any column for\n\tthe given row we return false.*\/\n\treturn false;\n}\n\nvoid NQueen(int N)\n{\n\t\/* creating chess board of NxN and initialising it with 0*\/\n\tvector&lt;vector&lt;int>> chess(N,vector&lt;int>(N,0));\n\t\n\t\/*creating and initializing global vector to store answers \n\tfor prev diagonals and columns.*\/\n\tprevd.resize(2*N,vector&lt;int> (2,0));\n\tprevc.resize(N,0);\n\n\t\/*initialising the recursive function from 0th row*\/\n\tif (recurNqueen(chess, 0, N) == 0) {\n\t\t\/* if no solution exists the recursive function will end up \n\t\treturning false.*\/\n\t\tcout&lt;&lt;\"Solution Do not exist for \"&lt;&lt;N&lt;&lt;\" Queens \";\n\t\treturn;\n\t}\n\t\/* else solution exists and printing out the solution*\/\n\tprintBoard(chess);\n\treturn;\n}\n<\/pre>\n\n\n\n<h3 id=\"java-code-implementation-\"><span id=\"java-code-implementation-2\">Java Code Implementation <\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">\/*global arrays to store previously placed queens*\/\nstatic int prevd[][];\nstatic int prevc[];\n\n\/* Function to print solution *\/\nstatic void printBoard(int chess[][],int N)\n{\n\tfor (int i = 0; i &lt; N; i++) {\n\t\tfor (int j = 0; j &lt; N; j++) {\n\t\t\tSystem.out.print(\" \" + chess[i][j] + \" \");\n        }\n        System.out.println();\n\t}\n}\n\nstatic boolean isValid(int chess[][], int r, int c,int N)\n{\t\n\t\/* Check this column only upward *\/\n\tif(prevc[c] == 1) return false;\n\n\t\/* Check upper diagonal on right side *\/\n\tif(prevd[r+c][0] == 1) return false;\n\n\t\/* Check upper diagonal on left side *\/\n\tif(prevd[r-c+N-1][1] == 1) return false;\n\n\treturn true;\n\n}\n\n\/* Recursive function for N-Queen Problem*\/\nstatic boolean recurNqueen(int chess[][], int r,int N)\n{\n\t\/* if no queens are left to place\n\twe return true. *\/\n\tif (r >= N)\n\t\treturn true;\n\n\tfor (int i = 0; i &lt; N; i++) {\n\t\t\/*Check if placing queen to chess[r][i] is valid.*\/\n\t\tif (isValid(chess, r, i, N)) {\n\t\t\t\/* Place this queen in chess[r][i] *\/\n\t\t\tchess[r][i] = 1;\n\t\t\tprevc[i] = 1;\n\t\t\tprevd[r+i][0] = 1;\n\t\t\tprevd[r-i+N-1][1] = 1;\n\t\t\t\n\t\t\t\/* move ahead for next row *\/\n\t\t\tif (recurNqueen(chess, r + 1, N))\n\t\t\t\treturn true;\n\n\t\t\/* Backtracking *\/\n\t\t\tchess[r][i] = 0;\n\t\t\tprevc[i] = 0;\n\t\t\tprevd[r+i][0] = 0;\n\t\t\tprevd[r-i+N-1][1] = 0;\n\t\t\t \n\t\t}\n\t}\n\n\t\/* If the queen cannot be placed in any column for\n\tthe given row we return false.*\/\n\treturn false;\n}\n\nstatic void NQueen(int N)\n{\n\t\/* creating chess board of NxN and initialising it with 0*\/\n\tint chess[][] = new int[N+1][N+1];\n    for(int i=0;i&lt;N+1;i++){\n        for(int j=0;j&lt;N+1;j++){\n            chess[i][j] = 0;\n        }\n    }\n\n\tprevd = new int[2*N][2];\n\tfor(int i=0;i&lt;2*N;i++){\n\t\tprevd[i][0] = 0;\n\t\tprevd[i][0] = 1;\n\t}\n\n\tprevc = new int[N];\n\tfor(int i=0;i&lt;N+1;i++){\n\t\tprevc[i] = 0;\n\t}\n\t\/*initialising the recursive function from 0th row*\/\n\tif (recurNqueen(chess, 0, N) == 0) {\n\t\t\/* if no solution exists the recursive function will end up \n\t\treturning false.*\/\n        System.out.print(\"Solution Do not exist for \" + N + \" Queens. \");\n\t\treturn;\n\t}\n\t\/* else solution exists and printing out the solution*\/\n\tprintBoard(chess, N);\n\treturn;\n}\n<\/pre>\n\n\n\n<h3 id=\"python-code-implementation\">Python Code Implementation<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">prevd = []\nprevc = []\n\n# Function to print solution \ndef printBoard(chess,N) :\n    for i in range(N):\n        for j in range(N):\n            print(chess[i][j],end=' ')\n        print()\n\ndef isValid( chess, r, c, N) :\t\n\t# Check this column only upward \n\tif prevc[c] == 1: \n\t\treturn False\n\n\t# Check upper diagonal on right side \n\tif prevd[r+c][0] == 1: \n\t\treturn False\n\n\t# Check upper diagonal on left side \n\tif prevd[r-c+N-1][1] == 1: \n\t\treturn False\n\n\treturn True\n\n# Recursive function for N-Queen Problem\ndef recurNqueen( chess, r, N):\n\t# if no queens are left to place\n\t# we return true. \n\tif r >= N:\n\t\treturn True\n\n\tfor i in range(N):\n\t\t# Check if placing queen to chess[r][i] is valid.\n\t\tif isValid(chess, r, i, N) == True: \n\t\t\t# Place this queen in chess[r][i] \n\t\t\tchess[r][i] = 1\n\t\t\tprevc[i] = 1\t\n\t\t\tprevd[r+i][0] = 1 \nprevd[r-i+N-1][1] = 1 \n\n\t\t\t# move ahead for next row \n\t\t\tif recurNqueen(chess, r + 1, N):\n\t\t\t\treturn True\n\n\t\t\t# Backtracking \n\t\t\tchess[r][i] = 0 \n\t\t\tprevc[i] = 0\t\n\t\t\tprevd[r+i][0] = 0 \n\t\t\tprevd[r-i+N-1][1] = 0 \n\n\n\t# If the queen cannot be placed in any column for\n\t# the given row we return false.\n\treturn False\n\ndef NQueen():\n    N = 8\n\t# creating chess board of NxN and initialising it with 0\n    chess = [[0 for i in range(N+1)] for j in range(N+1)]\n    prevd = [[0 for i in range(2*N)] for j in range(2)]\n\tprevc = [0 for i in range(N+1)]\n\n\t# initialising the recursive function from 0th row\n    if recurNqueen(chess, 0, N) == 0:\n\t\t# if no solution exists the recursive function will end up \n\t\t# returning false.\n        print(\"Solution not found !!\")\n        return\n\n    # else solution exists and printing out the solution*\/\n    printBoard(chess, N)\n\t<\/pre>\n\n\n\n<h3 id=\"practice-question\">Practice Question<\/h3>\n\n\n\n<ul><li><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/problems\/nqueens\/\" target=\"_blank\">NQueens<\/a><\/li><\/ul>\n\n\n\n<h2 id=\"faqs\">FAQs<\/h2>\n\n\n\n<h3 id=\"q1-what-is-the-algorithm-used-by-the-n--queen-problem\"><span id=\"q-1-what-is-the-algorithm-used-by-the-n-queen-problem\">Q.1: What is the algorithm used by the N- Queen problem?<\/span><\/h3>\n\n\n\n<p><strong>Ans:<\/strong> To solve the N- Queen problem we use backtracking to reach the solution, however, we can add some optimisations one such solution is as discussed above.<\/p>\n\n\n\n<h3 id=\"q2-what-is-the-time-complexity-of-the-n-queen-problem\"><span id=\"q-2-what-is-the-time-complexity-of-the-n-queen-problem\">Q.2: What is the Time Complexity of the N-Queen Problem?<\/span><\/h3>\n\n\n\n<p><strong>Ans: <\/strong>The time complexity for the N-Queen problem solved using Backtracking is O(N!) where N denotes the number of Queens and dimensions of the chess board.<\/p>\n","protected":false},"excerpt":{"rendered":"Problem Statement Given an NxN Chessboard, we have to place N Queens such that they do not attack&hellip;\n","protected":false},"author":4,"featured_media":3429,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_daextam_enable_autolinks":"1","csco_singular_sidebar":"","csco_page_header_type":"","csco_appearance_grid":"","csco_page_load_nextpost":"","csco_post_video_location":[],"csco_post_video_location_hash":"","csco_post_video_url":"","csco_post_video_bg_start_time":0,"csco_post_video_bg_end_time":0},"categories":[145],"tags":[538],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3427"}],"collection":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/users\/4"}],"replies":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/comments?post=3427"}],"version-history":[{"count":4,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3427\/revisions"}],"predecessor-version":[{"id":21888,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3427\/revisions\/21888"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/3429"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=3427"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=3427"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=3427"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}