Number connect game in C/C++?

Game - Suppose there is an n × n square array. Among them, some squares are empty, some are solid, and some non-solid squares are set by integers 1, 2, 3,... Each integer holds or occupies exactly two different squares on the board. The player's task is to connect the two occurrences of each integer on the board with the help of simple paths that implement only horizontal and vertical movements. Two different paths are not allowed to intersect each other. No path can contain any solid blocks (solid blocks are not allowed on any path). Finally, all non-solid squares must be filled by paths.

Algorithm - To construct an efficient random puzzle with a given board size n × n, we first generate random simple mutually disjoint paths on the blackboard. If some isolated blocks are still outside all generated paths, mark these isolated blocks as solid (forbidden). Next, we provide the path's endpoints and a list of solid squares as the puzzle.

So we first generate a solution and then calculate the puzzle based on that solution. Paths and solid squares separate n × n plates. We implement and find the data structure to generate this partition. The data structure handles a subset of the set of n^2 squares on the chessboard.

Pseudocode

• The positioning squares (a, b) and (c, d) appear randomly on the chessboard, making -

  • (a, b) and (c, d) are neighbors of each other, and

  • (a, b) and (c, d) are not part of the generation so far any path. if in Entire board, returns FAILURE /* Here, (a​​, b) and (c, d) are the first two squares on the new path establish. */

• Union two union search trees, which contains (a, b) and (c, d).

• Repeat until the current path can be expanded -

  Rename (a, b) = (c, d).

Find a randomly adjacent square (c, d) (a, b) such that -

• ( c, d) does not belong to any path generated so far (including the current path)

• The only neighbor (c, d) on the current path built in part is (a, b).

If no such neighbor (c, d) is found, the path cannot be extended further, thus breaking the cycle

Otherwise, find the two tree to which (a, b) and (c, d) belong.

Set the endpoint flags of the two blocks located at the start and at the start to terminate the new path.

Return SUCCESS

The above is the detailed content of Number connect game in C/C++?. For more information, please follow other related articles on the PHP Chinese website!