1. Topic source

Link: 181. Swing Game

Related links:

• [dfs] aw180. Book arrangement (IDA*+dfs in-depth understanding + thinking + good questions)

2. Topic analysis

The application of IDA * and code skills is also a classic application of IDA *.

8 operations, so that the middle 8 numbers become the same, and each step of operation is output according to the minimum dictionary order.

dfs can be very deep, because one operation and reverse operation will cancel out. But the answer should be in a shallow layer. Therefore, we can use iterative deepening to optimize the search answer of this question, and then introduce the valuation function to prune in advance, which becomes IDA *, which is more efficient.

Valuation function design:

• Each operation will affect the middle 8 numbers, one in and one out.
• Each operation is best to make the middle 8 numbers better.
• Count the number that appears the most in the middle 8 numbers. If the number is CNT, it will take at least 8-cnt operations to make the middle 8 numbers consistent.
• Therefore, it can be used as the valuation function to prune in advance with the current number of layers and the number of layers set by iteration deepening.

skill:

• Obviously, the current operation cannot be the inverse of the previous operation, otherwise it is equivalent to no change. Therefore, in the process of dfs, you need to record what the last operation was and add a parameter last to represent it.
• There are many kinds of operations, but the operation methods are the same. We can number each lattice, map the operands of each operation to a one-dimensional array, and then operate uniformly. This is a very important skill.
• Dictionary order is the smallest. Just search according to the minimum dictionary order A~H. If you find the answer, it must be the minimum dictionary order.

Handwritten notes:

Time complexity: O ( 7 k ) O(7^k) O(7k) . Assume that the answer requires at least k k In step k, 7 different operations need to be enumerated each time (except the reverse operation in the previous step), so enumeration is required in the worst case 7 k 7^k 7k schemes. However, after adding the heuristic function, the actual number of states enumerated is very small.

Space complexity: O ( n ) O(n) O(n)

/*
      0     1
      2     3
4  5  6  7  8  9  10
      11    12
13 14 15 16 17 18 19
      20    21
      22    23
*/

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 24;

// Operands of 8 operations
int op[8][7] = {
    {0, 2, 6, 11, 15, 20, 22},
    {1, 3, 8, 12, 17, 21, 23},
    {10, 9, 8, 7, 6, 5, 4},
    {19, 18, 17, 16, 15, 14, 13},
    {23, 21, 17, 12, 8, 3, 1},
    {22, 20, 15, 11, 6, 2, 0},
    {13, 14, 15, 16, 17, 18, 19},
    {4, 5, 6, 7, 8, 9, 10}
};
int oppsite[8] = {5, 4, 7, 6, 1, 0, 3, 2};          // Reverse operation
int center[8] = {6, 7, 8, 11, 12, 15, 16, 17};      // Middle 8

int q[N];               // One dimensional read in
int path[100];          // Number of schemes

// Valuation function
int f() {
    int sum[4] = {0};
    for (int i = 0; i < 8; i ++ ) sum[q[center[i]]] ++ ;    // Count the occurrence times of the middle 8 numbers, ranging from 1 to 3
        
    int s = 0;
    for (int i = 1; i <= 3; i ++ ) s = max(s, sum[i]);  
    
    return 8 - s;
}

// Do the x operation. Move the first six backward and the last one becomes the first one
void operate(int x) {
    int t = q[op[x][0]];
    
    for (int i = 0; i < 6; i ++ ) q[op[x][i]] = q[op[x][i + 1]];
    q[op[x][6]] = t;
}

bool dfs(int u, int depth, int last) {
    if (u + f() > depth) return false;
    if (!f()) return true;
    
    for (int i = 0; i < 8; i ++ ) {
        // If (I! = oppsite [last]) at first, last = -1, so the array subscript is out of bounds
        // This reverse operation is very ingenious. You can also judge the special case of last == -1
        if (oppsite[i] != last) {                   // If the current operation is i, it is not the reverse operation of the last operation
            operate(i);
            path[u] = i;
            if (dfs(u + 1, depth, i)) return true;
            operate(oppsite[i]);                    // Restore the site
            path[u] = 0;                            // This is optional
        }
    }

    return false;
}

int main() {
    while (cin >> q[0], q[0]) {
        for (int i = 1; i < N; i ++ ) cin >> q[i];
        
        int depth = 0;
        while (!dfs(0, depth, -1)) depth ++ ;   // Pass on the operation done in the previous step
        
        if (!depth) puts("No moves needed");
        else {
            for (int i = 0; i < depth; i ++ ) printf("%c", path[i] + 'A');
            puts("");
        }
        
        printf("%d\n", q[6]); // The same number in the middle 8 grid 
    }
    
    return 0;
}