Use backtracking to calculate the maximum score of the game

preface

It’s a very, very simple match-and-match game. In an M by N grid, there are all kinds of objects. Players can swap two items in either column or row. When there are 3 to 5 consecutive identical items in a column or row direction, these items can be eliminated. Eliminating 3,4,5 consecutive identical items scores 1,3,10, respectively. When an item is eliminated, the item above it drops vertically to fill the void. If 3 to 5 consecutive identical items remain after the fill, continue to eliminate. If the swap operation does not eliminate any items, the operation is prohibited. The task is to get the highest score in a given number of steps.

As shown in the figure above, after swapping the 2 and 3 in the figure, there will be four consecutive 2’s and three 3’s, which will then be eliminated together, scoring 1 + 3 = 4 points. In fact, after the re-elimination is complete, items above the drop will appear in a row of 3 2’s and 4 4’s can also be eliminated.

Write a simple elimination

Basic algorithm ideas and problems to be solved

The basic algorithm idea is as follows:

Swap two points that need to be swapped;
Starting from the point of exchange, the number of consecutive and same elements on the left, right and left are counted respectively, and the points are scored according to the scoring rules. The exchange of points is forbidden if no element can be eliminated after the exchange.
Eliminate the element that needs to be eliminated, then move the element above the eliminated element down to fill the gap, and mark the spot where the top is empty as no item;
Conduct an overall check and mark each point as described in Step 2.
If the full check finds that there are still elements that can be eliminated, go back to Step 3. Otherwise, end the check adjustment.

In order to solve the problem of calculating the maximum score of a vanish game by backtracking, we need to implement a simple vanish game first. The two main problems that a match-free game needs to solve are as follows (here the game grid is called the board) :

Check for 3 to 5 consecutive identical items
Calculate the score after eliminating the item
The checkerboard adjusts after eliminating items and dropping items

Problem 1: Check whether there are 3 to 5 consecutive identical items

According to the rules of the game, each operation is to exchange two adjacent points, so we only need to start from the point of exchange to check the four directions of up, down, left and right. In order to facilitate the implementation of the program, we implement Enum classes in the following four directions, in which the Point class only has two attributes row and COL.

ArrowE.class

public enum ArrowE {
    UP(1."^"."up".new Point(-1.0)),
    RIGHT(2.">"."right".new Point(0.1)),
    DOWN(3."v"."down".new Point(1.0)),
    LEFT(4."<"."left".new Point(0, -1));private final int value;
    private final String arrow;
    private final String name;
    private final Point vector;

    private static final Map<ArrowE, ArrowE> arrowMapReverse;
	
    static {
        arrowMapReverse = new HashMap<ArrowE, ArrowE>();
        addReverse(ArrowE.UP, ArrowE.DOWN);
        addReverse(ArrowE.LEFT, ArrowE.RIGHT);
    }
    // getters and setters.// Get the method in the opposite direction
    public ArrowE getReverse(a) {
        return arrowMapReverse.get(this); }}Copy the code

The basic idea is simple: start at a point and count the total number of identical items up and down, numUp and numDown, and the total number of identical items left and right, numLeft and numRight, respectively. Then calculate the score of numUp + 1 + numDown and numLeft + 1 + numRight according to the calculation rules. If the score is greater than 0, the operation of item elimination will be performed. Otherwise, the subsequent operation will not be calculated.

By the above logic, it seems simple and can be eliminated immediately. It seems that only the range specified by the exchange point and numUp numDown numLeft numRight can be eliminated. However, in the actual operation, more complex scenarios will appear. The diagram below:

After a normal exchange, the rows and rows of exchange points can be checked in the manner described above and erasable positions marked. However, after the exchange, a very complicated scene can occur due to the drop of items, as shown in Figure 3 above. Even more complex situations can occur where there are multiple disconnected areas that can be eliminated. In this case, the entire board can only be checked to find all areas that can be eliminated.

There are two rows and four columns in the eliminable region of Figure 3 in the figure above, among which some positions will act on the same row and column at the same time, such as [3, 0], [3, 1], etc. By designating a tag value, an element is marked as participating in the elimination of rows or columns. A tag value of 1 means that the element is eliminated in the row, 2 in the column, and 3 in both the row and column (where 1 + 2 = 3 is very clever). If a point participates in the elimination of rows, it can no longer participate in the elimination of other rows, but can continue to participate in the elimination of other columns. Similarly, if this point participates in the elimination of columns, then this point can no longer participate in the elimination of other columns, but can participate in the elimination of other columns. When the value of the marked position is 3, that point cannot continue to participate in the elimination of other rows or columns.

Since the area formed by the elements to be eliminated cannot be simply expanded from a point to the top, bottom and left, a two-dimensional array needs to be designed for marking. The labeled bitmap below can be obtained in Figure 3 above.

During the marking process, you can keep score in the simple way, or you can directly score the column statistics of the two-dimensional array of marks.

Question 2: Calculate the score after eliminating items

This has been explained briefly above and will not be repeated here.

Problem 3: Checkerboard adjustments after eliminating items and dropping items

Elimination is also important to the whole process, but it is neither simple nor complicated. According to the two-dimensional tag array, find the column with the element to be eliminated, and perform the drop operation on the column. The core code is just one line:

chessboard[row][col] = chessboard[row - offset][col];
Copy the code

The complete code for column elimination drops is as follows:

/** * select * from col, The point at the offset above (row, col) falls to the position starting from (row, col) * this will drop from (row, col) Col) start overwrite * <pre> * 0 0 0 0 0 * 0 0 0 1 0 * 0 0 0 x 0 * 0 0 0 0 x 0 * 0 0 0 0 * 0 * 0 0 0 0 (*) 0 * v * row = row(*),col=col(*),offset=num(*) * v * 0 0 0 0 0 * 0 0 0 0 0 * 0 0 0 0 0 * 0 0 0 1 0 * 0 0 0 x 0 * 0 0 0 x 0 * </pre> *@paramRow Indicates the row number of the destination location *@paramCol The column number of the destination location *@paramOffset Drop distance */
private void dropColDownTo(int row, int col, int offset) {
    if(offset == 0) {
        return;
    }
    while(row - offset >= 0) {
        // If chessboard[row][col] == 0, all points above chessboard[row][col] are 0
        chessboard[row][col] = chessboard[row - offset][col];
        row --;
    }
    while(row >= 0&& chessboard[row][col] ! =0) {
        chessboard[row][col] = 0; row --; }}Copy the code

The complete adjustment to the entire board is implemented with a double for loop as follows. One particular detail is that you must adjust each column from top to bottom. Because if you adjust from the bottom to the top, you change the position of the top element. As a result, adjusting the upper element after the adjustment does not adjust to the correct element.

/** * Removes marked elements within the specified range. The elimination method is: detect each column from left to right, and then eliminate and drop each column from top to bottom. * <pre> * 0 0 0 0 * (1)(1)(1) 0 * 3 3 2 0 * 4 (2)(2)(2) * * 0 0 0 0 * (0)(1)(1) 0 * 3 3 2 0 * 4 (2)(2)(2) * * 0 0 0 0 * (0)(0)(1) 0 * 3 3 2 0 * 4 (2)(2)(2) * * 0 0 0 0 * (0)(0)(1) 0 * 3 3 2 0 * 4 (0)(2)(2) * </pre> *@paramRange Range to be adjusted *@paramMarks marks the element to eliminate */
private void eliminateAndDropDownAdjust(DetectionRange range, int[][] marks) {
    for(int c = range.getColLeft(); c <= range.getColRight(); c ++) {
        // Adjust each column from top to bottom
        for(int r = range.getRowTop(); r <= range.getRowBottom(); r ++) {
            // Calculate the length of the eliminated column
            int originalR = r;
            while(r <= range.getRowBottom() && marks[r][c] ! =0) {
                // Untag
                marks[r ++][c] = 0;
            }
            dropColDownTo(r - 1, c, r - originalR); }}}Copy the code

The elimination of items and the adjustment of the board are basically done here. Notice, however, that there is a special class, DetectionRange, in the code above. This class, as its name suggests, is “detection range,” and after counting elements as needed and calculating scores, it does not need to adjust the entire board, only the affected range. Some calculations can be reduced by limiting the scope.

There is also a small optimization mentioned above, that is, when testing, the overall testing starts from the lower left corner, and checks to the right and up. This is because after elimination, there are no items at the top, so it is meaningless to repeat the detection. In addition, the detection of only the “right” and “up” directions can cover all the detection, and there is no need for “left” and “down” detection, because “right” and “left”, “up” and “down” can be equivalent.