Shulou(Shulou.com)06/01 Report--

[topic description]

The n-queens puzzle is the problem of placing n queens on an n × n chessboard such that no two queens attack each other.Given an integer n, return all distinct solutions to the n-queens puzzle.Each solution contains a distinct board configuration of the nqueens' placement, where'Q 'and'. Both indicate a queen and an empty space respectively.

The problem for queens is to put n queens on the chessboard of naughn, and queens can't have sex with each other. Given an integer n, returns all different solutions to the n queen problem. Each solution contains a clear n-queen placement layout, where "Q" and "." It represents a queen and an empty position, respectively.

[topic link]

Http://www.lintcode.com/en/problem/n-queens/

[topic Analysis]

In the classical DFS recursive backtracking method, the general idea is to try each row according to each column, and then save the results without trying.

The difficulty is probably to use an one-dimensional array to store the coordinates of the queen. For a chessboard, each point has horizontal and vertical coordinates, which can be used to represent a point.

Coincidentally, there can be only one queen per row, that is, there can be only one ordinate for a row, so using a 1-dimensional array can help solve the problem that queens can't be on the same line in advance.

If expressed in an one-dimensional array, the method is that the subscript of the one-dimensional array represents the Abscissa (which row), and the value of the array represents the ordinate (which column).

In this way, the coordinates of the queen can be represented by an one-dimensional array. It is this one-dimensional array that does not need to perform a remove reset operation when looking for results, because if backtracking happens to go back to the previous row, you can find the next legal column coordinates.

Because it is searched according to each row, when the row coordinate value is equal to the number of rows, it means that all the rows on the chessboard have placed the queen, then mark the position of the queen as Q and the place where there is no queen as 0.

According to the one-dimensional array mentioned above, we can traverse the whole chessboard. When the coordinate is (row,columnVal [row]), it means that this is the position of the queen. Just mark Q.

[reference answer]

Http://www.jiuzhang.com/solutions/n-queens/

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.