{"id":2901,"date":"2023-08-17T19:22:13","date_gmt":"2023-08-17T13:52:13","guid":{"rendered":"https:\/\/www.interviewbit.com\/blog\/?p=2901"},"modified":"2023-08-17T19:22:15","modified_gmt":"2023-08-17T13:52:15","slug":"8-queens-problem","status":"publish","type":"post","link":"https:\/\/www.interviewbit.com\/blog\/8-queens-problem\/","title":{"rendered":"8 Queens Problem"},"content":{"rendered":"\n<div class=\"gutentoc tocactive nostyle\"><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=\"#approach-bruteforce\">Approach: Bruteforce<\/a><\/li><li><a href=\"#efficient-approach-backtracking\">Efficient Approach: Backtracking<\/a><\/li><li><a href=\"#implementation-of-the-approach\">Implementation of the Approach<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-implementation\">C++ Implementation<\/a><\/li><li><a href=\"#java--implementation\">Java <meta charset=\"utf-8\">Implementation<\/a><\/li><li><a href=\"#python--implementation\">Python <meta charset=\"utf-8\">Implementation<\/a><\/li><\/ul><li><a href=\"#practice-questions\">Practice Questions<\/a><\/li><li><a href=\"#faq\">FAQ<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#q1-what-is-the-most-efficient-approach-to-solving-the\u00a0-n-queens-problem\">Q.1: What is the most efficient approach to solving the\u00a0 N queens problem?<\/a><\/li><li><a href=\"#q2-how-does-the-backtrack-function-work\">Q.2: How does the backtrack function work?<\/a><\/li><\/ul><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n<p>Given a <strong>8 X 8<\/strong> chessboard. The task is to place <strong>8<\/strong> queens on the board, such that no two queens attack each other. Return all distinct possible solutions for the <strong>8 queens problem.<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img  loading=\"lazy\"  width=\"680\"  height=\"668\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"8 queens\"  class=\"wp-image-3204 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 680px) 100vw, 680px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/8-Queens.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/8-Queens.png 680w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/8-Queens-300x295.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/8-Queens-80x80.png 80w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/8-Queens-380x373.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/8-Queens-550x540.png 550w\" ><\/figure>\n\n\n\n<h2 id=\"approach-bruteforce\">Approach: Bruteforce<\/h2>\n\n\n\n<p>A simple brute-force solution would be to generate all possible chess boards with 8 queens. Accordingly, there would be N^2 positions to place the first queen, N^2 &#8211; 1 position to place the second queen and so on.<\/p>\n\n\n\n<p>The total time complexity, in this case, would be O(N^(2N)), which is too high.<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img  loading=\"lazy\"  width=\"680\"  height=\"716\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"bruteforce solution\"  class=\"wp-image-3205 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 680px) 100vw, 680px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/bruteforce-solution.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/bruteforce-solution.png 680w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/bruteforce-solution-285x300.png 285w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/bruteforce-solution-380x400.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/bruteforce-solution-550x579.png 550w\" ><\/figure>\n\n\n\n<p>In the above image, suppose we place the first two queens adjacently. The other 6 queens can have 62! = 62 * 61 * 60 *&#8230;.. = 44,261,653,680 ways to place in the board, but these all are invalid since the first two queens would attack each other. This leads to unnecessary calculations, therefore we need to optimise the above approach.<\/p>\n\n\n\n<h2 id=\"efficient-approach-backtracking\">Efficient Approach: Backtracking<\/h2>\n\n\n\n<p>The idea is to apply a backtracking approach to solve the problem. The backtracking function does the following:<\/p>\n\n\n\n<ul><li>Places only 1 queen per row satisfying the conditions.<\/li><li>Places only 1 queen per column satisfying the conditions.<\/li><\/ul>\n\n\n\n<p>For the diagonals, the value of (<strong>row &#8211; col<\/strong>) is constant and the main diagonal is <strong>0<\/strong>.<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img  loading=\"lazy\"  width=\"680\"  height=\"716\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"diagonals\"  class=\"wp-image-3206 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 680px) 100vw, 680px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/diagonals.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/diagonals.png 680w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/diagonals-285x300.png 285w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/diagonals-380x400.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/diagonals-550x579.png 550w\" ><\/figure>\n\n\n\n<p>Similarly, for <strong>anti-diagonal<\/strong>, the value of (<strong>row + col) <\/strong>is constant.<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img  loading=\"lazy\"  width=\"680\"  height=\"716\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"anti-diagonal\"  class=\"wp-image-3207 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 680px) 100vw, 680px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/anti-diagonal.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/anti-diagonal.png 680w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/anti-diagonal-285x300.png 285w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/anti-diagonal-380x400.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/anti-diagonal-550x579.png 550w\" ><\/figure>\n\n\n\n<p>From, the above, we can keep track of the rows and columns which have been used already. Therefore, no more queens can be placed in such rows\/columns.<\/p>\n\n\n\n<p><strong>Algorithm:<\/strong><\/p>\n\n\n\n<ul><li>Create a function <strong>backtrack<\/strong> that simply places the queens on corresponding rows and columns and marks them visited.<\/li><li>The working of <strong>backtrack<\/strong> is as follows:<ul><li>If the current row is equal to <strong>8<\/strong>, then a solution has been found. Therefore, add this to the answer.<\/li><li>Traverse through the columns of the current row. At each column, try to place the queen in (<strong>row, col)<\/strong>:<ul><li>Calculate the <strong>diagonal<\/strong> and <strong>anti-diagonal<\/strong> which the current square belongs to. If it is unvisited, place the queen in the (<strong>row, col).<\/strong><\/li><li>Skip this column, if the queen cannot be visited.<\/li><\/ul><\/li><li>If the queen has been placed successfully, call the <strong>backtrack<\/strong> function of <strong>row + 1<\/strong>.<\/li><li>Since, all paths have now been explored, clear the values of the queens placed so far and the visiting arrays, so that next distinct solution can be found.&nbsp;<\/li><\/ul><\/li><\/ul>\n\n\n\n<h2 id=\"implementation-of-the-approach\">Implementation of the Approach<\/h2>\n\n\n\n<h3 id=\"c-implementation\">C++ 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=\"\"> std::vector&lt;std::vector&lt;std::string> > solveNQueens(int n) {\n        std::vector&lt;std::vector&lt;std::string> > res;\n        std::vector&lt;std::string> nQueens(n, std::string(n, '.'));\n        solveNQueens(res, nQueens, 0, n);\n        return res;\n    }\nprivate:\n    void solveNQueens(std::vector&lt;std::vector&lt;std::string> > &amp;res, std::vector&lt;std::string> &amp;nQueens, int row, int &amp;n) {\n        if (row == n) {\n            res.push_back(nQueens);\n            return;\n        }\n        for (int col = 0; col != n; ++col)\n            if (isValid(nQueens, row, col, n)) {\n                nQueens\t\t\t<div class=\"pk-row\">\n\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<div class=\"pk-col-md-1\">\n\t\t\t\t\t\t\t<\/div>\n\t\t = 'Q';\n                solveNQueens(res, nQueens, row + 1, n);\n                nQueens\t\t\t<div class=\"pk-row\">\n\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<div class=\"pk-col-md-1\">\n\t\t\t\t\t\t\t<\/div>\n\t\t = '.';\n            }\n    }\n    bool isValid(std::vector&lt;std::string> &amp;nQueens, int row, int col, int &amp;n) {\n        for (int i = 0; i != row; ++i)\n            if (nQueens[i]\t\t\t<div class=\"pk-col-md-1\">\n\t\t\t\t\t\t\t<\/div>\n\t\t == 'Q')\n                return false;\n \n        for (int i = row - 1, j = col - 1; i >= 0 &amp;&amp; j >= 0; --i, --j)\n            if (nQueens[i][j] == 'Q')\n                return false;\n \n        for (int i = row - 1, j = col + 1; i >= 0 &amp;&amp; j &lt; n; --i, ++j)\n            if (nQueens[i][j] == 'Q')\n                return false;\n        return true;\n    }\n\n<\/pre>\n\n\n\n<h3 id=\"java--implementation\"><span id=\"java-implementation\">Java <meta charset=\"utf-8\">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=\"\">private int size;\n    private List&lt;List&lt;String>> solutions = new ArrayList&lt;List&lt;String>>();\n    \n    public List&lt;List&lt;String>> solveNQueens(int n) {\n        size = n;\n        char emptyBoard[][] = new char[size][size];\n        for (int i = 0; i &lt; n; i++) {\n            for (int j = 0; j &lt; n; j++) {\n                emptyBoard[i][j] = '.';\n            }\n        }\n \n        backtrack(0, new HashSet&lt;>(), new HashSet&lt;>(), new HashSet&lt;>(), emptyBoard);\n        return solutions;\n    }\n    \n    private List&lt;String> createBoard(char[][] state) {\n        List&lt;String> board = new ArrayList&lt;String>();\n        for (int row = 0; row &lt; size; row++) {\n            String current_row = new String(state\t\t\t<div class=\"pk-row\">\n\t\t\t\t\t\t\t<\/div>\n\t\t);\n            board.add(current_row);\n        }\n        \n        return board;\n    }\n    \n    private void backtrack(int row, Set&lt;Integer> diagonals, Set&lt;Integer> antiDiagonals, Set&lt;Integer> cols, char[][] state) {\n        if (row == size) {\n            solutions.add(createBoard(state));\n            return;\n        }\n        \n        for (int col = 0; col &lt; size; col++) {\n            int currDiagonal = row - col;\n            int currAntiDiagonal = row + col;\n            if (cols.contains(col) || diagonals.contains(currDiagonal) || antiDiagonals.contains(currAntiDiagonal)) {\n                continue;    \n            }\n            \n            cols.add(col);\n            diagonals.add(currDiagonal);\n            antiDiagonals.add(currAntiDiagonal);\n            state\t\t\t<div class=\"pk-row\">\n\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<div class=\"pk-col-md-1\">\n\t\t\t\t\t\t\t<\/div>\n\t\t = 'Q';\n \n            backtrack(row + 1, diagonals, antiDiagonals, cols, state);\n \n            cols.remove(col);\n            diagonals.remove(currDiagonal);\n            antiDiagonals.remove(currAntiDiagonal);\n            state\t\t\t<div class=\"pk-row\">\n\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<div class=\"pk-col-md-1\">\n\t\t\t\t\t\t\t<\/div>\n\t\t = '.';\n        }\n    }\n\n<\/pre>\n\n\n\n<h3 id=\"python--implementation\"><span id=\"python-implementation\">Python <meta charset=\"utf-8\">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=\"\">def solveNQueens(self, n):\n        \n        def create_board(state):\n            board = []\n            for row in state:\n                board.append(\"\".join(row))\n            return board\n        \n        def backtrack(row, diagonals, anti_diagonals, cols, state):\n            \n            if row == n:\n                ans.append(create_board(state))\n                return\n \n            for col in range(n):\n                curr_diagonal = row - col\n                curr_anti_diagonal = row + col\n                \n                if (col in cols \n                      or curr_diagonal in diagonals \n                      or curr_anti_diagonal in anti_diagonals):\n                    continue\n \n                \n                cols.add(col)\n                diagonals.add(curr_diagonal)\n                anti_diagonals.add(curr_anti_diagonal)\n                state\t\t\t<div class=\"pk-row\">\n\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<div class=\"pk-col-md-1\">\n\t\t\t\t\t\t\t<\/div>\n\t\t = \"Q\"\n \n                \n                backtrack(row + 1, diagonals, anti_diagonals, cols, state)\n \n               \n                cols.remove(col)\n                diagonals.remove(curr_diagonal)\n                anti_diagonals.remove(curr_anti_diagonal)\n\n                state\t\t\t<div class=\"pk-row\">\n\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<div class=\"pk-col-md-1\">\n\t\t\t\t\t\t\t<\/div>\n\t\t = \".\"\n \n        ans = []\n        empty_board = [[\".\"] * n for _ in range(n)]\n        backtrack(0, set(), set(), set(), empty_board)\n        return ans\n \n<\/pre>\n\n\n\n<ul><li><strong>Time Complexity: <\/strong>O(N!), where N is the size of the board.<\/li><li><strong>Space Complexity:<\/strong> O(N^2), since <strong>visiting array<\/strong> is used.<\/li><\/ul>\n\n\n\n<h2 id=\"practice-questions\">Practice Questions<\/h2>\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=\"faq\">FAQ<\/h2>\n\n\n\n<h3 id=\"q1-what-is-the-most-efficient-approach-to-solving-the\u00a0-n-queens-problem\"><span id=\"q-1-what-is-the-most-efficient-approach-to-solving-the-n-queens-problem\">Q.1: What is the most efficient approach to solving the\u00a0 N queens problem?<\/span><\/h3>\n\n\n\n<p><strong>Ans:<\/strong> The backtracking approach is the most efficient approach since it takes O(N!) time.<\/p>\n\n\n\n<h3 id=\"q2-how-does-the-backtrack-function-work\"><span id=\"q-2-how-does-the-backtrack-function-work\">Q.2: How does the backtrack function work?<\/span><\/h3>\n\n\n\n<p><strong>Ans: <\/strong>The backtrack function explores all paths possible by placing the queens on the rows and the columns.\u00a0 It keeps a visiting set to keep track of the rows and columns which have been already used.<\/p>\n","protected":false},"excerpt":{"rendered":"Given a 8 X 8 chessboard. The task is to place 8 queens on the board, such that&hellip;\n","protected":false},"author":4,"featured_media":3203,"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":[476],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2901"}],"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=2901"}],"version-history":[{"count":4,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2901\/revisions"}],"predecessor-version":[{"id":22956,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2901\/revisions\/22956"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/3203"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=2901"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=2901"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=2901"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}