{"id":767,"date":"2025-07-22T14:58:26","date_gmt":"2025-07-22T09:28:26","guid":{"rendered":"https:\/\/codeanddebug.in\/blog\/?p=767"},"modified":"2025-07-24T15:28:42","modified_gmt":"2025-07-24T09:58:42","slug":"n-queens","status":"publish","type":"post","link":"https:\/\/codeanddebug.in\/blog\/n-queens\/","title":{"rendered":"N-Queens | Leetcode 51 | Brute and Optimal Solution"},"content":{"rendered":"\n<p>The&nbsp;<strong>n-queens<\/strong>&nbsp;puzzle is the problem of placing&nbsp;<code>n<\/code>&nbsp;queens on an&nbsp;<code>n x n<\/code>&nbsp;chessboard such that no two queens attack each other.<\/p>\n\n\n\n<p>Given an integer&nbsp;<code>n<\/code>, return&nbsp;<em>all distinct solutions to the&nbsp;<strong>n-queens puzzle<\/strong><\/em>. You may return the answer in&nbsp;<strong>any order<\/strong>.<\/p>\n\n\n\n<p>Each solution contains a distinct board configuration of the n-queens&#8217; placement, where&nbsp;<code>'Q'<\/code>&nbsp;and&nbsp;<code>'.'<\/code>&nbsp;both indicate a queen and an empty space, respectively.<\/p>\n\n\n\n<p>Here&#8217;s the [<strong><a href=\"https:\/\/leetcode.com\/problems\/n-queens\/description\/\" target=\"_blank\" rel=\"noreferrer noopener\"><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-vivid-purple-color\"><span style=\"text-decoration: underline;\">Problem Link<\/span><\/mark><\/a><\/strong>] to begin with.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2020\/11\/13\/queens.jpg\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted\"><strong>Input:<\/strong> n = 4<br><strong>Output:<\/strong> [[\".Q..\",\"...Q\",\"Q...\",\"..Q.\"],[\"..Q.\",\"Q...\",\"...Q\",\".Q..\"]]<br><strong>Explanation:<\/strong> There exist two distinct solutions to the 4-queens puzzle as shown above<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted\"><strong>Input:<\/strong> n = 1<br><strong>Output:<\/strong> [[\"Q\"]]<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><code>1 &lt;= n &lt;= 9<\/code><\/li>\n<\/ul>\n\n\n<div style=\"max-width: -moz-fit-content; \" class=\"wp-block-ub-table-of-contents-block ub_table-of-contents ub_table-of-contents-collapsed\" id=\"ub_table-of-contents-1acc886b-ada9-414f-bb51-74fc20c5285d\" data-linktodivider=\"false\" data-showtext=\"show\" data-hidetext=\"hide\" data-scrolltype=\"auto\" data-enablesmoothscroll=\"true\" data-initiallyhideonmobile=\"true\" data-initiallyshow=\"false\"><div class=\"ub_table-of-contents-header-container\" style=\"\">\n\t\t\t<div class=\"ub_table-of-contents-header\" style=\"text-align: left; \">\n\t\t\t\t<div class=\"ub_table-of-contents-title\">Contents:<\/div>\n\t\t\t\t<div class=\"ub_table-of-contents-header-toggle\">\n\t\t\t<div class=\"ub_table-of-contents-toggle\" style=\"\">\n\t\t\t\u00a0[<a class=\"ub_table-of-contents-toggle-link\" href=\"#\" style=\"\">show<\/a>]\n\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t<\/div>\n\t\t<\/div><div class=\"ub_table-of-contents-extra-container\" style=\"\">\n\t\t\t<div class=\"ub_table-of-contents-container ub_table-of-contents-1-column ub-hide\">\n\t\t\t\t<ul style=\"\"><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/n-queens\/#0-solution-1-brute-force-approach-check-all-conflicts-for-each-placement\" style=\"\">Solution 1: Brute Force Approach (Check All Conflicts For Each Placement)<\/a><ul><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/n-queens\/#1-intuition\" style=\"\">Intuition<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/n-queens\/#2-detailed-approach\" style=\"\">Detailed Approach<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/n-queens\/#3-code\" style=\"\">Code<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/n-queens\/#4-code-explanation\" style=\"\">Code Explanation<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/n-queens\/#5-dry-run\" style=\"\">Dry Run<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/n-queens\/#6-time-and-space-complexity\" style=\"\">Time and Space Complexity<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/n-queens\/#7-simplifying-it\" style=\"\">Simplifying It<\/a><\/li><\/ul><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/n-queens\/#8-solution-2-optimal-approach-hash-sets-for-o1-conflict-detection\" style=\"\">Solution 2: Optimal Approach (Hash Sets for O(1) Conflict Detection)<\/a><ul><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/n-queens\/#9-intuition\" style=\"\">Intuition<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/n-queens\/#10-detailed-approach\" style=\"\">Detailed Approach<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/n-queens\/#11-code\" style=\"\">Code<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/n-queens\/#12-code-explanation\" style=\"\">Code Explanation<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/n-queens\/#13-dry-run\" style=\"\">Dry Run<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/n-queens\/#14-time-and-space-complexity\" style=\"\">Time and Space Complexity<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/n-queens\/#15-simplifying-it\" style=\"\">Simplifying It<\/a><\/li><\/ul><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/n-queens\/#16-summary\" style=\"\">Summary<\/a><\/li><\/ul>\n\t\t\t<\/div>\n\t\t<\/div><\/div>\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"0-solution-1-brute-force-approach-check-all-conflicts-for-each-placement\">Solution 1: Brute Force Approach (Check All Conflicts For Each Placement)<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"1-intuition\">Intuition<\/h3>\n\n\n\n<p>Think of this like placing queens one by one on a chessboard, and every time you want to place a new queen, you look at the entire board to make sure it won&#8217;t be attacked by any existing queen! The brute force approach places queens column by column (to ensure no two queens are in the same column), and for each potential position, it checks all three attack directions: same row, upper-left diagonal, and lower-left diagonal. It&#8217;s like being a very careful chess player who double-checks every existing piece on the board before making a move.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"2-detailed-approach\">Detailed Approach<\/h3>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Column-by-Column Placement<\/strong>: Place queens one column at a time to ensure no column conflicts.<\/li>\n\n\n\n<li><strong>Safety Check Function<\/strong>: For each potential position (row, col), check if it&#8217;s safe by scanning:\n<ul class=\"wp-block-list\">\n<li><strong>Left Row<\/strong>: Check if any queen exists in the same row to the left<\/li>\n\n\n\n<li><strong>Upper-Left Diagonal<\/strong>: Check upper-left diagonal for existing queens<\/li>\n\n\n\n<li><strong>Lower-Left Diagonal<\/strong>: Check lower-left diagonal for existing queens<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>Backtracking<\/strong>: If a position is safe, place the queen and recurse to next column. If not safe or no solution found, backtrack by removing the queen.<\/li>\n\n\n\n<li><strong>Base Case<\/strong>: When all N columns are filled, we found a valid solution.<\/li>\n\n\n\n<li><strong>String Manipulation<\/strong>: Build the board using string slicing for each placement\/removal.<\/li>\n<\/ol>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"3-code\">Code<\/h3>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro cbp-has-line-numbers\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;--cbp-line-number-color:#D4D4D4;--cbp-line-number-width:calc(2 * 0.6 * .875rem);line-height:1.5rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"class Solution:\n    def isSafe1(self, row, col, board, n):\n        duprow = row\n        dupcol = col\n\n        # Check upper-left diagonal\n        while row &gt;= 0 and col &gt;= 0:\n            if board[row][col] == &quot;Q&quot;:\n                return False\n            row -= 1\n            col -= 1\n\n        # Reset and check left row\n        col = dupcol\n        row = duprow\n        while col &gt;= 0:\n            if board[row][col] == &quot;Q&quot;:\n                return False\n            col -= 1\n\n        # Reset and check lower-left diagonal\n        row = duprow\n        col = dupcol\n        while row &lt; n and col &gt;= 0:\n            if board[row][col] == &quot;Q&quot;:\n                return False\n            row += 1\n            col -= 1\n        \n        return True\n\n    def solve(self, col, board, ans, n):\n        # Base case: placed queens in all columns\n        if col == n:\n            ans.append(list(board))  # Make a copy of current board state\n            return\n\n        # Try placing queen in each row of current column\n        for row in range(n):\n            if self.isSafe1(row, col, board, n):\n                # Place queen: replace '.' with 'Q' at position (row, col)\n                board[row] = board[row][:col] + &quot;Q&quot; + board[row][col + 1 :]\n                \n                # Recursively solve for next column\n                self.solve(col + 1, board, ans, n)\n                \n                # Backtrack: remove queen by replacing 'Q' with '.'\n                board[row] = board[row][:col] + &quot;.&quot; + board[row][col + 1 :]\n\n    def solveNQueens(self, n: int) -&gt; List[List[str]]:\n        ans = []\n        board = [&quot;.&quot; * n for _ in range(n)]  # Initialize n\u00d7n board with dots\n        self.solve(0, board, ans, n)  # Start from column 0\n        return ans\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #569CD6\">class<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #4EC9B0\">Solution<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">isSafe1<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">row<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">col<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">board<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">n<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        duprow = row<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        dupcol = col<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Check upper-left diagonal<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">while<\/span><span style=\"color: #D4D4D4\"> row &gt;= <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">and<\/span><span style=\"color: #D4D4D4\"> col &gt;= <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> board[row][col] == <\/span><span style=\"color: #CE9178\">&quot;Q&quot;<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">False<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            row -= <\/span><span style=\"color: #B5CEA8\">1<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            col -= <\/span><span style=\"color: #B5CEA8\">1<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Reset and check left row<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        col = dupcol<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        row = duprow<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">while<\/span><span style=\"color: #D4D4D4\"> col &gt;= <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> board[row][col] == <\/span><span style=\"color: #CE9178\">&quot;Q&quot;<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">False<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            col -= <\/span><span style=\"color: #B5CEA8\">1<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Reset and check lower-left diagonal<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        row = duprow<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        col = dupcol<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">while<\/span><span style=\"color: #D4D4D4\"> row &lt; n <\/span><span style=\"color: #569CD6\">and<\/span><span style=\"color: #D4D4D4\"> col &gt;= <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> board[row][col] == <\/span><span style=\"color: #CE9178\">&quot;Q&quot;<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">False<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            row += <\/span><span style=\"color: #B5CEA8\">1<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            col -= <\/span><span style=\"color: #B5CEA8\">1<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">True<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">solve<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">col<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">board<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">ans<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">n<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Base case: placed queens in all columns<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> col == n:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            ans.append(<\/span><span style=\"color: #4EC9B0\">list<\/span><span style=\"color: #D4D4D4\">(board))  <\/span><span style=\"color: #6A9955\"># Make a copy of current board state<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">return<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Try placing queen in each row of current column<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> row <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(n):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.isSafe1(row, col, board, n):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #6A9955\"># Place queen: replace &#39;.&#39; with &#39;Q&#39; at position (row, col)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                board[row] = board[row][:col] + <\/span><span style=\"color: #CE9178\">&quot;Q&quot;<\/span><span style=\"color: #D4D4D4\"> + board[row][col + <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\"> :]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #6A9955\"># Recursively solve for next column<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.solve(col + <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, board, ans, n)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #6A9955\"># Backtrack: remove queen by replacing &#39;Q&#39; with &#39;.&#39;<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                board[row] = board[row][:col] + <\/span><span style=\"color: #CE9178\">&quot;.&quot;<\/span><span style=\"color: #D4D4D4\"> + board[row][col + <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\"> :]<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">solveNQueens<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">n<\/span><span style=\"color: #D4D4D4\">: <\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">) -&gt; List[List[<\/span><span style=\"color: #4EC9B0\">str<\/span><span style=\"color: #D4D4D4\">]]:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        ans = []<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        board = [<\/span><span style=\"color: #CE9178\">&quot;.&quot;<\/span><span style=\"color: #D4D4D4\"> * n <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> _ <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(n)]  <\/span><span style=\"color: #6A9955\"># Initialize n\u00d7n board with dots<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.solve(<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">, board, ans, n)  <\/span><span style=\"color: #6A9955\"># Start from column 0<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> ans<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"4-code-explanation\">Code Explanation<\/h3>\n\n\n\n<p>This brute force solution uses a comprehensive safety check for each queen placement. The&nbsp;<code>isSafe1<\/code>&nbsp;function performs three separate scans: it checks the entire row to the left, the upper-left diagonal, and the lower-left diagonal. For each potential queen position, we scan these three directions completely to ensure no conflicts. The main backtracking happens in&nbsp;<code>solve<\/code>&nbsp;function, which tries placing a queen in each row of the current column, and if it&#8217;s safe, recursively solves for the next column. String slicing is used to place\/remove queens from the board representation.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"5-dry-run\">Dry Run<\/h3>\n\n\n\n<p>Let&#8217;s trace through:&nbsp;<code>n = 4<\/code><\/p>\n\n\n\n<div class=\"wp-block-merpress-mermaidjs diagram-source-mermaid\"><pre class=\"mermaid\">graph TD\n    Root[\"solve(col=0, board=[...., ...., ...., ....], n=4)&lt;br\/>Place queens column by column\"]\n    \n    %% Level 0: col=0, try rows 0-3\n    Root --- A[\"Try row=0&lt;br\/>board=[Q..., ...., ...., ....]&lt;br\/>col=1\"]\n    Root --- B[\"Try row=1&lt;br\/>board=[...., Q..., ...., ....]&lt;br\/>col=1\"]\n    Root --- C[\"Try row=2&lt;br\/>board=[...., ...., Q..., ....]&lt;br\/>col=1\"]\n    Root --- D[\"Try row=3&lt;br\/>board=[...., ...., ...., Q...]&lt;br\/>col=1\"]\n    \n    %% Level 1 from row=0: col=1, check safety for each row\n    A --- A1[\"Try row=0&lt;br\/>Unsafe: same row\"]\n    A --- A2[\"Try row=1&lt;br\/>Unsafe: diagonal\"]\n    A --- A3[\"Try row=2&lt;br\/>Safe!&lt;br\/>board=[Q..., ..Q., ...., ....]&lt;br\/>col=2\"]\n    A --- A4[\"Try row=3&lt;br\/>Safe!&lt;br\/>board=[Q..., ...Q, ...., ....]&lt;br\/>col=2\"]\n    \n    %% Level 1 from row=1: col=1, check safety for each row  \n    B --- B1[\"Try row=0&lt;br\/>Safe!&lt;br\/>board=[.Q.., Q..., ...., ....]&lt;br\/>col=2\"]\n    B --- B2[\"Try row=1&lt;br\/>Unsafe: same row\"]\n    B --- B3[\"Try row=2&lt;br\/>Unsafe: diagonal\"]\n    B --- B4[\"Try row=3&lt;br\/>Safe!&lt;br\/>board=[...., Q..., ...., .Q..]&lt;br\/>col=2\"]\n    \n    %% Level 1 from row=2: col=1, similar pattern\n    C --- C1[\"Try row=0&lt;br\/>Safe!&lt;br\/>board=[.Q.., ...., Q..., ....]&lt;br\/>col=2\"]\n    C --- C2[\"Try row=1&lt;br\/>Unsafe: diagonal\"]\n    C --- C3[\"Try row=2&lt;br\/>Unsafe: same row\"]\n    C --- C4[\"Try row=3&lt;br\/>Safe!&lt;br\/>board=[...., ...., Q..., .Q..]&lt;br\/>col=2\"]\n    \n    %% Level 1 from row=3: col=1, similar pattern\n    D --- D1[\"Try row=0&lt;br\/>Safe!&lt;br\/>board=[.Q.., ...., ...., Q...]&lt;br\/>col=2\"]\n    D --- D2[\"Try row=1&lt;br\/>Safe!&lt;br\/>board=[...., .Q.., ...., Q...]&lt;br\/>col=2\"]\n    D --- D3[\"Try row=2&lt;br\/>Unsafe: diagonal\"]\n    D --- D4[\"Try row=3&lt;br\/>Unsafe: same row\"]\n    \n    %% Level 2 from A3: col=2, board=[Q..., ..Q., ...., ....]\n    A3 --- A3a[\"Try row=0&lt;br\/>Unsafe: same row as Q\"]\n    A3 --- A3b[\"Try row=1&lt;br\/>Unsafe: diagonal conflict\"]\n    A3 --- A3c[\"Try row=2&lt;br\/>Unsafe: same row as Q\"]\n    A3 --- A3d[\"Try row=3&lt;br\/>Unsafe: diagonal conflict\"]\n    A3d --- BacktrackA3[\"All unsafe - Backtrack\"]\n    \n    %% Level 2 from B1: col=2, board=[.Q.., Q..., ...., ....]  \n    B1 --- B1a[\"Try row=0&lt;br\/>Unsafe: same row as Q\"]\n    B1 --- B1b[\"Try row=1&lt;br\/>Unsafe: same row as Q\"]\n    B1 --- B1c[\"Try row=2&lt;br\/>Unsafe: diagonal conflict\"]\n    B1 --- B1d[\"Try row=3&lt;br\/>Safe!&lt;br\/>board=[.Q.., Q..., ..Q., ....]&lt;br\/>col=3\"]\n    \n    %% Level 2 from C1: col=2, board=[.Q.., ...., Q..., ....] - This leads to solution\n    C1 --- C1a[\"Try row=0&lt;br\/>Unsafe: same row as Q\"]\n    C1 --- C1b[\"Try row=1&lt;br\/>Unsafe: diagonal conflict\"]\n    C1 --- C1c[\"Try row=2&lt;br\/>Unsafe: same row as Q\"]\n    C1d[\"Try row=3&lt;br\/>Safe!&lt;br\/>board=[.Q.., ...., Q..., ..Q.]&lt;br\/>col=3\"]\n    C1 --- C1d\n    \n    %% Level 3 from B1d: col=3, board=[.Q.., Q..., ..Q., ....]\n    B1d --- B1d1[\"Try row=0&lt;br\/>Safe!&lt;br\/>board=[.Q.., Q..., ..Q., ...Q]&lt;br\/>col=4\"]\n    B1d --- B1d2[\"Try row=1&lt;br\/>Unsafe: same row as Q\"]\n    B1d --- B1d3[\"Try row=2&lt;br\/>Unsafe: same row as Q\"]\n    B1d --- B1d4[\"Try row=3&lt;br\/>Unsafe: diagonal conflict\"]\n    \n    %% Level 3 from C1d: col=3, board=[.Q.., ...., Q..., ..Q.]\n    C1d --- C1d1[\"Try row=0&lt;br\/>Unsafe: diagonal conflict\"]\n    C1d --- C1d2[\"Try row=1&lt;br\/>Safe!&lt;br\/>board=[.Q.., .Q.., Q..., ..Q.]&lt;br\/>col=4\"]\n    C1d --- C1d3[\"Try row=2&lt;br\/>Unsafe: same row as Q\"]\n    C1d --- C1d4[\"Try row=3&lt;br\/>Unsafe: same row as Q\"]\n    \n    %% Base cases: col=4\n    B1d1 --- Fail1[\"col=4: Solution found but incorrect&lt;br\/>Actually conflicts - backtrack\"]\n    C1d2 --- Success1[\"col=4 == n&lt;br\/>\u2705 Solution 1: ['.Q..', '...Q', 'Q...', '..Q.']\"]\n    \n    %% Continue exploring other paths for second solution\n    D1 --- D1Path[\"Similar exploration leads to&lt;br\/>\u2705 Solution 2: ['..Q.', 'Q...', '...Q', '.Q..']\"]\n    \n    %% Final result\n    Success1 --- Final[\"Final Result:&lt;br\/>[&lt;br\/>  ['.Q..', '...Q', 'Q...', '..Q.'],&lt;br\/>  ['..Q.', 'Q...', '...Q', '.Q..']&lt;br\/>]\"]\n    D1Path --- Final\n\n    %% Styling\n    style Success1 fill:#90EE90\n    style D1Path fill:#90EE90\n    style Final fill:#90EE90\n    \n    style A1 fill:#FFB6C1\n    style A2 fill:#FFB6C1\n    style B2 fill:#FFB6C1\n    style BacktrackA3 fill:#FFB6C1\n    style Fail1 fill:#FFB6C1\n    \n    style A3 fill:#87CEEB\n    style B1 fill:#87CEEB\n    style C1 fill:#87CEEB\n    style B1d fill:#87CEEB\n    style C1d fill:#87CEEB\n    \n    style Root fill:#E6E6FA\n<\/pre><\/div>\n\n\n\n<p>For detailed dry run [<strong><a href=\"https:\/\/mermaid.live\/edit#pako:eNqdmM2SozYUhV9FUWqqkyq3gwD_UXGqbNpeZTGMO5u0eyGDbFODwREwM05XL_MWebo8SYQkwLaQMeMFbax7ji6fri6qfoN-EhDowB3Fxz14flrHgH0-JUn2soZpEn0hP_lJNDV6YJNgGkxf-uzTA9fX1x6Ip_bPv27oL799jLBPwF85IXEKmDg_xGBzkt_W8FVMIa4fPoDfyRcSAcMBcp6MngBNvqbAeLTqbMDj4yOYsZyexfDU4HPJpLzmpHhIYYuqaSuv-ZkXOvcSeq-Ll3vmZape1443vZ7OvCydV-3Y5HWFFoEtTQ4CmqCMesDfE_8zSPGWZCewTSgg2N8XMUI8E7yRAvyPuNA4THkgPLycVCpMBWupCEK8S2IcXSssBd6Kxf_QtLyeZknMa09bgaj17HttnnqcqB1nKZ-LolOBKomxp7xZf3Vi0lOPXFkkqVCRaxdJKu4A2rBvvK5AzQpoGh7CCFNwxFlGaCwkrthtd0PUb7w6GenZoW6lQg9RwS4Vd0O8yLszROs2xCfRZjpCbOo4dTLSU4Woe0Dvbs8OtSoVKmbtwlxBNAXEmSRoVi89TQOSPceSjQy3dkuAU-DVzaoUblqLj-UTb6PQz1Sx31qHmlkDLadbswaiIWD_c0bZhbfvWRSBnGvB2VAL5Tm6pqzpfFULRbKHduVcCTetnVIj9FuLUEVViYM7tv3Fk3tKu7JaWLoalkoDZOvzvA9TEBEcpCBLADvi5VmYlA0WyQ7bFXEl_J5SrsRdS9m9n-0lCa-RbZVH0MjaKus2ELAtTeF6l-2BxZeF0PntL628Olv7rL4qX7NzXVdSqyPyM6n9Hf2jGamrQ6qsWrXu5UrpT6i36q2S3_PG8uo3VlP92E2-VvdKLqXtr69LaYV0jlMCfHZJBUy7WjFR10scRgUuPuaAldz57LiaxwHY5BkIYz-hlPgZn3bmZzmOolMFMGXdY6N094Ii91_lvk_StJoCTKcg5k7__ftPPR1rVS8PBc6HHngoirv4W4AV917_4VV9NjeJszDOCSDfjlFCw3gHkmxP-NFmn_ITd0pYnsFVQ3tC8rTzkcWxxFbyRCRsME-o7IVqqiZPtUjpIkWRMn-EhlSXYVF0lKR5lIkfSzBiFYphlokI-8TDHD71C7-CVjq9Ou5majysTlAwqHNYx1XKq-wUMaTiPmU3pM55G0aR8-PEWCwmxnmAtNMNi8dTR89jZqX7cjkfuuhiyNQOzW8M1acSbQzfBQ2jF7OX8vHIXSzmF1Mg7ZCLbqiCG7KmsfMI_r8BEbIYLobL2TqGPbijYQCdjOakBw-EHnBxC98K4RqyvXEga-iwrwHZ4qIU4Tp-Z7Ijjv9MkkOppEm-20Nni6OU3eXHAGfkiXVOig_Vr5TEAaEuaxMZdExrNOIu0HmD36AzsMd9yzYmYxPZ4xGyrR48QQchqz8YGCMLDewBGiLDeu_Bv_m8qD-ejA3bmkwmw4HJBs33_wEA8kt4\" target=\"_blank\" rel=\"noreferrer noopener\"><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-vivid-purple-color\"><span style=\"text-decoration: underline;\">Click here<\/span><\/mark><\/a><\/strong>]<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"6-time-and-space-complexity\">Time and Space Complexity<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Time Complexity:<\/strong>&nbsp;O(N^N) &#8211; For each of the N^N possible ways to place N queens, we do O(N) safety checks<\/li>\n\n\n\n<li><strong>Space Complexity:<\/strong>&nbsp;O(N^2) &#8211; Board storage plus O(N) recursion depth<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"7-simplifying-it\">Simplifying It<\/h3>\n\n\n\n<p>This approach is like being an extremely cautious chess player who, before placing each queen, carefully examines the entire board in all attack directions to make sure it&#8217;s completely safe. Very thorough, but time-consuming because you&#8217;re doing a lot of redundant checking.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"8-solution-2-optimal-approach-hash-sets-for-o1-conflict-detection\">Solution 2: Optimal Approach (Hash Sets for O(1) Conflict Detection)<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"9-intuition\">Intuition<\/h3>\n\n\n\n<p>Instead of scanning the entire board every time we want to place a queen, what if we kept track of which rows and diagonals are already &#8220;occupied&#8221; by previous queens? It&#8217;s like having a smart notification system that instantly tells you if a position conflicts with existing queens, without having to look around the board. The key insight is that we can represent diagonals mathematically: upper-left to lower-right diagonals have the property that&nbsp;<code>row - col<\/code>&nbsp;is constant, while upper-right to lower-left diagonals have&nbsp;<code>row + col<\/code>&nbsp;constant.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"10-detailed-approach\">Detailed Approach<\/h3>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Use Hash Sets for Tracking<\/strong>: Maintain arrays\/sets to track occupied:\n<ul class=\"wp-block-list\">\n<li><strong>leftrow[row]<\/strong>: Track if row is occupied<\/li>\n\n\n\n<li><strong>lowerDiagonal[row + col]<\/strong>: Track lower-left to upper-right diagonals<\/li>\n\n\n\n<li><strong>upperDiagonal[n &#8211; 1 + col &#8211; row]<\/strong>: Track upper-left to lower-right diagonals<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>Mathematical Diagonal Representation<\/strong>:\n<ul class=\"wp-block-list\">\n<li>Lower diagonal (\u2197): Points with same&nbsp;<code>row + col<\/code>&nbsp;value are on same diagonal<\/li>\n\n\n\n<li>Upper diagonal (\u2196): Points with same&nbsp;<code>row - col<\/code>&nbsp;value are on same diagonal<\/li>\n\n\n\n<li>Offset upper diagonal by&nbsp;<code>n-1<\/code>&nbsp;to avoid negative indices<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>O(1) Safety Check<\/strong>: Just check if the three corresponding positions in our tracking arrays are free<\/li>\n\n\n\n<li><strong>Update Tracking<\/strong>: When placing\/removing queen, update all three tracking arrays<\/li>\n\n\n\n<li><strong>Same Backtracking Structure<\/strong>: Column-by-column placement with backtracking<\/li>\n<\/ol>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"11-code\">Code<\/h3>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro cbp-has-line-numbers\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;--cbp-line-number-color:#D4D4D4;--cbp-line-number-width:calc(2 * 0.6 * .875rem);line-height:1.5rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"class Solution:\n    def solve(self, col, board, ans, leftrow, upperDiagonal, lowerDiagonal, n):\n        # Base case: placed all queens successfully\n        if col == n:\n            ans.append(board[:])  # Make a copy of current board\n            return\n\n        # Try each row in current column\n        for row in range(n):\n            # O(1) safety check using our tracking arrays\n            if (\n                leftrow[row] == 0\n                and lowerDiagonal[row + col] == 0\n                and upperDiagonal[n - 1 + col - row] == 0\n            ):\n                # Place queen and update all tracking arrays\n                board[row] = board[row][:col] + &quot;Q&quot; + board[row][col + 1 :]\n                leftrow[row] = 1\n                lowerDiagonal[row + col] = 1\n                upperDiagonal[n - 1 + col - row] = 1\n                \n                # Recurse to next column\n                self.solve(\n                    col + 1, board, ans, leftrow, upperDiagonal, lowerDiagonal, n\n                )\n                \n                # Backtrack: remove queen and reset tracking arrays\n                board[row] = board[row][:col] + &quot;.&quot; + board[row][col + 1 :]\n                leftrow[row] = 0\n                lowerDiagonal[row + col] = 0\n                upperDiagonal[n - 1 + col - row] = 0\n\n    def solveNQueens(self, n: int) -&gt; List[List[str]]:\n        ans = []\n        board = [&quot;.&quot; * n for _ in range(n)]\n        \n        # Initialize tracking arrays\n        leftrow = [0] * n  # Track occupied rows\n        upperDiagonal = [0] * (2 * n - 1)  # Track upper diagonals\n        lowerDiagonal = [0] * (2 * n - 1)  # Track lower diagonals\n        \n        self.solve(0, board, ans, leftrow, upperDiagonal, lowerDiagonal, n)\n        return ans\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #569CD6\">class<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #4EC9B0\">Solution<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">solve<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">col<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">board<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">ans<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">leftrow<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">upperDiagonal<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">lowerDiagonal<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">n<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Base case: placed all queens successfully<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> col == n:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            ans.append(board[:])  <\/span><span style=\"color: #6A9955\"># Make a copy of current board<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">return<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Try each row in current column<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> row <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(n):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #6A9955\"># O(1) safety check using our tracking arrays<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> (<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                leftrow[row] == <\/span><span style=\"color: #B5CEA8\">0<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #569CD6\">and<\/span><span style=\"color: #D4D4D4\"> lowerDiagonal[row + col] == <\/span><span style=\"color: #B5CEA8\">0<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #569CD6\">and<\/span><span style=\"color: #D4D4D4\"> upperDiagonal[n - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\"> + col - row] == <\/span><span style=\"color: #B5CEA8\">0<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            ):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #6A9955\"># Place queen and update all tracking arrays<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                board[row] = board[row][:col] + <\/span><span style=\"color: #CE9178\">&quot;Q&quot;<\/span><span style=\"color: #D4D4D4\"> + board[row][col + <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\"> :]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                leftrow[row] = <\/span><span style=\"color: #B5CEA8\">1<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                lowerDiagonal[row + col] = <\/span><span style=\"color: #B5CEA8\">1<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                upperDiagonal[n - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\"> + col - row] = <\/span><span style=\"color: #B5CEA8\">1<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #6A9955\"># Recurse to next column<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.solve(<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    col + <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, board, ans, leftrow, upperDiagonal, lowerDiagonal, n<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                )<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #6A9955\"># Backtrack: remove queen and reset tracking arrays<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                board[row] = board[row][:col] + <\/span><span style=\"color: #CE9178\">&quot;.&quot;<\/span><span style=\"color: #D4D4D4\"> + board[row][col + <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\"> :]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                leftrow[row] = <\/span><span style=\"color: #B5CEA8\">0<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                lowerDiagonal[row + col] = <\/span><span style=\"color: #B5CEA8\">0<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                upperDiagonal[n - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\"> + col - row] = <\/span><span style=\"color: #B5CEA8\">0<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">solveNQueens<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">n<\/span><span style=\"color: #D4D4D4\">: <\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">) -&gt; List[List[<\/span><span style=\"color: #4EC9B0\">str<\/span><span style=\"color: #D4D4D4\">]]:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        ans = []<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        board = [<\/span><span style=\"color: #CE9178\">&quot;.&quot;<\/span><span style=\"color: #D4D4D4\"> * n <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> _ <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(n)]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Initialize tracking arrays<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        leftrow = [<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">] * n  <\/span><span style=\"color: #6A9955\"># Track occupied rows<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        upperDiagonal = [<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">] * (<\/span><span style=\"color: #B5CEA8\">2<\/span><span style=\"color: #D4D4D4\"> * n - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">)  <\/span><span style=\"color: #6A9955\"># Track upper diagonals<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        lowerDiagonal = [<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">] * (<\/span><span style=\"color: #B5CEA8\">2<\/span><span style=\"color: #D4D4D4\"> * n - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">)  <\/span><span style=\"color: #6A9955\"># Track lower diagonals<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.solve(<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">, board, ans, leftrow, upperDiagonal, lowerDiagonal, n)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> ans<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"12-code-explanation\">Code Explanation<\/h3>\n\n\n\n<p>This optimal solution eliminates the expensive O(N) safety checks by maintaining three tracking arrays. The clever part is the mathematical representation of diagonals: for any cell (row, col),&nbsp;<code>row + col<\/code>&nbsp;uniquely identifies its lower diagonal, and&nbsp;<code>row - col<\/code>&nbsp;(offset by n-1) uniquely identifies its upper diagonal. Before placing a queen, we just check three array positions in O(1) time. When placing\/removing a queen, we update these arrays to reflect the new state. This transforms our expensive safety checks into simple array lookups.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"13-dry-run\">Dry Run<\/h3>\n\n\n\n<p>Let&#8217;s trace through:&nbsp;<code>n = 4<\/code><\/p>\n\n\n\n<div class=\"wp-block-merpress-mermaidjs diagram-source-mermaid\"><pre class=\"mermaid\">graph TD\n    Root[\"solve(col=0, board=[...., ...., ...., ....], n=4)&lt;br\/>leftrow=[0,0,0,0], upperDiag=[0,0,0,0,0,0,0], lowerDiag=[0,0,0,0,0,0,0]\"]\n    \n    %% Level 0: col=0, try rows 0-3\n    Root --- A[\"Try row=0&lt;br\/>Check: leftrow[0]=0 \u2713, lowerDiag[0]=0 \u2713, upperDiag[3]=0 \u2713&lt;br\/>Place Q, mark arrays&lt;br\/>board=[Q..., ...., ...., ....]&lt;br\/>col=1\"]\n    Root --- B[\"Try row=1&lt;br\/>Check: leftrow[1]=0 \u2713, lowerDiag[1]=0 \u2713, upperDiag[2]=0 \u2713&lt;br\/>Place Q, mark arrays&lt;br\/>board=[...., Q..., ...., ....]&lt;br\/>col=1\"]\n    Root --- C[\"Try row=2&lt;br\/>Check: leftrow[2]=0 \u2713, lowerDiag[2]=0 \u2713, upperDiag[1]=0 \u2713&lt;br\/>Place Q, mark arrays&lt;br\/>board=[...., ...., Q..., ....]&lt;br\/>col=1\"]\n    Root --- D[\"Try row=3&lt;br\/>Check: leftrow[3]=0 \u2713, lowerDiag[3]=0 \u2713, upperDiag[0]=0 \u2713&lt;br\/>Place Q, mark arrays&lt;br\/>board=[...., ...., ...., Q...]&lt;br\/>col=1\"]\n    \n    %% Level 1 from row=0: col=1\n    A --- A1[\"Try row=0&lt;br\/>Check: leftrow[0]=1 \u274c&lt;br\/>Skip - same row occupied\"]\n    A --- A2[\"Try row=1&lt;br\/>Check: leftrow[1]=0 \u2713, lowerDiag[2]=0 \u2713, upperDiag[2]=0 \u2713&lt;br\/>But upperDiag[2] conflicts with diagonal&lt;br\/>Actually safe! Place Q\"]\n    A --- A3[\"Try row=2&lt;br\/>Check: leftrow[2]=0 \u2713, lowerDiag[3]=0 \u2713, upperDiag[1]=0 \u2713&lt;br\/>Safe! board=[Q..., ..Q., ...., ....]&lt;br\/>col=2\"]\n    A --- A4[\"Try row=3&lt;br\/>Check: leftrow[3]=0 \u2713, lowerDiag[4]=0 \u2713, upperDiag[0]=0 \u2713&lt;br\/>Safe! board=[Q..., ...Q, ...., ....]&lt;br\/>col=2\"]\n    \n    %% Level 1 from row=1: col=1\n    B --- B1[\"Try row=0&lt;br\/>Check: leftrow[0]=0 \u2713, lowerDiag[1]=0 \u2713, upperDiag[4]=0 \u2713&lt;br\/>Safe! board=[.Q.., Q..., ...., ....]&lt;br\/>col=2\"]\n    B --- B2[\"Try row=1&lt;br\/>Check: leftrow[1]=1 \u274c&lt;br\/>Skip - same row occupied\"]\n    B --- B3[\"Try row=2&lt;br\/>Check: leftrow[2]=0 \u2713, lowerDiag[3]=0 \u2713, upperDiag[2]=0 \u2713&lt;br\/>Skip - diagonal conflict\"]\n    B --- B4[\"Try row=3&lt;br\/>Check: leftrow[3]=0 \u2713, lowerDiag[4]=0 \u2713, upperDiag[1]=0 \u2713&lt;br\/>Safe! board=[...., Q..., ...., .Q..]&lt;br\/>col=2\"]\n    \n    %% Level 1 from row=2: col=1\n    C --- C1[\"Try row=0&lt;br\/>Check: leftrow[0]=0 \u2713, lowerDiag[2]=0 \u2713, upperDiag[5]=0 \u2713&lt;br\/>Safe! board=[.Q.., ...., Q..., ....]&lt;br\/>col=2\"]\n    C --- C2[\"Try row=1&lt;br\/>Check: leftrow[1]=0 \u2713, lowerDiag[3]=0 \u2713, upperDiag[4]=0 \u2713&lt;br\/>Skip - diagonal conflict\"]\n    C --- C3[\"Try row=2&lt;br\/>Check: leftrow[2]=1 \u274c&lt;br\/>Skip - same row occupied\"]\n    C --- C4[\"Try row=3&lt;br\/>Check: leftrow[3]=0 \u2713, lowerDiag[5]=0 \u2713, upperDiag[3]=0 \u2713&lt;br\/>Skip - diagonal conflict\"]\n    \n    %% Level 1 from row=3: col=1\n    D --- D1[\"Try row=0&lt;br\/>Check: leftrow[0]=0 \u2713, lowerDiag[3]=0 \u2713, upperDiag[6]=0 \u2713&lt;br\/>Safe! board=[.Q.., ...., ...., Q...]&lt;br\/>col=2\"]\n    D --- D2[\"Try row=1&lt;br\/>Check: leftrow[1]=0 \u2713, lowerDiag[4]=0 \u2713, upperDiag[5]=0 \u2713&lt;br\/>Safe! board=[...., .Q.., ...., Q...]&lt;br\/>col=2\"]\n    D --- D3[\"Try row=2&lt;br\/>Check: leftrow[2]=0 \u2713, lowerDiag[5]=0 \u2713, upperDiag[4]=0 \u2713&lt;br\/>Skip - diagonal conflict\"]\n    D --- D4[\"Try row=3&lt;br\/>Check: leftrow[3]=1 \u274c&lt;br\/>Skip - same row occupied\"]\n    \n    %% Level 2: Continue with valid paths\n    B1 --- B1_continue[\"Continue exploration...&lt;br\/>leads to path with conflicts\"]\n    \n    C1 --- C1d[\"Try row=3 at col=2&lt;br\/>Safe! board=[.Q.., ...., Q..., ..Q.]&lt;br\/>col=3\"]\n    \n    D1 --- D1_continue[\"Continue exploration...&lt;br\/>leads to first solution\"]\n    \n    %% Level 3 from C1d: col=3\n    C1d --- C1d2[\"Try row=1 at col=3&lt;br\/>Check all arrays - Safe!&lt;br\/>board=[.Q.., .Q.., Q..., ..Q.]&lt;br\/>col=4\"]\n    \n    D1_continue --- Solution1[\"col=4 == n&lt;br\/>\u2705 Solution 1: ['..Q.', 'Q...', '...Q', '.Q..']\"]\n    \n    %% Level 4 from C1d2: Base case\n    C1d2 --- Solution2[\"col=4 == n&lt;br\/>\u2705 Solution 2: ['.Q..', '...Q', 'Q...', '..Q.']\"]\n    \n    %% Final result\n    Solution1 --- Final[\"Final Result:&lt;br\/>[&lt;br\/>  ['..Q.', 'Q...', '...Q', '.Q..'],&lt;br\/>  ['.Q..', '...Q', 'Q...', '..Q.']&lt;br\/>]\"]\n    Solution2 --- Final\n\n    %% Styling\n    style Solution1 fill:#90EE90\n    style Solution2 fill:#90EE90\n    style Final fill:#90EE90\n    \n    style A1 fill:#FFB6C1\n    style B2 fill:#FFB6C1\n    style B3 fill:#FFB6C1\n    style C2 fill:#FFB6C1\n    style C3 fill:#FFB6C1\n    style C4 fill:#FFB6C1\n    style D3 fill:#FFB6C1\n    style D4 fill:#FFB6C1\n    \n    style A3 fill:#87CEEB\n    style B1 fill:#87CEEB\n    style C1 fill:#87CEEB\n    style D1 fill:#87CEEB\n    style C1d fill:#87CEEB\n    style C1d2 fill:#87CEEB\n    \n    style Root fill:#E6E6FA\n<\/pre><\/div>\n\n\n\n<p>For detailed dry run [<strong><a href=\"https:\/\/mermaid.live\/edit#pako:eNqtl81u4zYQx1-FZbFIF5BdUZJlS6gLxLJz6qHa7Kl2UHAt2hYiS4Y-knWDHHvbW6_bl8uTlCJpfS1l2eo6gB1xZji_of4cUS9wHXkE2nAb48MOfJyvQkA_H6IoXa5gEgVP5Kd1FExVBXyKcOxNl0P6UUDz-0EB4dR4_8un-OdfA7JJ4-h5ulQV9kdt2eFA4rmPt8VgYQqiZ7lpBR84DP9-9w78Rp5IAFQbCKI0PgKaKAHqQC-5wWAwALeU_iM3T1VG5ezI-tEGAm6pPkxV8Pb1nwpAZazgXepijM3xe4DXBLgK2OP4EeA4xseEGcTauPK1YS45MypqKkBnFVAkA0USUCQB1a4B5XDuNaBOBVSTgWoSUE0Ciq4HbeKeBZ1XQHUZqC4B1SWgal_QElcG2pAzAps42nOhcmUj7nHLhYwuUDICb_9-Ybb7R_8ABiDBe5JHgGi9zg4-8YrsYlatj-y0LtnNsrRmouWEm8Bfpwl49tMd8OhwFOKAOd-u0wwHwZHCbsgPQCxwE1TvIzu9S3b3LGVj17otm0FrMhl9FGZ0KUzKNHS7mNrlhGpymvF2g_o0Rlm_MVrZ6UKebS4lu2C6RIxXSFzM-t2UU5O4yH5ScqHwZvbvppF23UqauHutRrSaRhze6XtpRNYcRh0aae_rJbtg6tWw9E7ddt1Nkf0SLV2hUDFrL42Mug4pnTW1q0GvqWHOH6e91CBbefMiNcgenqUaBFMvNRjXKbTYURcy9eo3o_-tUJH9Ei1dodCGRmibcKIw9cOM8Cf5Ew58DxxwuktE20Pi-fLnWjhSoCKGfD4EUYxTPwrpIoq3BOwlII3YJHzS4rTQwHCQ6EtetUiAU6ZW7bLu4lbund5IMEdC6lfDb_w4SQF9T8pyc9vy6XyL0QL4BtNPdXmnwmqCPlVWuY-AnpTEqZPeN1Zs7fTplmKVFWx8U3BRKSO4FwXke535g-kUhCz87evfhRnQI8XyJp_6RgE3eaL8Nz-lsF86cNP62mYUa0DFNMMJAWv6VSyEVuPQOjg0xuHW85c8rpTjzs83UEySLEj5YFE2S87sNDH3-8D8bJZ7yb5BZ-1K6XeWjbmVhEXVJcYqLLDv02Pgh1t-ndALUuHe-EFg_2ipi4Wlyjy0Vg9e5bfWqs_tKcHd3cx0UNU009pNeqvJaY9yzkQZraZ5e9RcFlWr7hQ7GTuLxaxWAmo1Oe2m-bko75xNkxirLuzllrsszIV5d7sKoQK3se9BO40zosA9ifc4v4QveeAKpjuyJyto0389ssG55uEqfKVhBxz-EUX7U2QcZdsdtDc4SOhVdvBwSvLnUIz3xWhMQo_ETpSFKbQ1U0dsFmi_wM_QNsZDTbeQpemqNbEMyzAVeIT2ZDQ0Td20tIk1NsbaZPKqwL9YXjQc6ZMxGlOzalkmGuuv_wGJlbGD\" target=\"_blank\" rel=\"noreferrer noopener\"><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-vivid-purple-color\"><span style=\"text-decoration: underline;\">Click here<\/span><\/mark><\/a><\/strong>]<\/p>\n\n\n\n<p><strong>The tracking arrays instantly tell us conflicts without scanning the board!<\/strong><\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"14-time-and-space-complexity\">Time and Space Complexity<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Time Complexity:<\/strong>&nbsp;O(N!) &#8211; Still exponential, but with much faster O(1) conflict detection<\/li>\n\n\n\n<li><strong>Space Complexity:<\/strong>&nbsp;O(N) &#8211; Three tracking arrays plus O(N) recursion depth<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"15-simplifying-it\">Simplifying It<\/h3>\n\n\n\n<p>This approach is like having a smart assistant who keeps track of where all your queens are placed and can instantly tell you &#8220;Yes, that position is safe&#8221; or &#8220;No, that would create a conflict&#8221; without having to look at the board. The mathematical diagonal representation is the key insight that makes this instant lookup possible.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"16-summary\">Summary<\/h2>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><thead><tr><th>Approach<\/th><th>Time<\/th><th>Space<\/th><th>Difficulty<\/th><th>Best For<\/th><\/tr><\/thead><tbody><tr><td>Brute Force (Full Board Scan)<\/td><td>O(N^N)<\/td><td>O(N^2)<\/td><td>Medium<\/td><td>Understanding the problem<\/td><\/tr><tr><td>Optimal (Hash Set Tracking)<\/td><td>O(N!)<\/td><td>O(N)<\/td><td>Hard<\/td><td>Production code<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>The&nbsp;<strong>optimal approach<\/strong>&nbsp;is dramatically better because it reduces conflict detection from O(N) to O(1), which compounds significantly over the exponential search space. The key insights are:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Mathematical diagonal representation<\/strong>&nbsp;&#8211; Using&nbsp;<code>row \u00b1 col<\/code>&nbsp;to uniquely identify diagonals<\/li>\n\n\n\n<li><strong>Constant-time conflict detection<\/strong>&nbsp;&#8211; Hash sets\/arrays for O(1) lookups<\/li>\n\n\n\n<li><strong>Smart state tracking<\/strong>&nbsp;&#8211; Update tracking arrays during backtracking<\/li>\n<\/ol>\n\n\n\n<p>The N-Queens problem is a classic example of how the right data structures can transform an expensive operation (board scanning) into a cheap one (array lookup), leading to dramatic performance improvements in backtracking algorithms!<\/p>\n\n\n\n<div class=\"wp-block-buttons is-content-justification-center is-layout-flex wp-container-core-buttons-is-layout-16018d1d wp-block-buttons-is-layout-flex\">\n<div class=\"wp-block-button\"><a class=\"wp-block-button__link wp-element-button\" href=\"https:\/\/codeanddebug.in\/course\/zero-to-hero-python-dsa\" target=\"_blank\" rel=\"noreferrer noopener\">Join our Advance DSA COURSE<\/a><\/div>\n<\/div>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><em>For any changes to the article, kindly email at <a href=\"mailto:code@codeanddebug.in\" target=\"_blank\" rel=\"noreferrer noopener\">code@codeanddebug.in<\/a> or contact us at <a href=\"tel:+91-9712928220\" target=\"_blank\" rel=\"noreferrer noopener\">+91-9712928220<\/a>.<\/em><\/p>\n\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>The&nbsp;n-queens&nbsp;puzzle is the problem of placing&nbsp;n&nbsp;queens on an&nbsp;n x n&nbsp;chessboard such that no two queens attack each other. Given an integer&nbsp;n, return&nbsp;all distinct solutions to the&nbsp;n-queens puzzle. You may return the answer in&nbsp;any order. Each solution contains a distinct board configuration of the n-queens&#8217; placement, where&nbsp;&#8216;Q&#8217;&nbsp;and&nbsp;&#8216;.&#8217;&nbsp;both indicate a queen and an empty space, respectively. Here&#8217;s<\/p>\n","protected":false},"author":1,"featured_media":770,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3,5],"tags":[32,18],"class_list":{"0":"post-767","1":"post","2":"type-post","3":"status-publish","4":"format-standard","5":"has-post-thumbnail","7":"category-data-structures-and-algorithm","8":"category-expert","9":"tag-advance-recursion","10":"tag-hard"},"featured_image_src":"https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/07\/n-queens-featured-image.png","author_info":{"display_name":"codeanddebug","author_link":"https:\/\/codeanddebug.in\/blog\/author\/codeanddebug\/"},"_links":{"self":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/767","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/comments?post=767"}],"version-history":[{"count":2,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/767\/revisions"}],"predecessor-version":[{"id":778,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/767\/revisions\/778"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media\/770"}],"wp:attachment":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media?parent=767"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/categories?post=767"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/tags?post=767"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}