Nuggets team number online, help you Offer impromptu! Click to view spring recruitment positions in big factories

I. Title Description:

The n Queens problem is the study of how to place n queens on an n by n board so that queens cannot attack each other.

Given an integer n, return all the different solutions to the n queen problem.

Each solution contains a different chess placement scheme for the N-queen problem, in which ‘Q’ and ‘.’ represent queens and slots, respectively.

Example 1:

Input: n = 4 output: [[". Q.. ", "... Q ", "Q...", ".. Q. "], [".. Q. ", "Q...", "... Q ", ". Q.. "]] : as shown in the above, 4 queen problems exist two different solutions.Copy the code

Example 2:

Input: n = 1 Output: [["Q"]Copy the code

Subject address: leetcode-cn.com/problems/n-…

Ii. Analysis of Ideas:

Very classic recursion + backtracking algorithm problem. Each time a queen is placed in the recursion, it is necessary to go back to the previous state after the current condition is determined. Then place the queen in the next available position.

Recurse row by row, and each time you recurse, try to place a queen in a row. Until the current line can no longer put the queen, backtrace to the previous line. Keep trying. The time consuming part is deciding whether the current position is suitable for placing the queen. You can just go through the whole checkerboard, and you can always tell if there’s a conflict, and the way to optimize the point is to loop through all the rows. You can tell. Here, by swapping space for time, you can directly determine whether you can place the queen or not without going through the loop.

Four arrays need to be initialized

XFlag [I] = true: indicates that the queen has been placed on line I. YFlag [I] = true: indicates that the queen has been placed in column I. MdFlag [I] = true: indicates that the queen has been placed on the main diagonal of I. SdFlag [I] = true: indicates that the queen has been placed on the I diagonal. Main diagonal (mdFlag) : 1 2 3 4 5 2 3 4 5 6 3 4 5 6 7 4 5 6 7 8 5 6 6 8 9 If mdFlag[4] = true, then it indicates that a queen has been placed at some position of value 4. Sub-diagonal (sdFlag) : 5 4 3 2 1 6 5 4 3 2 7 6 5 4 3 8 7 6 6 5 4 9 8 7 6 5 If mdFlag[6] = true, then it indicates that the queen has been placed at some position with the value of 6. We don't need to know where the queen has been placed, we just need to know if there's a queen in the current row, the current column, the current diagonal. Correspondence: If the queen is placed in position (I,j). XFlag [I] =true yFlag[j] =true mdFlag[I +j] =true sdFlag[I + n-J-1] =true PS: In fact, we recursive by row, so we can not use xFlag arrayCopy the code

Iii. AC Code:

Public static List<List<String>> solveNQueens(int n) {// line Boolean [] xFlag = new Boolean [n]; Boolean [] yFlag = new Boolean [n]; Boolean [] mdFlag = new Boolean [2 * n-1]; Boolean [] sdFlag = new Boolean [2 * n-1]; char[][] checkerboard = new char[n][n]; List<List<String>> ansList = new ArrayList<>(); Arrays.fill(xFlag, false); Arrays.fill(yFlag, false); Arrays.fill(mdFlag, false); Arrays.fill(sdFlag, false); // Initialize checkerboard for (char[] item: checkerboard) {array.fill (item, '.'); } setQueens(checkerboard, xFlag, yFlag, mdFlag, sdFlag, 0, n, ansList); return ansList; } private static void setQueens(char[][] checkerboard, boolean[] xFlag, boolean[] yFlag, boolean[] mdFlag, boolean[] sdFlag, int x, int n, List<List<String>> ansList) { if (x == n) { List<String> ansItem = new ArrayList<>(); for (char[] item : checkerboard) { ansItem.add(new String(item)); } ansList.add(ansItem); return; } for (int i = 0; i < n; i++) { if (xFlag[x]) { return; } if (yFlag[i]) { continue; } if (mdFlag[x + i]) { continue; } if (sdFlag[x + n - i - 1]) { continue; } checkerboard[x][i] = 'Q'; xFlag[x] = true; yFlag[i] = true; mdFlag[x + i] = true; sdFlag[x + n - i - 1] = true; setQueens(checkerboard, xFlag, yFlag, mdFlag, sdFlag, x + 1, n, ansList); xFlag[x] = false; yFlag[i] = false; mdFlag[x + i] = false; sdFlag[x + n - i - 1] = false; checkerboard[x][i] = '.'; }}Copy the code

Four,

The irony is that Python is so friendly to arrays that it can do the same thing in half as much code as Java.