解魔方机器人大创项目（持续更新）

2016-10-12

和海哥奋战一周，1600行的暴力解写出来啦，纯模拟，毫无算法，后续更新

项目地址：https://github.com/Hengliy/CubeRobot

---

2017-3-14

研究八数码的双向广搜解：

#include <iostream>
#include <cstring>
#include <cstdio>

//八数码问题总共9个位置，也可以求15数码之类。
#define N 9
#define R 3
#define C 3
#define FACTORIAL_N 362890   //9! + 10, 10只是习惯了防止数组越界。
#define NO_PARENT -1  //没有父节点
struct node
{
    char data[N + 1];   //当前节点数字排列
    int blankPos;   //空格位置
    int parentIndex;    //父节点在数组a中的下标，可据此找到上一步的移动信息。
    int d;            //从父节点的哪个方向扩展而来
    int key;
}a[2][FACTORIAL_N];
bool visited[2][FACTORIAL_N];
const int factorial[N] = { 1, 1, 2, 6, 24, 120, 720, 5040, 40320 };  //康托展开需要，N!，如求15数码之类需扩展此处。
int canMoveStep[N][4];   //每个数字四个方向是否可移动，四个方向走算位置变换，如空格与上方换位置数就减3。
char direction[] = "lurd";
char target[] = "123456789";

int hash(char* data)
{
    int sum = 0;
    for (int i = 0; i < N; i++) {
        int count = 0;
        for (int j = i + 1; j < N; j++) {
            if (data[i] > data[j]) {  //求逆序数数目，因为是只找data[i]右边的数，所以不用判断比它小的数是否已经用过。
                count++;
            }
        }
        sum += count * factorial[N - i - 1];
    }
    return sum;
}

inline bool getTarget(node *a)
{
    return strcmp(a->data, target) == 0;
}

int dbfs(node *firstNode)
{
    int key;
    memset(visited, 0, sizeof(visited));
    int head[] = { 0, 0 }, tail[] = { 1, 1 };  //首、尾指针
    strcpy(a[0][head[0]].data, firstNode->data);
    a[0][head[0]].blankPos = firstNode->blankPos;
    a[0][head[0]].parentIndex = NO_PARENT;
    a[0][head[0]].d = -1;
    key = hash(a[0][head[0]].data);
    visited[0][key] = 1;
    a[0][head[0]].key = key;
    if (getTarget(&a[0][head[0]])) return head[0];

    strcpy(a[1][head[1]].data, target);
    for (int i = 0; i < N; i++) {
        if (target[i] == N + '0') {
            a[1][head[1]].blankPos = i;
            break;
        }
    }
    a[1][head[1]].parentIndex = NO_PARENT;
    a[1][head[1]].d = -1;
    key = hash(a[1][head[1]].data);
    visited[1][key] = 1;
    a[1][head[1]].key = key;

    while (head[0] < tail[0] && head[1] < tail[1]) {
        //从节点少的一边进行扩展
        int currentQueue = (tail[0] - head[0] > tail[1] - head[1]) ? 1 : 0;
        int blankPos = a[currentQueue][head[currentQueue]].blankPos;
        for (int i = 0; i < 4; i++) {
            if (canMoveStep[blankPos][i]) {
                int newBlankPos = a[currentQueue][tail[currentQueue]].blankPos = blankPos + canMoveStep[blankPos][i];
                strcpy(a[currentQueue][tail[currentQueue]].data, a[currentQueue][head[currentQueue]].data);   //将移动后的新结点信息放入对列中。
                char temp = a[currentQueue][tail[currentQueue]].data[blankPos];    //保存新结点的数字排列
                a[currentQueue][tail[currentQueue]].data[blankPos] = a[currentQueue][tail[currentQueue]].data[newBlankPos];
                a[currentQueue][tail[currentQueue]].data[newBlankPos] = temp;
                a[currentQueue][tail[currentQueue]].parentIndex = head[currentQueue];
                a[currentQueue][tail[currentQueue]].d = i;

                key = hash(a[currentQueue][tail[currentQueue]].data);
                a[currentQueue][tail[currentQueue]].key = key;
                if (!visited[currentQueue][key]) {
                    visited[currentQueue][key] = 1;
                    //两个对列中有访问到相同的结点即表示找到了起点到终点的路径。
                    int otherQueue = currentQueue ? 0 : 1;
                    if (visited[otherQueue][key]) return tail[currentQueue] << 1 | currentQueue;
                    tail[currentQueue]++;
                }
            }
        }
        head[currentQueue]++;  //处理下一个入列结点
    }
    return -1;
}

void initMoveFlags()
{
    memset(canMoveStep, 0, sizeof(canMoveStep));
    for (int i = 0; i < N; i++) {
        canMoveStep[i][0] = i % C != 0 ? -1 : 0;   //第0列不能向左搜索
        canMoveStep[i][2] = (i + 1) % C != 0;   //最后一列不能向右搜索
        canMoveStep[i][1] = i < C ? 0 : -C;     //第0行不能向上搜索
        canMoveStep[i][3] = i >= (N - C) ? 0 : C;   //最后一行不能向下搜索
    }
}

void print(int result)
{
    if (result == -1) {
        printf("unsolvable\n");
        return;
    }
    //在哪个对列中被找到及在当前对列中的下标。
    int resultQueue = result & 1, resultIndex = result >> 1;
    int key = hash(a[resultQueue][resultIndex].data);
    char step[FACTORIAL_N];    //存放移动路径
    int start = FACTORIAL_N / 2, end = start;
    int firstQueueIndex = 1, sencondQueueIndex = 1;;
    if (resultQueue == 1) {
        while (a[0][firstQueueIndex].key != key) firstQueueIndex++;
        sencondQueueIndex = resultIndex;
    }
    else {
        firstQueueIndex = resultIndex;
        while (a[1][sencondQueueIndex].key != key) sencondQueueIndex++;
    }
    int currentIndex = firstQueueIndex;
    // //d表示从父节点的哪个方向来，如果当前节点没有父节点则表示是开始结点或结束结点。
    while (a[0][currentIndex].parentIndex != NO_PARENT) {
        step[--start] = direction[a[0][currentIndex].d];
        currentIndex = a[0][currentIndex].parentIndex;
    }

    currentIndex = sencondQueueIndex;
    while (a[1][currentIndex].parentIndex != NO_PARENT) {
        //双向广搜相对搜索到相同结点时，从相同结点开始到结束结点是反向往回走，即与搜索到的方向相反。
        step[end++] = direction[(a[1][currentIndex].d + 2) % 4];
        currentIndex = a[1][currentIndex].parentIndex;
    }
    for (int i = start; i < end; i++) {
        printf("%c", step[i]);
    }
    printf("\n");
}

int main()
{
    //freopen("in.txt", "r", stdin);
    node firstNode;
    initMoveFlags();
    char ch[2];
    for (int i = 0; i < N; i++) {
        scanf("%s", ch);
        if (ch[0] == 'x') {
            firstNode.data[i] = N + '0';
            firstNode.blankPos = i;
        }
        else {
            firstNode.data[i] = ch[0];
        }
    }
    firstNode.data[N] = '\0';
    int result = dbfs(&firstNode);
    print(result);
    return 0;
}

广搜 双向广搜 A 启发式搜索