Electrical Engineering@Techno Main Saltlake'24 || Expert @CodeStudio || LeetCode Rating: 1624(highest) || 5? C++ @HackerRank || 5? Java @HackerRank
?? ?????? ?????? - ?????? ???????? ???? ?????????????? ?????????????? ?? Day 77/160: 30th January ?????????????? : N-Queen Problem ?????????????? ????????: https://lnkd.in/g3WthQ_b ?????????????? ??????????????????: The?n-queens puzzle is the problem of placing n queens on a?(n × n)?chessboard such that no two queens can attack each other. Note that two queens attack each other if they are placed on the same row, the same column, or the same diagonal. Given an integer?n, find all distinct solutions to the?n-queens puzzle. You can return your answer in?any?order but each solution should represent a distinct board configuration of the queen placements, where the solutions are represented as permutations of [1, 2, 3, ..., n]. In this representation, the number in the?ith?position denotes the row in which the queen is placed in the?ith?column. For eg. below figure represents a chessboard?[3 1 4 2]. Examples: Input: n = 1 Output: [1] Explaination: Only one queen can be placed in the single cell available. Input: n = 4 Output: [[2 4 1 3 ] [3 1 4 2 ]] Explaination: There are 2 possible solutions for n = 4. Input: n = 2 Output: [] Explaination: There are no possible solutions for n = 2. Constraints: 1 ≤ n ≤ 10 ???????????????????????????? ??????????: ? Input Parameters and State Tracking list: A 2D list (ArrayList<ArrayList<Integer>>) that stores all valid solutions, where each solution is represented as a list of integers indicating column positions for queens in each row. board: A 2D array (int[][]) used to track queen placements on the chessboard. ? Base Case When col >= N (all queens are placed successfully), invoke printSolution to store the current configuration in list. ? Safety Check for Queen Placement (isSafe): This function ensures that a queen can be safely placed at (row, col) by checking: Row on the left: No other queens should be present in the same row to the left of the column. Upper-left diagonal: Lower-left diagonal: No queens should exist diagonally in the lower-left direction. ? Recursive Backtracking (solveNQueen): Try placing a queen in each row of the current column col. For each valid placement (isSafe returns true): Place the queen (board[row][col] = 1). Recursively solve for the next column (col + 1). Backtrack by removing the queen (board[row][col] = 0) when the recursion completes. ???????? ????????????????????: O(N!) Each column tries placing a queen in one of the N rows. For each placement, recursive calls explore the remaining columns. This results in a factorial growth in possibilities. ?????????? ????????????????????: O(N2) Recursive stack space is proportional to N calls in the worst case. Additional space is used to store solutions in list. Grateful to GeeksforGeeks for this incredible opportunity to showcase our skills ? and for helping us maintain consistency in our learning journey ????. Let's code together, let's think together ?? #geekstreak2024 #gfg160 #GeeksforGeeks
