使用 Thistlethwaite 算法解决魔方：完整代码实现
#include
// 定义魔方的颜色 enum Color { RED, BLUE, GREEN, WHITE, YELLOW, ORANGE };
// 定义魔方的转动方式 enum Rotation { CLOCKWISE, COUNTERCLOCKWISE, DOUBLE };
// 定义魔方的状态 struct CubeState { Color up[3][3]; // 上层 Color down[3][3]; // 下层 Color left[3][3]; // 左层 Color right[3][3]; // 右层 Color front[3][3]; // 前层 Color back[3][3]; // 后层
bool operator==(const CubeState& other) const {
return memcmp(this, &other, sizeof(other)) == 0;
}
size_t hash() const {
size_t h = 0;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
h ^= std::hash<int>()(up[i][j]);
h ^= std::hash<int>()(down[i][j]) << 1;
h ^= std::hash<int>()(left[i][j]) << 2;
h ^= std::hash<int>()(right[i][j]) << 3;
h ^= std::hash<int>()(front[i][j]) << 4;
h ^= std::hash<int>()(back[i][j]) << 5;
}
}
return h;
}
};
// 定义魔方操作 class Cube { public: void rotate(Color face, Rotation rotation) { // 定义一个临时数组，用于存储需要旋转的面的颜色 Color temp[3][3];
// 根据旋转方式调整魔方状态
switch (face) {
case RED:
// 根据旋转方式调整 red 面的状态
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
temp[i][j] = up[i][j];
}
}
if (rotation == CLOCKWISE) {
for (int i = 0; i < 3; i++) {
up[0][i] = left[2-i][0];
left[2-i][0] = down[2][2-i];
down[2][2-i] = right[i][2];
right[i][2] = temp[0][i];
}
for (int i = 0; i < 3; i++) {
up[1][i] = left[2-i][1];
left[2-i][1] = down[1][2-i];
down[1][2-i] = right[i][1];
right[i][1] = temp[1][i];
}
for (int i = 0; i < 3; i++) {
up[2][i] = left[2-i][2];
left[2-i][2] = down[0][2-i];
down[0][2-i] = right[i][0];
right[i][0] = temp[2][i];
}
} else if (rotation == COUNTERCLOCKWISE) {
for (int i = 0; i < 3; i++) {
up[0][i] = right[i][2];
right[i][2] = down[2][2-i];
down[2][2-i] = left[2-i][0];
left[2-i][0] = temp[0][i];
}
for (int i = 0; i < 3; i++) {
up[1][i] = right[i][1];
right[i][1] = down[1][2-i];
down[1][2-i] = left[2-i][1];
left[2-i][1] = temp[1][i];
}
for (int i = 0; i < 3; i++) {
up[2][i] = right[i][0];
right[i][0] = down[0][2-i];
down[0][2-i] = left[2-i][2];
left[2-i][2] = temp[2][i];
}
} else if (rotation == DOUBLE) {
for (int i = 0; i < 3; i++) {
up[0][i] = down[2][2-i];
down[2][2-i] = temp[0][i];
}
for (int i = 0; i < 3; i++) {
up[1][i] = down[1][2-i];
down[1][2-i] = temp[1][i];
}
for (int i = 0; i < 3; i++) {
up[2][i] = down[0][2-i];
down[0][2-i] = temp[2][i];
}
for (int i = 0; i < 3; i++) {
left[i][0] = right[2-i][2];
right[2-i][2] = temp[i][0];
}
for (int i = 0; i < 3; i++) {
left[i][1] = right[2-i][1];
right[2-i][1] = temp[i][1];
}
for (int i = 0; i < 3; i++) {
left[i][2] = right[2-i][0];
right[2-i][0] = temp[i][2];
}
}
break;
case BLUE:
// 根据旋转方式调整 blue 面的状态
if (rotation == CLOCKWISE) {
rotateFace(front);
for (int i = 0; i < 3; i++) {
temp[0][i] = up[2][2-i];
up[2][2-i] = left[2-i][2];
left[2-i][2] = down[0][i];
down[0][i] = right[i][0];
right[i][0] = temp[0][i];
}
} else if (rotation == COUNTERCLOCKWISE) {
rotateFace(front);
for (int i = 0; i < 3; i++) {
temp[0][i] = up[i][2];
up[i][2] = right[2-i][0];
right[2-i][0] = down[2][2-i];
down[2][2-i] = left[2-i][2];
left[2-i][2] = temp[0][i];
}
} else if (rotation == DOUBLE) {
rotateFace(front);
rotateFace(front);
for (int i = 0; i < 3; i++) {
temp[0][i] = up[2][2-i];
up[2][2-i] = down[0][i];
down[0][i] = temp[0][i];
temp[1][i] = left[2-i][2];
left[2-i][2] = right[i][0];
right[i][0] = temp[1][i];
}
}
break;
case GREEN:
// 根据旋转方式调整 green 面的状态
if (rotation == CLOCKWISE) {
rotateFace(back);
for (int i = 0; i < 3; i++) {
temp[0][i] = up[i][0];
up[i][0] = right[2-i][2];
right[2-i][2] = down[2][2-i];
down[2][2-i] = left[2-i][0];
left[2-i][0] = temp[0][i];
}
} else if (rotation == COUNTERCLOCKWISE) {
rotateFace(back);
for (int i = 0; i < 3; i++) {
temp[0][i] = up[2][2-i];
up[2][2-i] = left[2-i][0];
left[2-i][0] = down[0][i];
down[0][i] = right[i][2];
right[i][2] = temp[0][i];
}
} else if (rotation == DOUBLE) {
rotateFace(back);
rotateFace(back);
for (int i = 0; i < 3; i++) {
temp[0][i] = up[i][0];
up[i][0] = down[2][2-i];
down[2][2-i] = temp[0][i];
temp[1][i] = left[2-i][0];
left[2-i][0] = right[i][2];
right[i][2] = temp[1][i];
}
}
break;
case WHITE:
// 根据旋转方式调整 white 面的状态
if (rotation == CLOCKWISE) {
rotateFace(up);
for (int i = 0; i < 3; i++) {
temp[0][i] = front[0][i];
front[0][i] = right[0][i];
right[0][i] = back[0][i];
back[0][i] = left[0][i];
left[0][i] = temp[0][i];
}
} else if (rotation == COUNTERCLOCKWISE) {
rotateFace(up);
for (int i = 0; i < 3; i++) {
temp[0][i] = front[0][i];
front[0][i] = left[0][i];
left[0][i] = back[0][i];
back[0][i] = right[0][i];
right[0][i] = temp[0][i];
}
} else if (rotation == DOUBLE) {
rotateFace(up);
rotateFace(up);
for (int i = 0; i < 3; i++) {
temp[0][i] = front[0][i];
front[0][i] = back[0][i];
back[0][i] = temp[0][i];
temp[1][i] = left[0][i];
left[0][i] = right[0][i];
right[0][i] = temp[1][i];
}
}
break;
case YELLOW:
// 根据旋转方式调整 yellow 面的状态
if (rotation == CLOCKWISE) {
rotateFace(down);
for (int i = 0; i < 3; i++) {
temp[0][i] = front[2][i];
front[2][i] = left[2][i];
left[2][i] = back[2][i];
back[2][i] = right[2][i];
right[2][i] = temp[0][i];
}
} else if (rotation == COUNTERCLOCKWISE) {
rotateFace(down);
for (int i = 0; i < 3; i++) {
temp[0][i] = front[2][i];
front[2][i] = right[2][i];
right[2][i] = back[2][i];
back[2][i] = left[2][i];
left[2][i] = temp[0][i];
}
} else if (rotation == DOUBLE) {
rotateFace(down);
rotateFace(down);
for (int i = 0; i < 3; i++) {
temp[0][i] = front[2][i];
front[2][i] = back[2][i];
back[2][i] = temp[0][i];
temp[1][i] = left[2][i];
left[2][i] = right[2][i];
right[2][i] = temp[1][i];
}
}
break;
case ORANGE:
// 根据旋转方式调整 orange 面的状态
if (rotation == CLOCKWISE) {
rotateFace(left);
for (int i = 0; i < 3; i++) {
temp[0][i] = up[i][0];
up[i][0] = back[2][2-i];
back[2][2-i] = down[2][i];
down[2][i] = front[0][2-i];
front[0][2-i] = temp[0][i];
}
} else if (rotation == COUNTERCLOCKWISE) {
rotateFace(left);
for (int i = 0; i < 3; i++) {
temp[0][i] = up[i][0];
up[i][0] = front[0][2-i];
front[0][2-i] = down[2][i];
down[2][i] = back[2][2-i];
back[2][2-i] = temp[0][i];
}
} else if (rotation == DOUBLE) {
rotateFace(left);
rotateFace(left);
for (int i = 0; i < 3; i++) {
temp[0][i] = up[i][0];
up[i][0] = down[2][i];
down[2][i] = temp[0][i];
temp[1][i] = back[2][2-i];
back[2][2-i] = front[0][2-i];
front[0][2-i] = temp[1][i];
}
}
break;
default:
cout << "无效的面颜色" << endl;
break;
}
}
CubeState getState() const {
return CubeState{
up, down, left, right, front, back
};
}
private: void rotateFace(Color (&face)[3][3]) { Color temp[3][3]; for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { temp[i][j] = face[i][j]; } } for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { face[i][j] = temp[2-j][i]; } } }
Color up[3][3] = {{YELLOW, YELLOW, YELLOW}, {YELLOW, YELLOW, YELLOW}, {YELLOW, YELLOW, YELLOW}}; // 上层
Color down[3][3] = {{WHITE, WHITE, WHITE}, {WHITE, WHITE, WHITE}, {WHITE, WHITE, WHITE}}; // 下层
Color left[3][3] = {{ORANGE, ORANGE, ORANGE}, {ORANGE, ORANGE, ORANGE}, {ORANGE, ORANGE, ORANGE}}; // 左层
Color right[3][3] = {{RED, RED, RED}, {RED, RED, RED}, {RED, RED, RED}}; // 右层
Color front[3][3] = {{GREEN, GREEN, GREEN}, {GREEN, GREEN, GREEN}, {GREEN, GREEN, GREEN}}; // 前层
Color back[3][3] = {{BLUE, BLUE, BLUE}, {BLUE, BLUE, BLUE}, {BLUE, BLUE, BLUE}}; // 后层
};
// Thistlethwaite 算法类 class ThistlethwaiteSolver { public: void solve(CubeState state) { // 使用 Thistlethwaite 算法解决魔方 // 1. 将魔方还原到第一层 solveToLayer1(state);
// 2. 将魔方还原到第二层
solveToLayer2(state);
// 3. 将魔方还原到第三层
solveToLayer3(state);
// 4. 将魔方还原到最终状态
solveToFinalState(state);
}
private: void solveToLayer1(CubeState state) { // TODO: 实现将魔方还原到第一层的逻辑 }
void solveToLayer2(CubeState state) {
// TODO: 实现将魔方还原到第二层的逻辑
}
void solveToLayer3(CubeState state) {
// TODO: 实现将魔方还原到第三层的逻辑
}
void solveToFinalState(CubeState state) {
// TODO: 实现将魔方还原到最终状态的逻辑
}
};
int main() { // 创建魔方对象 Cube cube;
// 获取初始魔方状态
CubeState initialState = cube.getState();
// 创建 ThistlethwaiteSolver 对象
ThistlethwaiteSolver solver;
// 使用 Thistlethwaite 算法解决魔方
solver.solve(initialState);
return 0;
}
原文地址: https://www.cveoy.top/t/topic/nhUo 著作权归作者所有。请勿转载和采集!